Greedy Algorithm – What Every one Has to Say?

What is Greedy Algorithm?

Greedy Algorithm is optimization method. When the problem has many feasible solutions with different cost or benefit, finding the best solution is known as an optimization problem and the best solution is known as the optimal solution.

There are numerous optimization problems in the real world, such as make a change, knapsack, shortest path, job sequencing, and so on. Greedy algorithms, like dynamic programming and many other techniques, are used to tackle optimization problems. The simplicity of greedy algorithms is their beauty. They are simple to comprehend and construct. Among all optimization techniques, greedy algorithms are maybe the simplest type of algorithm.

The greedy algorithm derives the solution step by step, by looking at the information available at the current moment. It does not look at future prospects. Decisions are completely locally optimal. This method constructs the solution simply by looking at current benefit without exploring future possibilities and hence they are known as greedy. The choice made under greedy solution procedure are irrevocable, means once we have selected the local best solution, it cannot be backtracked. Thus, a choice made at each step in the greedy method should be:

• Feasible : choice should satisfy problem constraints.
• Locally optimal : Best solution from all feasible solution at the current stage should be selected.
• Irrevocable : Once the choice is made, it cannot be altered, i.e. if a feasible solution is selected (rejected) in step i, it cannot be rejected (selected) in subsequent stages.

Greedy algorithms are based on five pillars:

• Candidate set : It is a pool of choices from which selection is made and the solution is constructed. An example includes a set of nodes, vertex, items, denominations etc.
• Selection function : This function chooses the best local optimal solution based on some heuristic, depending on a maximization or minimization problem.
• Feasibility function : Candidate selected by selection function from candidate set is tested against feasibility function. Feasibility function tells us whether to add or not a particular candidate in the solution set.
• Objective function : Objective function assigns benefit or cost to a partial solution. It decides whether a problem can be solved by maximizing cost/profit or by minimizing it. Certain problems are maximization problem whereas certain are minimization problems. The knapsack is a maximization problem, make a change is minimization problem.
• Solution function : It indicates whether a complete solution is found or not. If a complete solution is built then stop, otherwise continue selecting next candidates from candidate set until a solution is found or candidate set is exhausted.

Control Abstraction for Greedy Algorithm

By examining the information available at the time, the greedy algorithm generates the answer step by step. It does not consider the future. Locally optimal decisions are made. The decisions made under the greedy solution approach are irreversible, which implies that after we’ve chosen the local best solution, we can’t go back.
The greedy approach’s control abstraction is as follows:

Algorithm GREEDY_APPROACH(L, n)
// Description : Solve the given problem using a greedy approach
// Input : 
L : List of possible choices, 
n: the size of the solution 
// Output : Set Solution containing the solution of the given problem

Solution ← ∅
for i ← 1 to n do
    Choice ← Select(L)
    if (feasible(Choice ∪ Solution)) then
        Solution ← Choice ∪ Solution
    end
end
return Solution

The greedy technique does not guarantee the best solution, but it does provide a good estimate in most circumstances. For some situations (such as Prim’s and Kruskal’s algorithms), greedy always produces the best answer. If greedy gives the best solution, it is the finest technique among all others.

Characteristics of Greedy Algorithm

Problems which can be solved using the greedy method generally possess the following two interesting properties:

Greedy choice property:

The global optimal solution is found by selecting locally optimal choices, or the ones that appear to be the best at the time. If the choice is feasible, include it in the solution set and reduce the problem by the same amount. The current decision may be influenced by prior decisions, but it is independent by future decisions.

Optimal substructure:

We say given problem exhibits optimal substructure if the optimal solution to the given problem contains the optimal solution to its subproblems too. In the problem which possesses the optimal substructure, best next choice always leads to an optimal solution.

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Click to read