Greedy Approach: A Deep Dive
In this lesson, we will learn what greedy algorithms are and when to use them.
💰💰 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
Imagine 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 that has 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 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 .
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, where you have to travel the minimum distance from the starting point to the ending point
You are given the distance values respective to each path. Your goal is to minimize this (distance) value from .
Following the greedy approach, you will first pick the minimum choice available at the starting point. So, the path would look like:
...