Greedy Algorithm

Greedy algorithm is an algorithmic paradigm that builds a solution incrementally, making the locally optimal choice at each step with the hope of finding a globally optimal solution. Unlike dynamic programming, which explores the consequences of each choice recursively, or branch and bound, which maintains conservative bounds on unexplored regions, the greedy algorithm commits: it chooses, it does not reconsider. This commitment is its defining feature and its fundamental limitation.

The paradigm appears throughout computer science and operations research: Dijkstra's algorithm for shortest paths, Kruskal's and Prim's algorithms for minimum spanning trees, Huffman coding for data compression, and the fractional knapsack problem. In each case, the greedy choice is justified by a problem-specific structure — a greedy-choice property — that guarantees local optimality implies global optimality.

The Greedy-Choice Property

A problem exhibits the greedy-choice property if a globally optimal solution can be reached by a sequence of locally optimal choices, without reconsideration. Formally, if S is an optimal solution and x is the greedy choice at the first step, then there exists an optimal solution S' that contains x. This property is not universal. It holds for minimum spanning trees because any locally optimal edge can be extended to a globally optimal tree; it fails for the 0-1 knapsack problem because a locally optimal item may consume capacity that would be better used by a combination of smaller items.

The greedy-choice property is often confused with the optimal substructure property, which is necessary but not sufficient. Optimal substructure means that an optimal solution contains optimal solutions to subproblems. The greedy-choice property is stronger: it means that the optimal solution to the problem can be constructed by making a greedy choice and then solving the remaining subproblem optimally. Dynamic programming requires only optimal substructure; greedy algorithms require both optimal substructure and the greedy-choice property.

Greedy Algorithms and Heuristics

The relationship between greedy algorithms and heuristics is subtle and frequently misunderstood. In the context of informed search, greedy best-first search uses a heuristic to estimate proximity to the goal and always expands the node that appears closest. This is a greedy strategy in the heuristic space, not in the solution space. The algorithm is making a locally optimal choice based on incomplete information, and that choice may lead it into dead ends or local optima from which it cannot recover.

This reveals a deeper distinction. A true greedy algorithm — one with the greedy-choice property — never needs to backtrack because its local choices are provably safe. A heuristic greedy algorithm — greedy best-first search, hill climbing, simulated annealing without sufficient temperature — makes commitments it cannot justify, and suffers the consequences. The former is a proof technique; the latter is a bet. The distinction is not in the algorithm's surface behavior but in the mathematical structure of the problem it faces.

Limits and Critiques

The greedy paradigm has been both celebrated as a model of efficient decision-making and criticized as a model of human cognitive failure. In bounded rationality research, the satisficing heuristic — choose the first option that meets a threshold — resembles a greedy strategy. The criticism, most forcefully advanced by Kahneman and Tversky, is that humans are excessively greedy: they anchor on initial information, follow availability heuristics, and fail to reconsider commitments when new evidence arrives.

But this critique conflates two different phenomena. Algorithmic greediness — choosing the locally optimal action in a structured problem — is often optimal. Cognitive greediness — failing to integrate new information because of sunk costs or confirmation bias — is a failure of updating, not of commitment. The greedy algorithm does not ignore new evidence; it simply does not encounter it, because the problem structure guarantees that the evidence would not change the decision. The human failure is not greediness but rigidity: the inability to revise commitments when the problem structure does not justify them.

The greedy algorithm is not a model of human reasoning, and it is not a universal problem-solving strategy. It is a proof technique disguised as a search algorithm — a demonstration that under certain structural conditions, commitment is not recklessness but rationality. The question is never whether to be greedy. The question is whether the problem permits it. And the tragedy of both algorithms and humans is that we often cannot tell the difference until it is too late.