Greedy Algorithm

Version

v1 · 2026-08-24 · History

Prime #

887

Origin domain

Computer Science & Software Engineering

Subdomain

algorithms → Computer Science & Software Engineering

Core Idea

Commit to the locally best available choice at each step, irrevocably, with no lookahead and no backtracking. The pattern is interesting for its sharp dichotomy: on matroid-shaped problems greedy is provably optimal; otherwise it locks into local optima a little foresight would have avoided.

How would you explain it like I'm…

Grab the Biggest Now

Imagine you grab the biggest piece of candy you can see right now, every single time, and never trade it back. Sometimes that gets you the most candy, but sometimes grabbing a small piece now would have let you reach a huge piece later. Always grabbing the best thing in front of you can win, but it can also make you miss the bigger prize.

Best-Right-Now, No Takebacks

A greedy method always takes the best choice it can see right now, locks it in, and never goes back to change it. It's fast and simple because it only ever looks at the present step, not the future. For some kinds of problems this always gives the perfect answer. But for others it gets stuck: it gives up a big future reward because it grabbed the easy thing now — like taking cheese now and missing the steak later. So the real question whenever you spot a greedy method is whether the problem is one of the lucky kinds where greedy always wins, or one where its blindness to the future will cost you.

Local Best, No Lookahead

A greedy algorithm commits to the locally best available choice at each step, irrevocably, and continues until the problem is solved — no lookahead, no backtracking, no revision. Each decision uses only the present local evaluation and is then sealed. What makes it interesting is its sharp success/failure split: for problems with a matroid-like exchange property, greedy choice is provably globally optimal; for others it is provably suboptimal and traps the search in local optima that only foresight, randomization, or restart can escape. The reason is the same in every domain — greedy is fast, simple, and parallel-friendly, but it pays an information cost by ignoring everything its local evaluation can't see. When the global optimum is just a concatenation of locally optimal pieces, that cost is zero and greedy is unbeatable; when reaching it requires a locally costly move to unlock a later big gain ('give up cheese now for steak later'), greedy is structurally blind. Naming a process greedy makes the trade-off visible and points to the diagnostic question: is this problem matroid-shaped, and if not, where will the blindness bite?

 

A greedy algorithm is the structural pattern of committing to the locally best available choice at each step, irrevocably, and continuing until the problem is solved. The defining commitment is no lookahead, no backtracking, no revision: at each decision point the strategy uses only the present local evaluation, and the choice is sealed. The pattern is interesting precisely because of its sharp success/failure dichotomy — for some problem structures (those satisfying a matroid or matroid-like exchange property) greedy choice is provably globally optimal, while for others it is provably suboptimal and locks the search into local optima from which only foresight, randomisation, or restart can escape. The structural force comes from the same fact in every substrate: greedy is fast, simple, and parallel-friendly, but it pays an information cost, ignoring everything the local evaluation function cannot see. When the global optimum is a concatenation of locally optimal pieces (the matroid case), the cost is zero and greedy is unbeatable; when the global optimum requires a locally costly move to enable a later large gain — 'give up cheese now for steak later' — greedy is structurally blind and systematically produces worse outcomes than even minimal lookahead. Naming a process as greedy makes this trade-off visible and selects the diagnostic question: is this problem matroid-shaped, and if not, where will greedy's blindness bite? The substrate-neutral skeleton is local commitment plus irrevocability plus the matroid criterion plus a small family of escape patches, and although the name is coined in computer science, the no-lookahead-no-backtrack commitment is a structural property that recurs in behaviour, evolution, policy, and learning.

Broad Use

• Computer science: minimum spanning trees (provably optimal), Huffman codes, Dijkstra's algorithm, greedy set cover (a logarithmic-factor approximation).
• Behavioral economics: hyperbolic discounting and the marshmallow test — taking the locally best immediate payoff and forfeiting larger delayed ones.
• Evolution: incremental fitness optimization that locks populations onto local peaks — selection without lookahead.
• Policy: electoral-cycle policy that optimizes myopically per term, forfeiting long-term obligations.
• Bureaucracy and triage: queue-by-loudest-complaint and deal-with-the-closest-deadline.
• Machine learning: greedy decision-tree induction and greedy sequence decoding versus beam search.

Clarity

Makes the commitment-irrevocability of each step explicit and separates "the local score is wrong" from "greedy is wrong for this problem shape" — the single biggest clarifying move, since greedy is provably optimal where the structure permits.

Manages Complexity

Compresses the decision policy to one locally evaluable function and dispenses with state; when greedy fails, the diagnosis is compact — find the door-closing step, then widen the score, add lookahead, or restructure the problem.

Abstract Reasoning

The matroid criterion tests whether local-best concatenates to global-best; the single counter-example "give up a local best to enable a larger global gain" is the canonical failure shape, and random restart is a portable escape patch.

Knowledge Transfer

• Algorithms → life: the matroid criterion explains why accumulating independent course credits suits local preferences while saving a down payment demands foresight.
• Evolution → culture: populations stay stuck on local peaks until drift supplies the randomization a greedy process needs to escape — the same fact in cultural norm-evolution.
• Behavior → policy: commitment devices, defaults, and auto-escalators are the human analogue of constraints that stop greedy from closing a needed door.

Example

A salesperson's call list greedily sorted by smallest immediate effort fails when large accounts need multi-touch sequences the per-step rule undervalues — and the same three-part fix (change the score, add lookahead, add restart) that patches it also patches a greedy investment policy.

Relationships to Other Abstractions

Current abstraction Greedy Algorithm Prime

Parents (1) — more general patterns this builds on

• Greedy Algorithm is a kind of Heuristic Prime

  'Not heuristic in general — greedy is a specific heuristic schema (local-best, irrevocable, no-backtrack) with a sharp optimality theorem (matroids) most heuristics lack.' A specialization of heuristic.

Children (1) — more specific cases that build on this

• Greedy coloring Domain-specific is a kind of Greedy Algorithm

  The proposed strict upward parent is prime:greedy_algorithm.

Hierarchy paths (2) — routes to 2 parentless roots

• Greedy Algorithm → Heuristic → Approximation → Representation → Abstraction

Show alternative path (1)

Not to Be Confused With

• Greedy Algorithm is not Dynamic Programming because greedy uses only present local evaluation with no memo table, whereas dynamic programming stores and recombines subproblem solutions to discover that a locally-suboptimal move enables a globally-optimal whole.
• Greedy Algorithm is not a Local Optimum because a local optimum is a state (a point no neighbor improves), whereas greedy is the procedure that characteristically lands in one.
• Greedy Algorithm is not Satisficing because satisficing stops at the first good-enough option against a threshold, whereas greedy always takes the locally best and runs to completion.