💰💰 Greedy algorithms

Greedy is an algorithmic paradigm where the solution is built piece by piece. The next piece that offers the most obvious and immediate benefit is chosen. The greedy approach always makes the choice that maximizes the profit and minimizes the cost at any given point. It means that a locally-optimal choice is made in the hope that it leads to a globally optimal solution.

A real life example

For example:

You just got a new piggy bank to have some savings for your college admission. The bank is small, and can only contain a fixed weight. Therefore, you have to be smart and choose the maximum value vs weight ratio for adding anything into it. You have a fixed number of coins and have to pick them one at a time until the capacity of the bank is reached.

This is also called the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to an optimal global solution because we are allowed to take fractions of an item.

💡 How to make the optimal choice?
The greedy algorithm only has one shot to compute the optimal solution. It can never go back and reverse the decision. Hence, the algorithm makes greedy choices at each step to ensure that the objective function is $optimized$.

Shortest path finding problem

In order to understand the un-optimized solution issue, consider the following shortest path finding problem.

Look at the figure above. You have to travel the minimum distance from the starting point $Venice(S)$ to the ending point $Rome(E)$.

You are given the distance values respective to each path. Your goal is to minimize this (distance) value from $S -> E$

Following the greedy approach, you first pick the minimum choice available at the starting point. So, the path would look like:

$Venice -> Cinque\ Terre\ NP Cost = 10$ ...