Greedy algorithm
Algorithm making locally optimal choices without reconsidering past decisions.
A greedy algorithm is an algorithmic paradigm that, at each step, makes the choice that is locally optimal and subsequently never reconsiders past decisions. It is frequently employed to solve combinatorial optimization problems. In this context, a greedy algorithm is a special case of dynamic programming, as noted by Uriel Feige, who described it as the ultimate form of dynamic programming where only one partial solution is maintained. However, for this approach to succeed, the problem must possess significant additional structure. In many cases, a greedy algorithm does not yield an exact solution but can produce an approximate solution within a reasonable timeframe. A classic example of a problem with an exact greedy solution is the activity selection problem, where tasks are sorted by end time and the first task beginning after the last selected task is repeatedly chosen. Many foundational algorithms in computer science, including Huffman coding, Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm, incorporate greedy properties. Mathematicians also use greedy strategies in proofs, such as the greedy proof that every tournament contains a Hamiltonian path. A complete characterization of when a problem admits a greedy solution is unknown, as no formal definition exists. However, special cases have been identified: Jack Edmonds showed that greedy algorithms solve linear combinatorial optimization problems with a matroid structure, while Bernhard Korte and László Lovász introduced the broader concept of a greedoid, which allowed a proof of optimality for Prim's algorithm. Algorithms that undo past steps, such as the Gale-Shapley algorithm, are not considered greedy. One technique for proving optimality is an exchange argument, which demonstrates that any solution differing from the greedy solution is at most as good. Further examples include the fractional knapsack problem, the Zeckendorf representation of natural numbers, and greedy routing in networks.
- field
- Computer science, mathematics
- known_for
- Making locally optimal choices at each step without reconsidering past decisions
- related_concepts
- Dynamic programming, matroids, greedoids, exchange argument
Lore & Background
Greedy algorithms are characterized by a decision-making process that, at each step, selects the option that appears best at that moment without revisiting or altering past choices. This local optimization approach is applied to combinatorial optimization problems where the solution depends only on solving a single subproblem at a time, making it a special case of dynamic programming that maintains only one partial solution. The approach requires significant problem structure to succeed; while it often fails to produce an exact solution, it can yield approximate solutions efficiently. A defining feature is that algorithms which undo previous steps, such as the Gale-Shapley algorithm, are not considered greedy. The activity selection problem exemplifies an exact greedy solution: tasks are sorted by end time, and the algorithm repeatedly picks the first task starting after the last selected one ends. In graph theory, Dijkstra's algorithm and A* search are optimal greedy algorithms for shortest paths, with A* requiring an admissible heuristic that never overestimates costs. Kruskal's and Prim's algorithms greedily construct minimum spanning trees, always finding optimal solutions. Greedy methods also appear in signal approximation via matching pursuit, in decision tree learning with algorithms like ID3, and in network routing where messages are forwarded to the geographically closest neighbor. The fractional knapsack problem admits a polynomial-time greedy solution, while the Frobenius coin problem sometimes yields optimal results but not always. Mathematicians use greedy strategies in proofs, such as demonstrating that every tournament contains a Hamiltonian path.
Reader's Guide
Greedy algorithms are significant because they provide efficient solutions to many optimization problems, though they are not always optimal. Their correctness is often proven using an exchange argument, which shows that any solution different from the greedy solution is at most as good. The characterization of when a problem admits a greedy solution is not fully known, but special cases have been identified, such as problems with a matroid structure (Jack Edmonds) or a greedoid structure (Bernhard Korte and László Lovász). Greedy algorithms are also used for approximation, as in the travelling salesman problem, the 0-1 knapsack problem, and submodular maximization. Their legacy includes foundational algorithms in graph theory, network routing, and signal approximation.
Did You Know?
- A greedy algorithm is a special case of a dynamic programming algorithm, according to Uriel Feige.
- The Gale-Shapley algorithm is not greedy because it may modify existing solutions.
- A greedy algorithm finds the optimal solution to Malfatti's problem of finding three disjoint circles within a triangle.
- Fibonacci described a greedy algorithm for computing Egyptian fractions.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record