Greedy Algorithm

What is Greedy Algorithm?

-which makes local optimal choice at each step with the hope of finding global optimal solution.

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.

Greedy algorithms do not always yield optimal solutions, but for many problems

they do.

For Example, Counting Coins:

This problem is to count to a desired value by choosing the least possible coins and the greedy approach forces the algorithm to pick the largest possible coin. 

If we are provided coins of ₹1, 2, 5 and 10 and we are asked to count ₹18 then the greedy procedure will be −

• 1 − Select one ₹ 10 coin, the remaining count is 8
• 2 − Then select one ₹ 5 coin, the remaining count is 3
• 3 − Then select one ₹ 2 coin, the remaining count is 1
• 4 − And finally, the selection of one ₹ 1 coins solves the problem

Though, it seems to be working fine, for this count we need to pick only 4 coins. But if we slightly change the problem then the same approach may not be able to produce the same optimum result.

For the currency system, where we have coins of 1, 7, 10 value, counting coins for value 18 will be absolutely optimum but for count like 15, it may use more coins than necessary. For example, the greedy approach will use 10 + 1 + 1 + 1 + 1 + 1, total 6 coins. Whereas the same problem could be solved by using only 3 coins (7 + 7 + 1).

Subsequently, we may reason that the eager approach picks a prompt improved arrangement and may come up short where global optimisation is a major concern.

Reaching the largest-sum (Source:Wikipedia)

Examples

Most networking algorithms use the greedy approach. Here is a list of few of them −

• Travelling Salesman Problem

• Prim's Minimal Spanning Tree Algorithm

• Kruskal's Minimal Spanning Tree Algorithm

• Dijkstra's Minimal Spanning Tree Algorithm

• Graph - Map Coloring

• Graph - Vertex Cover

• Knapsack Problem

• Job Scheduling Problem

Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work will have two properties:

Greedy choice property

We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution.

After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.

Optimal substructure 

"A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."

Components of Greedy Algorithm

Greedy algorithms have the following five components −

A candidate set − A solution is created from this set.
A selection function − Used to choose the best candidate to be added to the solution.
A feasibility function − Used to determine whether a candidate can be used to contribute to the solution.
An objective function − Used to assign a value to a solution or a partial solution.
A solution function − Used to indicate whether a complete solution has been reached.

Areas of Application

Greedy approach is used to solve many problems, such as

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

Where Greedy Approach Fails

In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this approach.

Source:Tutorialspoint & Wikipedia