Greedy Algorithm:
Greedy algorithm solve problem by making the choice that seems best at that particular moment. Many optimization problems can be solved using a greedy algorithm.
We shall arrive at greedy algorithm by first considering a dynamic approach and then showing that we can always make greedy choice to arrive at an optimal solution.
A greedy algorithm works well if problem have the following three properties.
i. Feasible solution : We check whether all the constraints are satisfied or not so that we have an optimal solution for the problem under consideration.
ii. Greedy choice : The input is consider from the current available feasible solution. i.e. we make whatever choice seems best at that particular moment.
iii. Unalterable : At any subsequent stages a choice remains unaltered once it is made.
Applications of Greedy Algorithms
1. Construction of MST using prim’s and kruskals algorithm.
2. Scheduling activity selection problem.
3. Solving TSP.
4. Huffman’s coding algorithm.
5. Single source shortest path using Dijkstra algorithm.
6. Solving fractional knapsack problem.
Different between Greedy Algorithm and Dynamic Programming :
N o. | Greedy Algorithm | Dynamic programming |
1. | Here, we make whatever choice seem s best at the moment t and then solve the sub problem arising after the choice is made. | We make a choice at each step. |
2. | The choice made by greedy algorithm may depend on choice so far, but it can not depend in any future choice or on the solution to sub problem . | Choice usually depends o n the solutions to sub problems. |
3. | It uses top-down approach, problems gets decreased in size. | It uses bottom- up approach, processing from smaller to larger sub-problems. |
4. | Applications are : Construction of MST, SSSP problem using Dijkstra algorithm , scheduling activity selection problem fractional knapsack problem etc.... | Application are : Matrix chain multiplication, longest common sub sequence, optimal binary search tree, 0/ ^ knapsack problem etc....
|
