What is Greedy Algorithms? Basic understanding of Greedy Algorithms.
How To Understand
In the Game of Chess ,everytime we make a decision about a move, we have to think about the future consequences as well.But in the gsme of Tennis or football, our action is based on current situation, which looks great right at the moment,without bothering about the future consequences.
This means in some cases making a decision which looks right at the moment gives the best solution. greedy Technique is best suited for this kind of problems.
How Does It work
Greedy Algorithm works in stages. In each stage,a decision is made that is good at that point,without bothering next consequences.This means some local best is chosen.It assumes local good selection makes global optimal solution.
Elements Of Greedy Algorithm
- Greedy Choice Property
- Optimal Substructure
Greedy Choice Property
This property says globally optimal solutions can be obtained by making a locally optimal solution.The choices made may depend upon earlier choices but not on future.It iteratively makes greedy choices one after another and reduces the problem to a smaller one.
A problem shows optimal substructure if an optimal solution to the problem contains optimal solution to its subproblems.That means we can solve subproblems and build up solution to solve larger problems.
Pros and Cons
It is straightforward, easy to code and easy to understand.Once we make a decision, we don’t have to spend time in re-examining computed values.
Main disadvantage is that for many problems there is no greedy algorithms.In many cases there is no guarantee that making locally optimal improvements in a locally optimal solution gives the optimal global solution.