0

Is there any generalized rule to decide if applying greedy algorithm on a problem will yield optimal solution or not? For example - some of the popular algorithm problems like the ‘Coin Change’ problem and the 'Traveling Salesman' problem can not be solved optimally from greedy approach.

  • 2
    Wikipedia is your friend: From Greedy algorithm: > They [greedy algorithms] are ideal only for problems which have 'optimal substructure'. From optimal substructure: > [A] problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.... . – walpen Feb 19 '17 at 22:19
  • 1
    This question (and walpen's comment-answer) feel like they would be a better fit for Computer Science rather than here. – Philip Kendall Feb 19 '17 at 22:35
5

Greedy algorithms do not find optimal solutions for any nontrivial optimization problem. That is the reason why optimization is a whole field of scientific research and there are tons of different optimization algorithms for different categories of problems.

Moreover, "greedy algorithms" is only a category of optimization algorithms, for a given problem, there can be lots of different greedy algorithms, so it does not make much sense to ask "if applying greedy algorithm on a problem will yield optimal solution". What makes sense could be to ask "if applying a specific greedy algorithm" will always yield to an optimal solution, or to ask if for a given problem an "optimal" greedy algorithm exists (or not). Typically, there is no "optimal" greedy algorithm when a given optimization problem has local maxima which are not the global maximum, because a greedy algorithm will get stuck when it reaches such a local maximum.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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