Greedy algorithm

A short list of categories : 

1 A short list of categories Algorithm types : Simple recursive algorithms Divide and conquer algorithms Greedy algorithms Dynamic programming algorithms Backtracking algorithms

DEFINATIONS : 

2 DEFINATIONS Feasible Solution Optimum Solution

Optimization problems : 

3 Optimization problems A greedy algorithm works in phases. At each phase: You take the best you can get right now, without regard for future consequences You hope that by choosing a local optimum at each step, you will end up at a global optimum A “greedy algorithm” sometimes works well for optimization problems

Example: Counting money : 

4 Example: Counting money Suppose you want to count out a certain amount of money, using the fewest possible bills and coins A greedy algorithm would do this would be:At each step, take the largest possible bill or coin that does not overshoot Example: To make 6.39 Rs, you can choose: a 5 Rs coin a Rs1 coin, to make 6 Rs a 0.25 Rs coin, to make 6.25 Rs A 0.10 Rs coin, to make 6.35 Rs four 0.1 Rs coins, to make 6.39 Rs. For INDIAN money, the greedy algorithm always gives the optimum solution

A failure of the greedy algorithm : 

5 A failure of the greedy algorithm In some (fictional) monetary system, “krons” come in 1 kron, 7 kron, and 10 kron coins Using a greedy algorithm to count out 15 krons, you would get A 10 kron piece Five 1 kron pieces, for a total of 15 krons This requires six coins A better solution would be to use two 7 kron pieces and one 1 kron piece This only requires three coins The greedy algorithm results in a solution, but not in an optimal solution

General Algorithm : 

6 General Algorithm Algorithm Greedy (a, n) { solution=nil; for (i=1 to n ) { x=select (a); if Feasible (solution ,x) then solution = Union (solution ,x); } return solution }

Job sequencing with deadlines : 

7 Job sequencing with deadlines Problem: n jobs, S={1, 2, …, n}, each job i has a deadline di  0 and a profit pi  0. We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline. The optimal solution = {3, 1, 2, 4, 5}. The total profit = 45+ 99 + 67 + 34 + 23 = 268.

Slide 8: 

8 Algorithm Job_Sequence (d, j, n) { d[0]=j[0]=0; k=j[1]=1; for i=2 to n do { r=k; while( (d [ j [ r ] ] > d [ i] ) && (d[ j[ r] ] ! = r)) r--; if (( d[ j [r] ] <=d[ i]) &&(d[ i] >r)) { for (q=k; q>=(r+1);q--) j[ q+1] = j[ q]; j[ r+1] = i; k++; } } return (k);}

COMPLEXITY ANALYSIS OF JS ALGORITHM : 

9 COMPLEXITY ANALYSIS OF JS ALGORITHM Let n be the number of jobs and s be the number of jobs included in the solution. The loop between lines 4-15 (the for-loop) is iterated (n-1)times. Each iteration takes O(k) where k is the number of existing jobs. The time needed by the algorithm is 0(sn) s  n so the worst case time is 0(n2).

The knapsack problem : 

10 The knapsack problem n objects, each with a weight wi > 0 a profit pi > 0 capacity of knapsack: M Maximize Subject to

Knapsack Problems : 

11 Knapsack Problems 0-1 knapsack  each item is taken or not taken Fractional knapsack  fractions of items can be taken

Greedy or Not? : 

12 Greedy or Not? Fractional knapsack can be solvable by the greedy strategy Compute the profit per weight pi/wi for each item Obeying a greedy strategy, we take as much as possible of the item with the greatest profit per weight Ratio. O(n lg n) (we need to sort the items by value per pound)

Greedy or Not? (Cont.) : 

13 Greedy or Not? (Cont.) 0-1 knapsack cannot be solved by the greedy strategy Unable to fill the knapsack to capacity, and the empty space lowers the effective value per pound of the load We must compare the solution to the sub-problem in which the item is included with the solution to the sub-problem in which the item is excluded before we can make the choice Dynamic Programming

The knapsack algorithm : 

14 The knapsack algorithm The greedy algorithm: Step 1: Sort pi/wi into nonincreasing order. Step 2: Put the objects into the knapsack according to the sorted sequence as possible as we can. e. g. n = 3, M = 20, (p1, p2, p3) = (25, 24, 15) (w1, w2, w3) = (18, 15, 10) Sol: p1/w1 = 25/18 = 1.32 p2/w2 = 24/15 = 1.6 p3/w3 = 15/10 = 1.5 Optimal solution: x1 = 0, x2 = 1, x3 = 1/2 total profit = 24 + 7.5 = 31.5

Slide 15: 

Algorithm Knapsack_Greedy (w[ ], p[], m) { weight=0;profit=0,; while (weight<m) do { i =object with highest profit /weight ratio if ((weight + w[i])<=m) { weight = weight +w[ i]; profit = profit + p[ i] ; }else{ x = (w-weight) / w[i] ; weight = weight + w[i] *x; profit = profit + p[i]*x; }// end of while }// end of function 15