Greedy Technique uses iterative/recursive approach to solve an optimization problem and selects an optimal(best) solution. Greedy approach look for simple, easytoimplement solutions to complex, multi step problems by deciding which next step will provide the most benefit. It is not always the greedy technique produce an optimal solution, but it helps in producing an approximate optimal solution in a reasonable time. Greedy generally works on heuristic approach. The greedy technique is one of the simplest approaches to solve the optimization problems in which we want to determine the local optimum of a given function by a sequence of steps where at each stage we can make a choice among a class of possible decisions. In this, the choice of the optimal decision is made in the information at hand without worrying about the effect these decisions may have in the future. The greedy choice property and optimal subproblem are two ingredients in the problem that lend to a greedy strategy. It says that a globally optimal solution can be arrived at by making a locally optimal choice(with no Guarantee). OR we can say greedy method arrives at a solution by making a sequence of choices, each of which simply looks the best at moment. Greedy Choice Property: It says, we can assemble a globally optimal solution by making locally optimal choices i.e. The greedy choice is always part of certain optimal solution. Optimal SubProblem:
It says, an optimal solution to the problem contains within its optimal
solution to subproblems i.e. Global optimal solution is constructed
from local optimal solutions.
Any Greedy Algorithm will have following five components:
