Greedy algorithms

Greedy algorithms are computational strategies that make the locally optimal choice at each stage, hoping that a sequence of locally optimal choices will produce a globally optimal solution. They are the algorithmic embodiment of short-term rationality: never look ahead, never revise, commit to each decision as if it were final. The approach succeeds when a problem exhibits the greedy choice property — the global optimum can be reached by a sequence of local optima — and optimal substructure — an optimal solution contains optimal solutions to subproblems.

Classic successes include Huffman coding, Dijkstra's shortest-path algorithm, and the minimum spanning tree algorithms of Prim and Kruskal. In each case, the greedy choice is not merely efficient; it is correct. The proof of correctness typically involves an exchange argument: show that any optimal solution can be transformed, without loss of optimality, into one that includes the greedy choice.

But the failures are more instructive than the successes. The traveling salesman problem, the knapsack problem, and the problem of learning optimal decision trees all defeat the greedy approach. In these domains, a locally attractive choice forecloses better global configurations. The greedy algorithm, in its single-minded pursuit of immediate gain, walks into local optima from which no sequence of further greedy steps can escape. This is not a bug in the implementation. It is a structural property of problems whose solution landscape is non-convex, multimodal, or path-dependent.

The deeper observation is that greedy algorithms are not merely computational procedures; they are models of decision-making under myopia. An agent that uses a greedy heuristic is not irrational in any simple sense — it is applying a strategy that is optimal for a restricted class of problems to a broader class where it fails. The failure is diagnostic: it reveals where the problem's structure departs from the assumptions that make local rationality sufficient.