GREEDY ALGORITHM

5 min readMar 19, 2021

The Greedy algorithm can be used for maximization on ‘independent systems’. We always tend to choose the element which seems to occur best at the moment (from all the admissible elements, we choose the element whose weight is maximal) and add it to the solution we are constructing (this explains the name given — GREEDY !).

Therefore, greedy algorithm is an algorithmic paradigm which is based on heuristic that follows local optimal choice at every step taken with the hope of finding the globally optimal solution.

Example — Greedy Approach

Problem statement: To make an amount of change using the smallest possible number of coins.
The given amount: $28Given available coins:
  $1 coin
  $2 coin
  $5 coin

Step-wise Solution Generated :

Create an empty solution-set = { },
coins = {1, 2, 5}
sum_of_coins = 0
While the sum_of_coins ≠ 28, perform the following steps.

Select a coin m from coins such that sum_of_coins + m< 28
If m+ sum_of_coins > 28, return no solution.
Else, return sum_of_coins = sum_of_coins + m.
Add m to solution-set.

Up to the first 5 iterations, the solution- set created will contain five $5 coins. After which, we get one $2 coin and finally, a single $1 coin.

WHERE TO USE GREEDY ALGORITHMS?

It must fulfill the following two properties in order to perform the greedy technique on an algorithm —

OPTIMAL SUBSTRUCTURE → In case the optimal solutions of the sub-problems lead to the optimal solution of the problem, then the problem is considered to exhibit the optimal substructure property.

# If the best way to change $34 is {25, 5, 1, 1, 1, 1} then the best way to change $29 is {25, 1, 1, 1, 1}.

GREEDY CHOICE PROPERTY (hard to prove its correctness!)→ Globally optimal solution can be arrived at by making locally optimal (greedy) choice.

# At each step, choose the most “promising” candidate, without worrying whether it would prove to be a sound decision in the long run.

EXAMPLES OF GREEDY ALGORITHMS

The greedy approach is used by most of the networking algorithms. Here is a list of few examples :

Prim’s Minimal Spanning Tree Algorithm
Travelling Salesman Problem
Graph — Map Coloring
Kruskal’s Minimal Spanning Tree Algorithm
Dijkstra’s Minimal Spanning Tree Algorithm
Graph — Vertex Cover

APPLICATIONS OF GREEDY APPROACH

Job sequenced with deadline
Knapsack Problem
Huffman Coding
Minimum Cost Spanning Tree
Bellman Ford
Breadth First Traversal (BFT)
Optimal Merge Pattern

GREEDY TECHNIQUE

Constructs a solution to an optimization problem piece by piece anyhow through a sequence of choices which are as follows:

=> Feasible : satisfying the prob. constraints
=> Locally Optimal : the best local choice
=> Irrevocable: cannot be changes on subsequent steps once made

For few problems, it yields an optimal solution for every instance. However, for most, it does not but can prove to be useful for fast approximations.

BASIC CHARACTERISTICS

**The example shown above, is an activity scheduling problem, the resource costs are in hours, and the activities that are required to be performed in serial order.**

~ Solution is built in small steps

~ Decisions on how to create the solution to the problem are made to maximize some criterion without looking to the future

~ Demands the “best” current partial solution as if the current step were the last step

KNAPSACK PROBLEM

Principal : Knapsack is a bag of fixed capacity

In this problem it is assumed that “n” with profit value and weight are given.

The main objective is to choose the objects and place them in a knapsack such that the object which is placed in the bag generates maximum profit possible.

TWO TYPES OF KNAPSACK PROBLEMS :

Fractional Knapsack Problem

thief can take partial items
for instance, items are liquids or powders
solvable with a greedy algorithm

0/1 Knapsack Problem

the items cannot be divided
thief must take the entire item or leave it behind

The Fractional Knapsack Problem can be solved using Greedy Technique, where as the 0/1 Knapsack problem does not provide any greedy solution.

ADVANTAGES OF GREEDY ALGORITHM

They are easier to implement
They require much less computing resources
Much faster to execute
Used to solve optimization problems

DISADVANTAGES OF GREEDY ALGORITHM

The only disadvantage is that they not always reach the global optimum solution
While even when the global optimum solution is not reached, most of the times the reached sub-optimal solution is a very good solution

In the above greedy scan displayed as a tree (higher value higher greed), an algorithm state at value — 40 is likely to take 29 as its next value. Furthermore, its quest ends at 12. This amounts to value- 41.

However, if this particular algorithm took a sub optimal direction or adopted a conquering strategy, then 25 would be followed by value 40, and the overall cost improvement would be : 65, which is finally valued 24 points higher as a sub-optimal decision.

AREAS OF APPLICATION

The greedy approach is used to solve a number of problems, such as

Locating the shortest distance between two vertices using Dijkstra’s algorithm.
Locating the minimal spanning tree in the graph using Prim’s /Kruskal’s algorithm, etc.

COMPONENTS OF GREEDY ALGORITHM

The five components of the Greedy Algorithm are as follows−

Candidate set − A solution is built from this set
Selection function − Used to select the best candidate which is to be added to the solution
Feasibility function − Used to determine whether the candidate can be used to contribute to the solution created
Objective function − Used to assign value to the partial solution or the solution
Solution function − Used to indicate whether a complete solution has been reached or not

CONCLUSION

Greedy Algorithms are simple, straightforward and shortsighted in their approach. A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that the solutions to sub-problems do not have to be known at each stage.