Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question
3  
Have you seen this before? en.wikipedia.org/wiki/Matroid#Greedy_algorithms –  Srivatsan Sep 6 '11 at 4:56
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.