What is a greedy algorithm?

Overview

A greedy algorithm is an approach used to solve a problem by building an optimal solution. It chooses the optimal local solution hoping to make globally optimal results. The selection of locally available options may not lead to an optimal global solution. It uses a top-down approach to make decisions, which means earlier decisions can't be reconsidered.

Note: An algorithm is a set of finite instructions to perform any task. Want to know more about algorithms? Click here

Create a greedy algorithm

• Find the subproblem of a given problem.
• Determine the required solution—the shortest path.
• Create an iterative base case that leads to the goal.

Working

Here's the animation of how the greedy approach works and makes decisions based on currently available resources.

When to use a greedy algorithm

Following are some cases where we can use a greedy algorithm:

• The locally selected optimal solutions can build a global solution without changing earlier decisions.
• The problem can be divided easily into sub-problems.

Applications

• Prim's minimum spanning tree
• Huffman coding
• Knapsack problem
• Job scheduling problem
• Map coloring- graph
• Traveling salesman problem and many others!

Limitations

• Sometimes it may get stuck in the loop because it doesn't know about the next greedy choice.
• It is unable to solve graphs with negative edges.
• It's hard to prove why it is correct, so accuracy is unknown.
• The locally optimal solutions may build a non-optimal global solution.