- For many optimization problems, dynamic programming to determine the best choice is overkill; simpler more efficient algorithms will do.
- A greedy algorithm always makes the choice that looks best at the moment
- It makes a locally optimal choice in hope that this choice will lead to globally optimal solution.
- Greedy algorithms don’t always yield optimal solution, but for many problems they do.
- Dynamic programming solutions analyze all possible sub-solutions, determining which is optimal. However, when we make one choice, the greedy choice, one one subproblem remains.
- Minimum-spanning-ree algorithms
- Dijkstra’s algorhtm
- Chavatal’s greed set-covering heuristic