How to know that Greedy approach is wrong in some cases. Is there any general proof to check whether it’s correct or not.How does one know that it’s correct to apply Greedy approach in a given case.For example let us take minimum coins sum problem containing coins : 1,7,10.
So, For 15,Greedy approach gives 10,1,1,1,1,1. But optimal solution gives 7,7,1.Here greedy approach fails.But in some cases greedy approach gives correct result.So how to decide that greedy is good.I know that one answer is defenitely practise,but still are there any methods ?
1 Like
Elements of the greedy strategy
Greedy algorithms should be applied to problems exhibiting these two properties:
greedy choice property: a globally optimal solution can be arrived at by making locally optimal (greedy) choice.
When a locally optimal choice can lead to a globally optimal solution, the problem has this property.
Applied to other problems that don’t have this property, such as the Traveling (now tired) Salesman Problem, greedy algorithms may not find the optimal solution, but might find one that is “good enough” for some applications, especially when the alternative is an exponential-time brute force solution.
optimal substructure: As in dynamic programming. An optimal solution to a problem contains within it an optimal solution to subproblems.
For a problem check for few test cases or for small data sets and check if these two properties apply. If yes, then you r good to go.
Matroids
Furthermore, there’s a powerful mathematical theory that can be in some case used to mechanically prove that a particular problem can be solved with a greedy approach.
Briefly:
One can define a particular combinatoric structure named matroid.
Some smart man proved in the past that these matroids have the Optimal substructure property and the Greedy choice property.
This means that you can run a greedy algorithm on your optimization problem, and it will find the optimal solution. You only need to verify that your problem is defined on a matroid-like structure.
Further information about this can be found here.
Finally Remember : all known greedy coloring algorithms for the graph coloring problem and all other NP-complete problems do not consistently find optimum solutions. Nevertheless, they are useful because they are quick to think up and often give good approximations to the optimum. For more refer to this page here
3 Likes