Overview
Greedy algorithms aim to solve optimization problems. They make the locally optimal choice in hope that it will lead to the globally optimal solution. They are a subset of Dynamic Programming.
Note
Greedy algorithms will usually find an optimal solution but not always the optimal solution.
Optimization problems must have two key elements for an optimal greedy algorithm to apply.
- Greedy-choice property
- Optimal substructure
Greedy-choice property: a globally optimal solution contains a locally optimal (greedy) choice.
Optimal substructure: a globally optimal solution contains the optimal solution to a subproblem.
Generally greedy algorithms can be designed using the following steps.
- Cast the optimization problem
- Prove greedy-choice property
- Prove optimal substructure
Reference
- Sun, Hongyang Greedy algorithims The University of Kansas 2024