6
$\begingroup$
  1. I was wondering what kinds of optimization problems can be solved by greedy algorithms accurately?
  2. I don't understand the following quote from Wikipedia:

    Greedy algorithms can be characterized as being 'short sighted', and as 'non-recoverable'. They are ideal only for problems which have 'optimal substructure'.

    If I am correct, an optimization problem with 'optimal substructure' can accurately be solved by dynamic programming method, not always by greedy algorithms. So what does "greedy algorithms are ideal only for problems which have 'optimal substructure'" mean?

Thanks and regards!

  • 3
    Have you seen this before? http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms2011-09-06

1 Answers 1

1

Optimal substructure means that optimising every part of the structure will give an optimal solution for the whole structure.