General method

The greedy method is a design technique applicable to problems that have n inputs and need to obtain a subset that satisfies some constraints.

• Any subset that satisfies these constraints is called a feasible solution.
• A feasible solution that either maximizes or minimizes the given objective function is called an optimal solution.

Methods

1. Subset paradigm

• Algorithms work in stages, considering one input at a time.
• At each stage, a decision is made regarding whether a particular input is in an optimal solution.
• Inputs are considered in the order determined by some selection procedure, where the selection procedure is an optimization measure.
• If the inclusion of the next input into the partially constructed optimal solution will result in an infeasible solution, then this input is not added to the partial solution. Otherwise it is added.
• The selection procedure's optimization measure is mostly the objective function.

This version of the greedy technique is called the subset paradigm.

Examples: the knapsack problem, job sequencing with deadlines, and minimum-cost spanning trees fit in the subset paradigm.

Greedy method control abstraction for the subset paradigm

Algorithm Greedy(a, n)
// a[1:n] contains the n inputs.
{
    soln := ∅;                  // Initialize the solution
    for i := 1 to n do
    {
        x := Select(a);
        if Feasible(soln, x) then
            soln := Union(soln, x);
    }
    return soln;
}

• Select() selects an input from a[ ] and removes it. The selected input value is assigned to x.
• Feasible() is a Boolean-valued function that determines whether x can be included into the solution vector.
• Union() combines x with the solution and updates the objective function.

2. Ordering paradigm

Problems that do not call for the selection of an optimal subset 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.

This version of the greedy method is called the ordering paradigm.

Example: the single source shortest path problem.

Example 1: Change making

The change to be returned is $500-232=268$ rupees.

In each stage, a note or coin is added to the change. This note or coin is selected using the greedy criterion: at each stage, increase the total amount of change constructed by as much as possible. The selected one should not cause the total amount of change given so far to exceed the final desired amount.

The handwritten list stops after the ₹2 coin, but its total of ₹268 needs the final ₹1 coin, so it is added as the sixth stage.

Advantages of Greedy Method

• Greedy methods are simple to understand and implement.
• They are faster.
• There are many problems where an optimal solution is sought using greedy technique.

Disadvatage of Greedy Method

• They may not always produce the optimum solution.
• The correctness of the algorithm is very hard to prove.
• This approach can be disastous for some computational task.

Applications of Greedy Method

1. Knaspsack problem.
2. Job sequencing with deadlines
3. Minimum -cost spanning trees
4. Single-source shortest path