Understanding Greedy Algorithms in Algorithm Analysis
Greedy algorithms are a simpler approach compared to dynamic programming, focusing on making locally optimal choices in order to achieve a globally optimal solution. While not always yielding the best solution, greedy algorithms can provide optimal solutions for problems with specific characteristics. This overview covers the concept, steps towards a greedy solution, designing strategies, and the correctness of greedy algorithms in algorithm analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Analysis of Algorithms CS 477/677 Instructor: Monica Nicolescu Lecture 20
Greedy Algorithms Similar to dynamic programming, but simpler approach Also used for optimization problems Idea: When we have a choice to make, make the one that looks best right now Make a locally optimal choice in the hope of getting a globally optimal solution Greedy algorithms don t always yield an optimal solution When the problem has certain general characteristics, greedy algorithms give optimal solutions CS 477/677 - Lecture 20 2 2
Activity Selection Problem Schedule the largest possible set of non-overlapping activities for a given room Start End Activity 1 8:00am 9:15am Numerical methods class 2 8:30am 10:30am Movie presentation (refreshments served) 3 9:20am 11:00am Data structures class 4 10:00am noon Programming club mtg. (Pizza provided) 5 11:30am 1:00pm Computer graphics class 6 1:05pm 2:15pm Analysis of algorithms class 7 2:30pm 3:00pm Computer security class 8 noon 4:00pm Computer games contest (refreshments served) 9 4:00pm 5:30pm Operating systems class CS 477/677 - Lecture 20 3
Steps Toward Our Greedy Solution 1. Determined the optimal substructure of the problem 2. Developed a recursive solution 3. Proved that one of the optimal choices is the greedy choice 4. Showed that all but one of the subproblems resulted by making the greedy choice are empty 5. Developed a recursive algorithm that implements the greedy strategy 6. Converted the recursive algorithm to an iterative one CS 477/677 - Lecture 20 4
Designing Greedy Algorithms 1. Cast the optimization problem as one for which: we make a (greedy) choice and are left with only one subproblem to solve 2. Prove the GREEDY CHOICE property: that there is always an optimal solution to the original problem that makes the greedy choice 3. Prove the OPTIMAL SUBSTRUCTURE: the greedy choice + an optimal solution to the resulting subproblem leads to an optimal solution CS 477/677 - Lecture 20 5
Correctness of Greedy Algorithms 1. Greedy Choice Property A globally optimal solution can be arrived at by making a locally optimal (greedy) choice 2. Optimal Substructure Property We know that we have arrived at a subproblem by making a greedy choice Optimal solution to subproblem + greedy choice optimal solution for the original problem CS 477/677 - Lecture 20 6
Dynamic Programming vs. Greedy Algorithms Dynamic programming We make a choice at each step The choice depends on solutions to subproblems Bottom up solution, from smaller to larger subproblems Greedy algorithm Make the greedy choice and THEN Solve the subproblem arising after the choice is made The choice we make may depend on previous choices, but not on solutions to subproblems Top down solution, problems decrease in size CS 477/677 - Lecture 20 7
The Knapsack Problem The 0-1 knapsack problem A thief robbing a store finds n items: the i-th item is worth vi dollars and weights wi pounds (vi, wi integers) The thief can only carry W pounds in his knapsack Items must be taken entirely or left behind Which items should the thief take to maximize the value of his load? The fractional knapsack problem Similar to above The thief can take fractions of items CS 477/677 - Lecture 20 8
Fractional Knapsack Problem Knapsack capacity: W There are n items: the i-th item has value vi and weight wi Goal: Find fractions xi so that for all 0 xi 1, i = 1, 2, .., n wixi W and xivi is maximum CS 477/677 - Lecture 20 9
Fractional Knapsack Problem Greedy strategy 1: Pick the item with the maximum value E.g.: W = 1 w1 = 100, v1 = 2 w2 = 1, v2 = 1 Taking from the item with the maximum value: Total value (choose item 1) = v1W/w1 = 2/100 Smaller than what the thief can take if choosing the other item Total value (choose item 2) = v2W/w2 = 1 CS 477/677 - Lecture 20 10
Fractional Knapsack Problem Greedy strategy 2: Pick the item with the maximum value per pound vi/wi If the supply of that element is exhausted and the thief can carry more: take as much as possible from the item with the next greatest value per pound It is good to order items based on their value per pound v v v ... 1 2 n w w w 1 2 n CS 477/677 - Lecture 20 11
Fractional Knapsack Problem Alg.: Fractional-Knapsack (W, v[n], w[n]) 1. w = W 2. While w > 0 and there are items remaining 3. pick item i with maximum vi/wi 4. xi min (1, w/wi) 5. remove item i from list 6. w w xiwi w the amount of space remaining in the knapsack Running time: (n) if items already ordered; else (nlgn) CS 477/677 - Lecture 20 12
Fractional Knapsack - Example E.g.: 20 --- 30 $80 + Item 3 50 50 20 Item 2 $100 30 Item 1 + 20 10 10 $60 $60 $100 $120 $240 $6/pound $5/pound $4/pound CS 477/677 - Lecture 20 13
Greedy Choice 1 x1 x1 2 x2 x2 3 j n x3 x3 Items: Optimal solution: Greedy solution: We know that: x1 x1 greedy choice takes as much as possible from item 1 Modify the optimal solution to take x1 of item 1 We have to decrease the quantity taken from some item j: the new xjis decreased by: Increase in profit: Decrease in profit: 1 1 1 (x v ) x - (x v w v xj xj xn xn (x1 - x1) w1/wj (x x - 1 (x v ) 1 1 x - )w v /w 1 1 1 j j x - v )w v /w 1 1 1 j j v True, since x1 had the best value/pound ratio j j 1 1 1 w w w 1 j j CS 477/677 - Lecture 20 14
The 0-1 Knapsack Problem Thief has a knapsack of capacity W There are n items: for i-th item value vi and weight wi Goal: Find coefficients xi so that for all xi = {0, 1}, i = 1, 2, .., n wixi W and xivi is maximum CS 477/677 - Lecture 20 15
0-1 Knapsack - Greedy Strategy E.g.: 30 Item 3 $120 + 50 50 20 50 Item 2 $100 30 Item 1 + 20 20 $100 10 10 $60 $60 $100 $120 $160 $220 $6/pound $5/pound $4/pound None of the solutions involving the greedy choice (item 1) leads to an optimal solution The greedy choice property does not hold CS 477/677 - Lecture 20 16
0-1 Knapsack - Dynamic Programming P(i, w) the maximum profit that can be obtained from items 1 to i, if the knapsack has size w Case 1: thief takes item i vi + P(i - 1, w-wi) P(i, w) = Case 2: thief does not take item i P(i, w) = P(i - 1, w) CS 477/677 - Lecture 20 17
0-1 Knapsack - Dynamic Programming Item i was taken Item i was not taken P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } W w - wi w 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 first second i-1 i n CS 477/677 - Lecture 20 18
W = 5 Example: Item 1 2 3 4 Weight 2 1 3 2 Value 12 10 20 15 P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } 0 1 2 3 4 5 0 P(1, 1) = P(0, 1) = 0 0 0 0 0 0 0 1 2 3 4 0 12 12 0 12 12 P(1, 2) = max{12+0, 0} = 12 10 12 22 22 22 0 P(1, 3) = max{12+0, 0} = 12 10 12 22 30 32 0 P(1, 4) = max{12+0, 0} = 12 10 15 25 30 37 0 max{12+0, 0} = 12 P(1, 5) = P(2, 1)= max{10+0, 0} = 10 P(3, 1)= P(2,1) = 10 P(4, 1)= P(3,1) = 10 P(2, 2)= P(3, 2)= P(2,2) = 12 max{10+0, 12} = 12 P(4, 2)= max{15+0, 12} = 15 P(4, 3)= max{15+10, 22}=25 P(2, 3)= max{10+12, 12} = 22 P(3, 3)= max{20+0, 22}=22 P(2, 4)= max{10+12, 12} = 22 P(3, 4)= max{20+10,22}=30 P(4, 4)= max{15+12, 30}=30 max{20+12,22}=32 P(4, 5)= max{15+22, 32}=37 P(2, 5)= max{10+12, 12} = 22 P(3, 5)= CS 477/677 - Lecture 20 19
Reconstructing the Optimal Solution 0 1 2 3 4 5 Item 4 0 0 0 0 0 0 0 1 2 3 4 0 12 12 0 12 12 Item 2 10 12 22 22 22 0 Item 1 10 12 22 30 32 0 10 15 25 30 37 0 Start at P(n, W) When you go left-up item i has been taken When you go straight up item i has not been taken CS 477/677 - Lecture 20 20
Optimal Substructure Consider the most valuable load that weights at most W pounds If we remove item j from this load The remaining load must be the most valuable load weighing at most W wj that can be taken from the remaining n 1 items CS 477/677 - Lecture 20 21
Overlapping Subproblems P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } w W 0: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i-1 i n E.g.: all the subproblems shown in grey may depend on P(i-1, w) CS 477/677 - Lecture 20 22
Readings Chapters 14, 15 CS 477/677 - Lecture 20 23
