How does the Greedy Algorithm works?
Greedy Algorithm solve optimization problems by making the best local choice at each step in the hope of finding the global optimum. It’s like taking the best option available at each moment, hoping it will lead to the best overall outcome.
Here’s how it works:
- Start with the initial state of the problem. This is the starting point from where you begin making choices.
- Evaluate all possible choices you can make from the current state. Consider all the options available at that specific moment.
- Choose the option that seems best at that moment, regardless of future consequences. This is the “greedy” part – you take the best option available now, even if it might not be the best in the long run.
- Move to the new state based on your chosen option. This becomes your new starting point for the next iteration.
- Repeat steps 2-4 until you reach the goal state or no further progress is possible. Keep making the best local choices until you reach the end of the problem or get stuck..
Example:
Let’s say you have a set of coins with values {1, 2, 5, 10, 20, 50, 100} and you need to give minimum number of coin to someone change for 36.
The greedy algorithm for making change would work as follows:
- Start with the largest coin value that is less than or equal to the amount to be changed. In this case, the largest coin less than 36 is 20.
- Subtract the largest coin value from the amount to be changed, and add the coin to the solution. In this case, subtracting 20 from 36 gives 16, and we add a 20 coin to the solution.
- Repeat steps 1 and 2 until the amount to be changed becomes 0.
So, using the greedy algorithm, the solution for making change for 36 would be one 20 coins, one 10 coin, one 5 coins and one 1 coin needed.
Note: This is just one example, and other greedy choices could have been made at each step. However, in this case, the greedy approach leads to the optimal solution.
The greedy algorithm is not always the optimal solution for every optimization problem, as shown in the example below.
- One such example where the Greedy Approach fails is to find the Maximum weighted path of nodes in the given graph.
Graph with weighted vertices
- In the above graph starting from the root node 10 if we greedily select the next node to obtain the most weighted path the next selected node will be 5 that will take the total sum to 15 and the path will end as there is no child of 5 but the path 10 -> 5 is not the maximum weight path.
Greedy Approach fails
- In order to find the most weighted path all possible path sum must be computed and their path sum must be compared to get the desired result, it is visible that the most weighted path in the above graph is 10 -> 1 -> 30 that gives the path sum 41.
Correct Approach
- In such cases Greedy approach wouldn’t work instead complete paths from root to leaf node has to be considered to get the correct answer i.e. the most weighted path, This can be achieved by recursively checking all the paths and calculating their weight.
Greedy Algorithm Tutorial – Examples, Application and Practice Problem
Greedy Algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It works for cases where minimization or maximization leads to the required solution.
Greedy Algorithm
Table of Content
- What is Greedy Algorithm?
- Characteristics of Greedy Algorithm
- Examples of Greedy Algorithm
- Why to use Greedy Approach?
- How does the Greedy Algorithm works?
- Greedy Algorithm Vs Dynamic Programming
- Applications of Greedy Algorithms
- Advantages of Greedy Algorithms
- Disadvantages of the Greedy Approach
- Greedy Algorithm Most Asked Interview Problems
- Frequently Asked Questions on Greedy Algorithm
Contact Us