Greedy Algorithms
A greedy algorithm makes the locally best choice at each step, which yields a global optimum only when the problem has the right structure.
Take the best each step
A greedy algorithm builds a solution one choice at a time, always taking the option that looks best right now and never reconsidering. It is simple and fast, but it is only correct when the local choices provably lead to a global optimum. Establishing that guarantee is the whole challenge of applying the greedy method.
When greedy is optimal
Greedy algorithms are provably optimal for problems with two properties. Greedy-choice property: a globally optimal solution can be reached by a sequence of locally optimal choices. Optimal substructure: after making the greedy choice, what remains is a smaller instance of the same problem. When these hold, greedy beats dynamic programming in both simplicity and speed.
- Dijkstra's shortest paths (non-negative weights)
- Prim's and Kruskal's minimum spanning trees
- Huffman coding for optimal prefix codes
- Interval scheduling by earliest finish time
When greedy fails
For many problems the greedy choice is a trap. The 0/1 knapsack problem cannot be solved greedily by value density, and making change with arbitrary coin denominations can require dynamic programming to reach the fewest coins. A greedy heuristic may still be useful as a fast approximation even when it is not exact.
Proving correctness
The two standard proof techniques are an exchange argument, which shows any optimal solution can be transformed into the greedy one without getting worse, and a stays-ahead argument, which shows the greedy partial solution is at least as good as any other at every step. Without such a proof, a greedy algorithm is only a heuristic.