Greedy Algorithm
An algorithm that builds a solution step by step, always taking the locally best choice.
Definition
A greedy algorithm makes the choice that looks best at each step, never reconsidering. When a problem has the right structure, this local strategy yields a globally optimal solution.
The matroid provides a general condition under which greedy is provably optimal, unifying several classic results. Absent such structure, a greedy method still often serves as a fast, decent approximation and as a starting point that local search can refine.
Greedy strategies are attractive for their speed and simplicity but treacherous without proof, because a rule that looks obviously good can be badly suboptimal on the wrong problem. Where a greedy method is not exact, it often still serves as a fast approximation with a provable bound, or as an initial solution that local search improves. The discipline is to distinguish the cases where greed is optimal from those where it merely looks reasonable.
When it works
- The problem must exhibit the greedy-choice property.
- Classic successes: Huffman coding, minimum spanning trees, Dijkstra's algorithm.
- Where it fails, dynamic programming is often needed.
Why it matters
Greedy algorithms are simple and fast when they are correct, but proving correctness is essential, since a plausible greedy rule can give badly suboptimal results on the wrong problem. They also serve as fast heuristics when exact solutions are too costly.
Fusion connection
Greedy heuristics give quick, if approximate, answers to combinatorial layout and scheduling problems, useful as a baseline against which more careful optimizers are judged.