Greedy Algorithm

Greedy Algorithm

 

Greedy algorithm is builds up a solution piece by piece, always choosing the next piece that offers the most  immediate benefit.Solving a problem by selecting the best option available at the moment is the main approach of this algorithm. This algorithms try to find a localized optimum solution, which may eventually lead to  optimized solutions.

The algorithm never reverses the earlier decision even if the choice goes wrong. This algorithm works in a top-down approach.

To solve a problem based on greedy approach, there are two stages they are follows:

1. 1. Scanning the list of items
   2. Optimization

 

 

Greedy Approach

 

1. Firstly start with the 20 i.e root node. The right child has weight 3 and the  left child has weight is 2.

2. We have to find the largest path and the optimal solution at the moment is 3. So, the greedy algorithm choose the 3.

3. The weight of only child of 3 is 1  so we  give final result 20 + 3 + 1 = 24.

It is not the optimal solution. There is one other path that carries more weight (20 + 2 + 10 = 32) as shown in the following figure

 

 

 

Greedy Algorithm

 

1. To begin with, the solution set i.e.containing answers is empty.
2. At every step, an item is added to the solution set until a solution will reached.
3. If the solution set is feasible, kept the current item.
4. Else, the item get rejected and never considered again.

 

 

 

Advantages of Greedy Approach

 

• This algorithm is easier to describe.
• This algorithm perform better than other algorithms

 

 

Drawback of Greedy Approach

 

The major disadvantage of this algorithm is as mentioned above, the greedy algorithm does not always produce the optimal solution.