Greedy algorithms is a paradigm that describes the approach on how you can go about solving a problem. You might have heard about a lot of algorithmic techniques while learning how to solve problems in computer science. The others being:
In this post we shall understand what a greedy algorithm is and how can it be used to solve problems which don’t seem very trivial at the first glance.
What is a Greedy Algorithm?
What is the first thing that comes to your mind when you think about greed? In the English language it usually means wanting the best for oneself. We use this technique everywhere around us. For instance, while shopping, we try to go at stores with the maximum discount, while choosing an internet plan, we want the maximum speed at our price range and so on.
But these are very small problems that require only one step of action. What you basically doing is “making the choice that seems best at that point of time”. If you are trying to rent a house, with a greedy approach you would try to get the house which offers you the best deal in the minimum price. After that, the house you selected may or may not be the best one in terms of commute or facilities, but with a greedy approach you hope that it would be the best one.
An example from day to day life:
One might encounter problems that require you to choose a series of steps. Let us take up a more relatable example. Suppose you are a workaholic student, who wants to take the maximum number of lessons.
Let’s assume that you after your daily chores you have 10 hours remaining in a day to take up these lessons. How do you go about choosing the tasks?
Solution:
Be greedy. A natural thought comes to your mind, “If I want to do maximum lessons, I should take up lessons that take minimum amount of time.” This defines our condition for a greedy algorithm and we hope that it will let us choose the maximum number of tasks. Hence at every step, we will try to choose the task that takes up the minimum time. Going by this approach let’s choose:
- Physics lesson (1 hour)
- Lessons: 1
- Total time: 1 hour
- Chemistry class (2 hours)
- Lessons: 2
- Total time: 1 + 2 = 3 hours
- Tennis lesson (3 hours)
- Lessons: 3
- Total time: 3 + 3 = 6 hours
- Cooking class (4 hours)
- Lessons: 4
- Total time: 6 + 4 = 10 hours
So with a greedy approach we were able to take a total of 4 lessons in a total of 10 hours. This is indeed the maximum number of tasks that we could have completed. What would happen if we chose some other strategy. Like choosing the task with maximum time or a mean time?
- Cricket coaching (5 hours)
- Lessons: 1
- Total time: 5 hours
- Tennis lesson (3 hours)
- Lessons: 2
- Total time: 5 + 3 = 8 hours
- Chemistry class (2 hours)
- Lessons: 3
- Total time: 8 + 2 = 10 hours
We were only able to complete 3 tasks with this approach. Hence for the given problem statement, a greedy approach would certainly give you the most-optimal solution.
Steps involved in a Greedy Algorithm
Based on the above example we can define the steps in a greedy algorithm.
- To begin, our solution is an empty set.
- At each step, add an item into the solution set.
- If the solution is feasible, keep the item in the current set.
- Reject the item, and never consider it again.
When does this algorithm fail?
Suppose you want to go on a hike. Ideally, to reach the topmost point, you would want to take the shortest path. This is where the greedy algorithm would fail. Choosing a shortest path during a hike would mean that we go straight towards the destination. This may not at all be feasible path and you may actually spend more time to overcome the hurdles.
An optimal path may be a little twisted and longer, but it may take up less time as it was easy to complete. That is why people go on hikes and then map the path they found 🤔.
Conclusion:
There are 3 major takeaways about greedy algorithms:
- It is very likely that a greedy algorithm may not give the best solution, and there could be a hidden best solution. This is because once you make a choice you never backtrack it. But still, this algorithm paradigm is very important as the approach is very easy to describe and it may perform better than other algorithms.
- Analyzing the run time of a greedy algorithm is also easier than approaches like divide and conquer. This is because no recursion is involved and you don’t break down the problem into smaller pieces. You may not know how long these smaller pieces are gonna take to solve.
- The most difficult part of a greedy algorithm is to determine whether the solution we obtain is the most optimal one. It may require some mathematical concepts and science to prove that the most greedy choice at each step would lead to a global optimum solution.
Some best examples where a greedy algorithm gives the global optimum solution are:
Video Explanation:
