Learning materials
Greedy Algorithms
On this page
A greedy algorithm is a simple, intuitive algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hopes of finding the global optimum.
Characteristics
- Heuristic
- Local optimum
- Intuitive
- No long term planning
- Exact when the greedy-choice property is justified; otherwise it may be approximate and may not find the best solution
- Often efficient, but runtime depends on the problem and implementation
Relationships with other paradigms
Greedy algorithms and backtracking are both decision-making paradigms in algorithm design, distinguished by their approach to finding solutions.
| Greedy | Backtracking |
|---|---|
| Exact when justified; otherwise may be approximate | Exact for the feasibility search when the pruning test is sound |
| Make a decision | Make a decision |
| Never look back | Look back |
| No long term planning | Long term planning |
| Often efficient; no universal runtime ranking | May explore many candidates; pruning can reduce the search |
| May fail to find the best solution | Can find one or all feasible solutions; it finds the best only when configured to retain and compare candidates |
Application Domain
Solve Optimization (find best) problems. Many combinatorial optimization problems can be solved by a greedy algorithm.
- Graph problems
- Shortest path: Dijkstra’s algorithm
- Minimum spanning tree: Prim’s algorithm, Kruskal’s algorithm
- Graph coloring
- Bin packing problem
- Activity selection problem
- Fractional knapsack problem
- Huffman coding