Greedy algorithms problems and solutions

greedy algorithms examples and greedy algorithms list and greedy algorithms problems solved
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Greedy algorithms Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Greedy algorithms 2 Algorithm Design To now, we have examined a number of data structures and algorithms to manipulate them We have seen examples of efficient strategies – Divide and conquer • Binary search • Depth-first tree traversals • Merge sort • Quicksort – Greedy algorithms • Prim’s algorithm • Kruskal’s algorithm • Dijkstra’s algorithmGreedy algorithms 3 Greedy algorithms This topic will cover greedy algorithms: – Definitions – Examples • Making change • Prim’s and Dijkstra’s algorithms – Other examplesGreedy algorithms 4 Greedy algorithms Suppose it is possible to build a solution through a sequence of partial solutions – At each step, we focus on one particular partial solution and we attempt to extend that solution – Ultimately, the partial solutions should lead to a feasible solution which is also optimalGreedy algorithms 5 Making change Consider this commonplace example: – Making the exact change with the minimum number of coins – Consider the Euro denominations of 1, 2, 5, 10, 20, 50 cents – Stating with an empty set of coins, add the largest coin possible into the set which does not go over the required amountGreedy algorithms 9 Making change Notice that each digit can be worked with separately – The maximum number of coins for any digit is three – Thus, to make change for anything less than €1 requires at most six coins – The solution is optimalGreedy algorithms 10 Making change To make change for 0.72¢ requires six Canadian coins – However, we have only four coins less than 1 – This is still, however, optimalGreedy algorithms 11 Making change Does this strategy always work? – What if our coin denominations grow quadraticly? Consider 1, 4, 9, 16, 25, 36, and 49 dumbledores Reference: J.K. Rowlings, Harry Potter, Raincoast Books, 1997.Greedy algorithms 12 Making change Using our algorithm, to make change for 72 dumbledores, we require six coins: 72 = 49 + 16 + 4 + 1 + 1 + 1Greedy algorithms 13 Making change The optimal solution, however, is two 36 dumbledore coinsGreedy algorithms 14 Definition A greedy algorithm is an algorithm which has: – A set of partial solutions from which a solution is built – An objective function which assigns a value to any partial solution Then given a partial solution, we – Consider possible extensions of the partial solution – Discard any extensions which are not feasible – Choose that extension which minimizes the object function This continues until some criteria has been reachedGreedy algorithms 15 Optimal example Prim’s algorithm is a greedy algorithm: – Any connected sub-graph of k vertices and k– 1 edges is a partial solution – The value to any partial solution is the sum of the weights of the edges Then given a partial solution, we – Add that edge which does not create a cycle in the partial solution and which minimizes the increase in the total weight – We continue building the partial solution until the partial solution has n vertices – An optimal solution is foundGreedy algorithms 16 Optimal example Dijkstra’s algorithm is a greedy algorithm: – A subset of k vertices and known the minimum distance to all k vertices is a partial solution Then given a partial solution, we – Add that edge which is smallest which connects a vertex to which the minimum distance is known and a vertex to which the minimum distance is not known – We define the distance to that new vertex to be the distance to the known vertex plus the weight of the connecting edge – We continue building the partial solution until either: • The minimum distance to a specific vertex is known, or • The minimum distance to all vertices is known – An optimal solution is foundGreedy algorithms 17 Optimal and sub-optimal examples Our coin change example is greedy: – Any subset of k coins is a partial solution – The value to any partial solution is the sum of the values Then given a partial solution, we – Add that coin which maximizes the increase in value without going over the target value We continue building the set of coins until we have reached the target value An optimal solution is found with euros and cents, but not with our quadratic dumbledore coins – It fails 29 out of 99 times: 12 18 19 22 23 32 41 42 43 48 52 56 61 64 67 68 70 71 72 73 76 77 80 81 88 90 91 92 97Greedy algorithms 18 Optimal and sub-optimal examples An implementation of the greedy algorithm is straight-forward: void greedy( int value, int coins, int rep, int n ) for ( int i = n - 1; i = 0; i ) repi = 0; while ( coinsi = value ) value -= coinsi; ++( repi ); //++repi also works Greedy algorithms 19 Optimal and sub-optimal examples Determining whether n denominations of coins will allow a greedy algorithm to minimize change is difficult—there are no easy rules 3 – The Pearson test is an O(n ) algorithm which returns either 0 or a value for which the greedy algorithm fails int pearson( int coins, int n ) int m = 0, rep1n, rep2n; for ( int j = 0; j n - 2; ++j ) for ( int i = j; i n - 2; ++i ) greedy( coinsi + 1 - 1, coins, rep1, n ); ++( rep1j ); for ( int k = 0; k j - 2; ++k ) rep1k = 0; int r = 0; for ( int k = 0; k n; ++k ) r += rep1kcoinsk; if ( m == 0 r m ) greedy( r, coins, rep2, n ); int sum1 = 0; for ( int k = 0; k n; ++k ) sum1 += rep1k; int sum2 = 0; for ( int k = 0; k n; ++k ) sum2 += rep2k; if ( sum2 sum1 ) m = r; return m; Jeffrey Shallit, What this Country Needs is an 18¢ Piece. Greedy algorithms 20 Unfeasible example In some cases, it may be possible that not even a feasible solution is found – Consider the following greedy algorithm for solving Sudoku: – For each empty square, starting at the top-left corner and going across: • Fill that square with the smallest number which does not violate any of our conditions • All feasible solutions have equal weightGreedy algorithms 21 Unfeasible example Let’s try this example the previously seen Sudoku square:Greedy algorithms 22 Unfeasible example Neither 1 nor 2 fits into the first empty square, so we fill it with 3Greedy algorithms 23 Unfeasible example The second empty square may be filled with 1