Greedy algorithms
Download as ppt, pdf0 likes254 views
This document discusses greedy algorithms and provides an example of the activity selection problem. It can be summarized as: 1. Greedy algorithms make locally optimal choices at each step in the hope that it will lead to a globally optimal solution. They are easier to code but do not always produce an optimal solution. 2. The activity selection problem involves scheduling a maximum number of non-overlapping activities given their start and finish times. The greedy algorithm selects the activity with the earliest finish time at each step. 3. For a problem to be solvable by a greedy approach, it must exhibit the greedy-choice property and optimal substructures - where optimal solutions to sub-problems are contained within an optimal solution to the
More Related Content
What's hot (19)
Similar to Greedy algorithms (20)
More from Md. Shafiuzzaman Hira (20)
Recently uploaded (20)
Greedy algorithms
- 1. Greedy Algorithms Md. Shafiuzzaman Lecturer, Dept. of CSE, JUST
- 2. Greedy algorithms • A greedy algorithm always makes the choice that looks best at the moment – The hope: a locally optimal choice will lead to a globally optimal solution – For some problems, it works • Greedy algorithms tend to be easier to code
- 3. An Activity Selection Problem (Conference Scheduling Problem) • Input: A set of activities S = {a1,…, an} • Each activity has start time and a finish time – ai=(si, fi) • Two activities are compatible if and only if their interval does not overlap • Output: a maximum-size subset of mutually compatible activities
- 4. The Activity Selection Problem • Here are a set of start and finish times • What is the maximum number of activities that can be completed? • {a3, a9, a11} can be completed • But so can {a1, a4, a8’ a11} which is a larger set • But it is not unique, consider {a2, a4, a9’ a11}
- 6. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 7. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 8. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 9. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 10. Early Finish Greedy • Select the activity with the earliest finish • Eliminate the activities that could not be scheduled • Repeat!
- 11. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 12. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 13. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 14. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 15. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 16. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 17. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
- 18. Assuming activities are sorted by finish time
- 19. Why it is Greedy? • Greedy in the sense that it leaves as much opportunity as possible for the remaining activities to be scheduled • The greedy choice is the one that maximizes the amount of unscheduled time remaining
- 20. Elements of Greedy Strategy • An greedy algorithm makes a sequence of choices, each of the choices that seems best at the moment is chosen – NOT always produce an optimal solution • Two ingredients that are exhibited by most problems that lend themselves to a greedy strategy – Greedy-choice property – Optimal substructure
- 21. Greedy-Choice Property • A globally optimal solution can be arrived at by making a locally optimal (greedy) choice – Make whatever choice seems best at the moment and then solve the sub-problem arising after the choice is made – The choice made by a greedy algorithm may depend on choices so far, but it cannot depend on any future choices or on the solutions to sub-problems • Of course, we must prove that a greedy choice at each step yields a globally optimal solution
- 22. Optimal Substructures • A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to sub-problems – If an optimal solution A to S begins with activity 1, then A’ = A – {1} is optimal to S’={i S: si f1}
- 23. Knapsack Problem • One wants to pack n items in a luggage – The ith item is worth vi dollars and weighs wi pounds – Maximize the value but cannot exceed W pounds – vi , wi, W are integers • 0-1 knapsack each item is taken or not taken • Fractional knapsack fractions of items can be taken • Both exhibit the optimal-substructure property – 0-1: If item j is removed from an optimal packing, the remaining packing is an optimal packing with weight at most W-wj – Fractional: If w pounds of item j is removed from an optimal packing, the remaining packing is an optimal packing with weight at most W-w that can be taken from other n-1 items plus wj – w of item j
- 24. Greedy Algorithm for Fractional Knapsack problem • Fractional knapsack can be solvable by the greedy strategy – Compute the value per pound vi/wi for each item – Obeying a greedy strategy, take as much as possible of the item with the greatest value per pound. – If the supply of that item is exhausted and there is still more room, take as much as possible of the item with the next value per pound, and so forth until there is no more room – O(n lg n) (we need to sort the items by value per pound) – Greedy Algorithm? – Correctness?
- 25. O-1 knapsack is harder! • 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 packing – 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