Saturday, February 16, 2013

Confudes by Dynamic Programming and Greedy Algorithms? See here!

Do dynamic programming and greedy algorithms solve the same type of problems?



I wonder if dynamic programming and greedy algorithms solve the same type of problems, either accurately or approximately? Specifically,
  1. As far as I know, the type of problems that dynamic programming can solve are those that have "optimal structure". Can the same type of problems always be solved by greedy algorithms, either accurately or approximately? (I think yes)
  2. Are there optimal problems that do not have "optimal structure" and can be solved by greedy algorithms, either accurately or approximately? If yes, what characterize the type of problems that can be solved by greedy algorithms, either accurately or approximately?
More Details ...

No comments:

Post a Comment