Greedy Algorithm
A greedy algorithm makes the locally optimal choice at each step without backtracking; it is simple and efficient but does not guarantee a global optimum.
Purpose
To solve optimization problems quickly and approximately, requiring proof of the greedy-choice property.
Mechanism
Each step takes the local optimum in expectation of a global one. Applicability requires the greedy-choice property (a local optimum extends to a global one) plus optimal substructure. Classics: Huffman coding, Dijkstra, Kruskal, fractional knapsack.
Use cases
- Algorithm design
- Approximate optimization
- Scheduling problems