The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure

Posted on by

The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure

 

[What is the Greedy Algorithm?]

The Greedy algorithm is not necessarily one algorithm, but rather any algorithm that is used to get an Optimal Solution by taking the next most obvious and immediate benefit. It can also be described by saying that it takes the most optimal solution at every stage. This is its strength that can sometimes become its weakness.

 

[Application / Examples]

The Greedy Algorithm has many applications, mostly in computations that have optimization problems, and thus need optimal solutions, for instance;

1. Huffman Coding
2. Minimum Spanning Tree Problems in a Graph (Prim’s, Kruskal’s & Dijkstra’s Algorithms)
3. Knapsack Problem
4. Travelling Salesman Problem
5. Counting Coins Problem

 

[Optimal Solutions with the Greedy Algorithm]

Counting Coins Problem

To demonstrate the use of a Greedy algorithm, take a Counting Coins Problem where;

– there are denominations of currency coins as 7, 6, and 1 cents
– we need to count the number of coins that add-up to a certain value with the least possible coins

 

Optimal Solution::

With coins of 7, 6, and 1 cents, the greedy algorithm works by breaking (minus-ing) the largest required cents, 7 cents, then 6 cents and finally 1 cent, from “N” cents.

For instance, When N is given as 21 (N = 21), the algorithm takes the most beneficial option, 7 cents and subtracts it from 21. It does that two more times, breaking the 21 cents in only 3 steps, which is the optimal solution;

N = 21 cents 
Options = 7 cents, 6 cents, 1 cent

21 - (7) = 14
14 - (7) = 7
7 - (7) = 0

Total steps = 3

 

[Unique Worst Possible Solution / Cases of Failure of the Greedy algorithm]

The greedy algorithm does not always give the optimal solution. Its strength can sometimes become its weakness. We can say that the algorithm works perfectly when all conditions for perfect computations are present, else it can be the worst algorithm for an optimal solution or rather can produce Unique Worst Possible Solutions. To demonstrate Cases of Failure, the Counting Coins Problem is again used!

Counting Coins Problem

[Case 1]

Unique Worst Possible Solution::

When N = 18 cents, the solution is not optimal. The total steps taken to break N (using the 7 cents and 1 cent option), are more than what is actually necessary;

N = 18 cents 
Options = 7 cents, 6 cents, 1 cent

18 - (7) = 9
9 - (7) = 2
2 - (1) = 1
1 - (1) = 1

Total steps = 4

 

Optimal Solution::

The optimal solution here however, is using the 6 cents option to break N, 18 cents;

N = 18 cents 
Options = 7 cents, 6 cents, 1 cent

18 - (6) = 12
12 - (6) = 6
6 - (6) = 0

Total steps = 3

 

[Case 2]

Unique Worst Possible Solution::

When N = 12 cents, the solution (number of steps) is by far NOT optimal. The total steps taken to break N (using the 7 cents and one cent option), are 6 steps;

N = 12 cents 
Options = 7 cents, 6 cents, 1 cent

12 - (7) = 5
5 - (1) = 4
4 - (1) = 3
3 - (1) = 2
2 - (1) = 1
1 - (1) = 0

Total steps = 6

 

Optimal Solution::

The optimal solution however, is using the 6 cents option to break N, 12 cents, which results in a cost of only 2 (steps);

N = 12 cents 
Options = 7 cents, 6 cents, 1 cent

12 - (6) = 6
6 - (6) = 0

Total steps = 2

 

In this last case [Case 2], the difference between the optimal solution and the Greedy Algorithm solution is “4” steps. This amounts to wastage of computational reseources/power.

 

The Greedy Algorithm, its Applications, Optimal Solutions & Cases of Failure
Data Structures and Algorithms | thetqweb