Logic series - 6

Greedy Algorithm


The algorithm that is designed to achieve the most optimized solution according to the given condition.

The greedy algorithm is follows the problem solving heuristic of making the locally optimal choice at each stage to find the global optimum.

In many problem the greedy strategy in general produce an optimal solutions but nonetheless a greedy heuristic may yield locally optimal solutions that help to produce a global optimal solutions that help to produce a global optimal solution in a reasonable time.

In normal words if we want to understand the greedy algorithm then it can be stated as “It is an algorithm where compiler greedily makes optimal choice for that moment to solve the problem and then try to solve the problems which are occurred due to that choice and mostly those regenerated problems are quite high compare to the first problem”. 

While applying this algorithm on live projects it creates the biggest roadblocks for the continuation of the project which are dependent on the previous model, in greedy applications a compiler will always think about the next step and does not look for the entire picture.

If we take a common example of this algorithm from above image, if we have given the task is to find the largest sum path at that moment the greedy algorithm will like.

Step 1 – It starts from 7 that is root node

Step 2 – Then from 3 and 12, as 12 is the greater among these two values according to this compiler it will select 12

Step 3 – As on next step node the compiler will select the 6 in between the node values 5 and 6 as it is the largest one.

So according to the greedy algorithm the addition will be 7+12+6=25 while the actual output should be 7+3+99=109

But it is not always that greedy algorithm is provide us the wrong algorithm.

We can see one more example of this.

If we have Rs.1, Rs.2, Rs.5 and Rs.10 coins and from this coin we want to make the addition as Rs.18  

In this case the greedy algorithm will work as 

Step 1 – It select Rs.10 coin, Rs.8 are remaining.

Step 2 – Then it will select Rs.5 Coin, Rs.3 are remaining.

Step 3 – Then according to the Greedy algorithm it will select the Rs.2 coin, Rs.1 is remaining.

Step 4 – Then at last it will select the remaining Rs.1 coin.

So in this process to cover up the Rs.18 we got around 4 coins and in general it is the best optimal solution as well.

Advantage of greedy algorithm.

- Straight forward, Easy to understand and code.

- Finding solution is quite easy.

- Once we have made our choice we don’t have to re-examining the already computed value.

Disadvantage of Greedy algorithm.

- We have to work much harder to understand the correctness of the algorithm.

- Even with the correct algorithm it is hard to prove why it is correct.

- In most of the cases it is not guaranteed that it will lead to most optimized solutions after getting the locally correct optimized solution.

n References

- Wikipedia

- Image reference – Wiki.

--Eduwithus Team.