Greedy algorithms

What is Greedy algorithm ?

Greedy algorithms always find for optimal solution of a problem by following greedy approach. This solution may require minimum or maximum result. There will be some feasible solutions for the problem and this algorithm will find the optimal one.

Let’s see an example to understand the approach.

Suppose, I want to place Y from X (P:X → Y). There might be several ways to reach the destination.

Possible solutions:

• S1: Go by feet (walking)

• S2: Go by bus

• S3: Go by train

• S4: Go by flight

….

….

• Sn: There may be n solutions

There is constraint for the problem. We have to reach the destination within 8 hours . Now , we need to find feasible solutions and an optimal solution for the problem.

What is feasible solution ?

Any subset of the solutions for a problem that satisfies the constraints of the problem.Solution S3: Go by train and S4: Go by flight can satisfy the condition. We can call S3 and S4 are the feasible solution for the problem. So, subset of feasible solution is {S3,S4}

What is optimal solution ?

Suppose, need to go to the destination with minimum cost. We can go to destination B at the minimum cost if we use train . So solution S4 is the optimal solution.Feasible solution can be found for either minimum value or maximum value. A feasible solution that minimizes or maximizes given objective function is known as optimal solution.

However we can write general form of the algorithm like the following.

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