Introduction to Greedy Algorithms

Greedy Algorithm

As the name suggests, a Greedy Algorithm always makes the choice that seems to be the best at that moment. This means that it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

How to decide which choice is optimal?

This algorithmic designing technique is mainly used to solve optimization problems. In these problems, usually, we have an objective function that needs to be optimized (maximized or minimized) at a given point. A Greedy Algorithm makes greedy choices at each step to ensure that the objective function is optimized. The Greedy Algorithm has only one shot to compute the optimal solution; it never goes back and reverses the decision.

Components of the Greedy Algorithm

Greedy Algorithms have the following five components:

• Candidate set: A solution is created from this set.
• Selection function: Used to choose the best candidate to be added to the solution
• Feasibility function: Used to determine whether a candidate can be used to contribute to the solution
• Objective function: Used to assign a value to a solution or a partial solution
• Solution function: Used to indicate whether a complete solution has been reached

Major areas in which the Greedy approach works

Greedy algorithms are used to solve many problems, such as:

• Finding the shortest path between two vertices using Dijkstra’s algorithm (refer to the Graphs chapter)
• Finding the minimal spanning tree in a graph using Prim’s/Kruskal’s algorithm (refer to the Graphs chapter)
• Optimization problems

Where does a Greedy approach fail?

In many problems, the Greedy algorithm fails to find an optimal solution. It may instead produce a worse solution. In the Dynamic Programming chapter, we will discuss that the problem that looks like it could have been solved using the Greedy approach doesn’t give us the optimal solution.