123 Eng

vidhya123 · Joined: 30 Mar 2007 Posts: 121

5.1 Greedy Method

Greedy method is a method of choosing a subset of the dataset as the solution set that results in some profit. Consider a problem having n inputs, we are required to obtain the solution which is a series of subsets that satisfy some constraints or conditions. Any subset, which satisfies these constraints, is called a feasible solution. It is required to obtain the feasible solution that maximizes or minimizes the objective function. This feasible solution finally obtained is called optimal solution.
If one can devise an algorithm that works in stages, considering one input at a time and at each stage, a decision is taken on whether the data chosen results with an optimal solution or not. If the inclusion of a particular data results with an optimal solution, then the data is added into the partial solution set. On the other hand, if the inclusion of that data results with infeasible solution then the data is eliminated from the solution set.

The general algorithm for the greedy method is

1. Choose an element e belonging to dataset D.

2. Check whether e can be included into the solution set S if Yes solution set is s ¬ s U e.

3. Continue until s is filled up or D is exhausted whichever is earlier.

5.1 Cassette Filling

Consider n programs that are to be stored on a tape of length L. Each program I is of length li where i lies between 1 and n. All programs can be stored on the tape iff the sum of the lengths of the programs is at most L. It is assumed that, whenever a program is to be retrieved the tape is initially positioned at the start end.

Let tj be the time required retrieving program ij where programs are stored in the order

I = i1, i2, i3, …,in.

The time taken to access a program on the tape is called the mean retrieval time (MRT)

i.e., tj =S lik k=1,2,…,j

Now the problem is to store the programs on the tape so that MRT is minimized. From the above discussion one can observe that the MRT can be minimized if the programs are stored in an increasing order i.e., l1 £ l2 £ l3, …£ ln.

Hence the ordering defined minimizes the retrieval time. The solution set obtained need not be a subset of data but may be the data set itself in a different sequence.

Illustration

Assume that 3 sorted files are given. Let the length of files A, B and C be 7, 3 and 5 units respectively. All these three files are to be stored on to a tape S in some sequence that reduces the average retrieval time. The table shows the retrieval time for all possible orders.

Order of recording Retrieval time MRT
ABC 7+(7+3)+(7+3+5)=32 32/3
ACB 7+(7+5)+(7+5+3)=34 34/3
BAC 3+(3+7)+(3+7+5)=28 28/3
BCA 3+(3+5)+(3+5+7)=26 26/3
CAB 5+(5+7)+(5+7+3)=32 32/3
CBA 5+(5+3)+(5+3+7)=28 28/3
lick here for more details:
http://onestopgate.com/gate-study-material/5.1.asp