To solve the optimization problem in computing the two methods namely greedy and dynamic programming are used. The solutions produced by the greedy algorithms are more effective than the dynamic programming solutions. The primary difference between the greedy method and dynamic programming is that greedy method just generates only one decision sequence. As against, dynamic programming can produce many decision sequences.
Content: Greedy Method Vs Dynamic Programming
Comparison Chart
| Basis for comparison | Greedy Method | Dynamic programming |
|---|---|---|
| Basic | Generates a single decision sequence. | Many decision sequence may be generated. |
| Reliability | Less reliable | Highly reliable |
| Follows | Top-down approach. | Bottom-up approach. |
| Solutions | Contain a particular set of feasible set of solutions. | There is no special set of feasible set of solution. |
| Efficiency | More | Less |
| Overlapping subproblems | Cannot be handled | Chooses the optimal solution to the subproblem. |
| Example | Fractional knapsack, shortest path. | 0/1 Knapsack |
Definition of Greedy Method
A Greedy method is considered to be most direct design approach and can be applied to a broad type of problems. Usually, these types of problems contain ‘n’ inputs from which a certain group of a subset is obtained that fulfils some conditions. The subset that fulfils these conditions is called a feasible solution. The particular feasible solution is searched that could increase or decrease the given objective function, this solution is called as an optimal solution. A feasible solution can easily be determined while an optimal solution is difficult to find.
The greedy method is helpful in devising an algorithm which involves some stages with a single intake at each stage in its working. For each particular stage, a decision is made against the input in an order identified by a selection procedure for the optimal solution. The input is not included in the partial solution if the addition of the next input in the partly built optimal solution could result in the infeasible outcome. Otherwise, it is added.
Optimization measure is the foundation of the selection procedure in the form of objective function. There are several different optimization measures that produces sub-optimal solutions and this technique is known as subset paradigm.
Definition of Dynamic Programming
Dynamic programming is used for designing the algorithms. It was mainly devised for the problem which involves the result of a sequence of decisions. When it is hard to obtain a sequence of stepwise decisions of a problem which lead to the optimal decision sequence then each possible decision sequence is deduced. Hence all decision sequence can be calculated and the best is selected. Dynamic programming is capable of significantly decreasing the quantity of enumeration by evading the enumeration regarding the decision sequences that does not contain optimal results.
Dynamic programming follows the Principle of optimality. Now, what is Principle of optimality? It describes that an optimal sequence of decisions possesses a feature which is irrespective of initial state and decision and the rest of the decisions should construct an optimal decision sequence with respect to the outcome state of the first decision.
The complexity of the dynamic programming algorithms is usually polynomial. Another crucial property of this approach is that the optimal solutions of the subproblems are stored previously to eliminate the requirement of recomputation of its values.
Key Differences Between Greedy Method and Dynamic Programming
- Greedy method produces a single decision sequence while in dynamic programming many decision sequences may be produced.
- Dynamic programming approach is more reliable than greedy approach.
- Greedy method follows a top-down approach. As against, dynamic programming is based on bottom-up strategy.
- Greedy algorithm contains a unique set of feasible set of solutions where local choices of the subproblem leads to the optimal solution. In contrast, in dynamic programming one problem is chosen from all the secondary subproblems which is capable of providing an optimal solution.
- Dynamic programming is less efficient and can be unnecessarily costly than greedy algorithm.
- Greedy method does not have the ability to handle overlapping subproblems whereas dynamic programming approach successfully handles the overlapping subproblems.
- The implementation of greedy method is fractional knapsack, shortest path algorithm, etcetera. On the contrary, 0/1 knapsack is one of the examples of dynamic programming.
Conclusion
Greedy method and dynamic programming both are used to find the optimal solution to the problem from a set of feasible solutions. The main difference between them is that Greedy method never reexamines its selections while Dynamic programming is inverse which also assures to provide an optimal solution to the problem.
Leave a Reply