Greedy method is a simple technique that is easy to understand.
Definition:
In greedy approach, we make decision on the current information available at the present time without worrying about the affect on the future result.
Let’s understand the above statement with help of an example.
Consider the graph below, you need to go from A to D with minimum cost.
From node “a”, we can either go to node “b” or node “c”.
With greedy method approach, we choose “a” to “b”. Because it is having less cost than “a” to “c”.
Then we move from “b” to “d”. Hence the total cost for “a” to “d” is “a to b” + “b to d” i.e 2 + 1 = 3.
Here we got the path with minimum cost.
But greedy approach will not always give the optimal solution.
Consider other graph as given below:
Now we need to reach from node “a” to “d”. As always we become greedy and choose “a” to “b” as the cost is “1”. Then we move from “b” to “d”. Hence the total cost will be 7.
But if you observe, “a to c” and “c to d” will cost only 3.
Hence in the definition we can say that, we make a decision based on current data available. Once the choice is made you cannot change it.
Ok, we stump upon an important question. When to choose greedy method to solve a problem?
For a problem to be solved by greedy approach, the problem should satisfy below 2 Properties:
-
Greedy Choice Property:
This property states that a global optimal solution can be achieved by selecting locally optimal solution.
-
Optimal Sub Problem Property:
It means, the sub problem you choose should be the optimal of all the sub problems present.
Let us understand above 2 properties with help of an example. Consider the graph below and you need to reach from node “a” to “b” at less cost.
For the 1stproperty: We choose the locally optimal sub solution and choose to go from “a” to “b”. Then we go to “b” to “d”. hence we have locally chosen the optimal solution and has
Resulted in globally optimal solution.
For the 2ndproperty: The sub problem which we choose should be optimal of all the sub problem.
In this example, from “a” we can go to “b” or “c”. We have chosen to go “a to b”. And again we have “c to d” or “b to d”. Again we chosen to go “b to d”, which is optimal of the sub problem. Hence we can solve this problem with help of greedy approach.
Below are the generic steps to be followed for a greedy algorithm.
- Initialize the set of items
- At each step, take a single item.
- Check if the selected item is feasible or not. If feasible add to the current set.
- If not feasible, discard the item and move to the next item.
We can see this kind of implementation in MST algorithms, that are discussed in coming chapters.
Below are some of the examples/ problems that can be solved using greedy approach.
- Finding shortest path
- Finding Minimum Spanning Tree [MST]
- Job sequencing problem
- Fractional Knapsack problem
We shall see all the above problems in coming chapters.
Further Reading:
