Greedy Algorithms: A Deep Dive

Greedy algorithms

Greedy is an algorithmic paradigm in which the solution is built piece by piece. The next piece that offers the most obvious and immediate benefit is chosen. The greedy approach will always make the choice that will maximize the profit and minimize the cost at any given point. It means that a locally optimal choice is made in the hope that it will lead to a globally optimal solution.

A real life example

Suppose you just got a new piggy bank to save some money for your college admission. The bank is small and can only contain a fixed weight. Each item can only be added once. You’ve got to be smart and choose the maximum value vs. weight ratio for putting anything into it.

This is also called the fractional knapsack problem. The local optimal strategy is to choose the item with the maximum value vs. weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item.

How to make the optimal choice?

The greedy algorithm has only one shot at computing the optimal solution. It can never reverse the decision. Therefore, the algorithm makes greedy choices at each step to ensure that the objective function is optimized.

The shortest path problem

In order to understand the unoptimized solution issue, consider the following shortest path problem:

Look at the figure above, where we have to travel the minimum distance from the starting point ...