Greedy Algorithm

Greedy Algorithm

Greedy is an algorithmic paradigm that builds up a solution piece by piece. Always choosing the next piece that offers the most obvious and immediate benefit. The Greedy method is perhaps the most straight forward design technique. This method suggests that one can devise an algorithm that works in stages considering one output at a time.
 At each stage, a decision is made regarding whether a particular input is in optimal solution. This is done by considering the inputs in an order determined by some selection procedure. If the inclusion of the next input into the partially constructed optimal solution will result in an infeasible solution. Then this input isn’t added to the partial solution, otherwise its added. The selection procedure itself is based on some optimization measure. This measure may be the objective function. In fact, several different optimization measures may be plausible for a given problem.

 Subset paradigm:

The sub set paradigm is abstractly described below:

Algorithm Greedy(a,n)

// a[1:n] contains n inputs

{

            solution=Θ; // Initialize the solution.

            for i=1 to n do

            {

                        x=select(a);

                        if Feasible(solution , x) then

                                    solution=Union(solution , x)

            }

            return solution;

            }

The function ‘Select’ selects an input from a [ ] and removes it. The selected input's value is assigned to x. Feasible is a Boolean valued function that determines whether x can be included into the solution vector. The function Union combines x with the solution and updates the objective function. The function' Greedy' describes the essential way that a greedy algorithm will look. Once a particular problem is chosen the functions 'Select', ‘Feasible’, ‘Union’, are properly implemented.

Ordering paradigm:

For problems that do not call for the selection of an optimal subset, in the greedy method we make decisions by considering the inputs in some order. Each decision is made using an optimization criterion that can be computed using decisions already made. Call this version of the greedy method the ‘Ordering paradigm’.

Components of Greedy Algorithm:

Greedy algorithms have following 5 components.

•    A candidate set: A solution is created from this set.
• A selection function: used to choose the best candidate to be added to the solution.
•   A feasibility function: Used to determine whether a candidate can be used to contribute to the solution.
•    An objective Function: Used to assign a value to a solution or a partial solution.
•    A solution function: Used to indicate whether a complete solution has been reached.

Disadvantages of Greedy algorithm:

In many Problems though greedy algorithm gives an approximate solution in reasonable time but it fails to find an optimal solution, moreover it may produce a worst solution.