Greedy Technique

Post date: Nov 15, 2013 5:18:53 AM

< Previous-Divide and Conquer Technique Next - Dynamic Programming Technique>

Greedy Technique uses iterative/recursive approach to solve an optimization problem and selects an optimal(best) solution. Greedy approach look for simple, easy-to-implement 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 sub-problem 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 Sub-Problem: It says, an optimal solution to the problem contains within its optimal solution to sub-problems i.e. Global optimal solution is constructed from local optimal solutions.

In optimization problems, there are two types of solutions:

• Feasible Solutions : these are not a clear optimal solution, but are close to optimal solution( can be said as approximate solution)
• Optimal Solutions : these are fully acceptable optimized solution for the current optimization problem.

Any Greedy Algorithm will have following five components:

1. Candidate Set: From which a solution is created.
2. Selection Function: Chooses the best candidate to be added to the solution.
3. Feasibility Function: Used to determine, if a candidate can be used to contribute to a solution.
4. Objective Function: Assigns a value to a solution or a partial solution
5. Solution Function: Indicates when we have discovered a complete solution.

Greedy algorithms are easy to invent, implement and most of time they are efficient. However there are may problems that cannot be solved correctly by this approach and in many cases there is no guarantee that making locally optimal improvements in a locally optimal solution with produce the optimal global solution.

Following are few algorithms that make use of greedy approach/technique:

• Knapsack problem.
• Kruskal's Algorithm.
• Prim's Algorithm.
• Dijkstra's Algorithm.
• Huffman tree building.
• Traveling salesman problem. etc.

< Previous-Divide and Conquer Technique Next - Dynamic Programming Technique>