- Both techniques use optimal substructure (optimal solution “contains optimal solution for subproblems within it”). In dynamic programming, solution depends on solution to subproblems. That is, compute the optimal solutions for each possible choice and then compute the optimal way to combine things together. In greedy algorithm we choose what looks like best solution at any given moment and recurse (choice does not depend on solution to subproblems).
Note: Shortsightedness: Always go for seemingly next best thing, optimizing the present without regard for the future, and never change past choices. - Any problem that can be solved by a greedy algorithm can be solved by dynamic programming, but not the other way around.
- It is often hard to figure out when being greedy works!
- How do we know if being greedy works? Try dynamic programming first and understand the choices. Try to find out if there is a locally best choice, i.e. a choice that looks better than the others (without computing recursive solutions to subproblems). Now try to prove that it works correctly.
- Greedy correctness proof: It is enough to prove that there exists an optimal solution which contains the greedy choice. That is, prove that, having made the greedy choice, what remains is a subproblem with the property that if we combine the optimal solution to the subproblem with the greedy choice, we get an optimal solution for the original problem. Typically this is proved by contradiction
Sharing is Caring !
Subscribe
0 Comments
Most Voted