Dynamic Programming Vs Greedy

Susritha09 — Tue, 04 May 2021 13:18:11 +0000

Dynamic Programming:

It just solves problems by combining the sub problems to solutions only of the sub problems were independent.
It can be used for solving both mathematical optimization method and computer programming method.
For example, it can be used for finding the shortest path in graph.
• Many decision sequence may be generated.
• Highly reliable
• Bottom-up approach
• There is no special set of feasible solution
• Less Efficiency
• Overlapping subproblems choose feasible solution

The algorithm used is:

Greedy Method:

Greedy method solves problems step by step which leads to global optimization solution.
• Generates a single decision sequence
• Less reliable
• Top to bottom approach
• Contain a special set of feasible set of solutions.
• More efficiency
• Overlapping subproblems cannot be handled.

Algorithm for greedy is:
Greedy(D,n)
//In Greedy approach D is domain
//from which solution is to be obtained of size n
//Initially assume
solution<-0
for i<-1 to n do{
s<-select(D)
if(Feasible solution,s))then
Solution<-Union(Solution,s)
}
return solution

Dynamic Programming Vs Greedy method

Susritha09 — Sun, 02 May 2021 06:04:18 +0000