Greedy Algorithms, A paradigm
So if you are a Dev around knacking your heads on favourite MacOS ❤ or some other platform, you might have applied once The Greedy Approach of solving problems. In this post, I am touching Greedy Algorithms because
Greedy Algorithm is an algorithm paradigm where the choices are made on the basis of the *greed*, yes you heard it right! The greed, the hunger to select the best choice among all the available choices is used for solving the problem. Generally the greedy algorithms are applied to optimisations problem, which follow the properties of
- Optimal Substructure : First time, I read it was like what…wtf! After understanding it says that the problem solving can lead to optimal solution by their optimal solutions of subproblems. In layman words, it says that
the considering the optimal solution of the subproblems will eventually lead you to the optimal solution of the whole problem or the other way round. - Greedy Choice Property : It says that, if you consider the best choice at every stage then it will lead you to the globally optimal solution or the selection of best choices will lead you to the optimal solution and you will never have to reconsider your choices. The greedy choices will never depend on further choices or any of the solutions to the subproblems. The startegy is top down approach here.
The greedy algorithms can be used to solve problems with ease and is the best case to be used when you can’t come up with some other algorithms. They aren’t applicable to all type of problems and can also lead to wrong solutions. The prove of correctness is also tough though!
The greedy algorithms are applicable in problems like Dijkstra’s Shortest Path, Prim’s MST etc.. but they also fail in cases of problems like Travelling Salesman Problem which is NP Hard.
Next Post, coming up with the first problem *The Activity Selection Problem*
