Greedy algorithms are good at finding solutions to problems by choosing a consistently optimal solution on each step.
- An optimal solution is a feasible solution with the largest (or smallest) objective function value.
- A local optimum can be obtained by finding the optimal solution within a neighboring set of candidate solutions.
- A global optimum can be obtained by finding the optimal solutions among all possible solutions.
- Greedy choice property: a global optimum can be obtained by the selection of a local optimum.
- Optimal substructure: a global optimum can be obtained by using the local optimum of its subproblems.
“Greedy stays ahead” arguments
Using “Greedy stays ahead” strategy, the algorithm is always at least as far ahead as the optimal solution of each iteration.
Define your solutions. Define what object will represent the global optimum, and what form each local optimum takes.
Find a measure. Find a series of measurements to ensure your algorithm stays ahead of the local optimums you’ve found.
Proove greedy stays ahead. Inductively show that the local optimums are as good as any of the solution’s measures.
Mathematical induction: a means of proving a theorem by showing that if it is true of any particular case, it is true of the next case in a series, and then showing that it is indeed true in one particular case.
Prove optimality. By contradiction, prove that since the algorithm stays ahead of its previous measures, it must produce an optimal solution.
Mathematical proof by contradiction: assume that a statement is not true and then to show that that assumption leads to a contradiction. In the case of trying to prove this is equivalent to assuming that That is, to assume that is true and is false.
The greedy exchange strategy is used to prove the correctness of greedy algorithms by transforming the global optimum iteratively without worsening its quality.
- Define your solutions. Define an object
Athat will represent the global optimum and an object
Othat represents a local optimum.
- Compare solutions. Show that if the global optimum is not the same as the local optimum, either:
- There is an element in
Othat is not in
- There are two elements of
Othat are in a different order in
- Exchange pieces. Gradually modify the local optimum
Ountil it is the same as the algorithm’s global optimum
- Iterate. Decrease the number of differences between
O, until you can turn
Owithout worsening the quality of the solution. Inductively,
Omust be optimal.
Example: Change-making problem
This classical problem addresses the following question: How can a given amount of money be made with the least number of coins of given denominations 1, 5, 10 and 25?
Input: 37 Output: 4 Explanation: 37 = 25 + 10 + 1 + 1
Implementation in Python:
def change_making_problem(n): count = 0 for coin in [25, 10, 5, 1]: # Largest coin not greater # than the remaining amount. while n >= coin: count += 1 n -= coin return count