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.
-
2Wikipedia 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– walpen2017年02月19日 22:19:35 +00:00Commented Feb 19, 2017 at 22:19
-
1This question (and walpen's comment-answer) feel like they would be a better fit for Computer Science rather than here.Philip Kendall– Philip Kendall2017年02月19日 22:35:43 +00:00Commented Feb 19, 2017 at 22:35
1 Answer 1
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.