• 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.

Problems

Algorithms

  • Minimum-spanning-ree algorithms
  • Dijkstra’s algorhtm
  • Chavatal’s greed set-covering heuristic