The fear of the LORD is the beginning of wisdom, and knowledge of the Holy One is understanding.
Friday, March 7, 2014
Divide and Conquer, DP and Greedy Algorithm
When I have a problem with optimal substructure and no subproblem shares subsubproblems then I can use a divide and conquer algorithm to solve it?
Yes, as far as you can find an optimal algorithm for each kind of subproblem.
But when the subproblem shares subsubproblems (overlapping subproblems) then I can use dynamic programming to solve the problem?
Is this correct?
Yes. Dynamic programming is basically a special case of the family of Divide & Conquer algorithms, where all subproblems are the same.
And how is greedy algorithms similar to dynamic programming?
They're different.
Dynamic programming gives you the optimal solution.
A Greedy algorithm usually give a good/fair solution in a small amount of time but it doesn't assure to reach the optimum.
It is, let's say, similar because it usually divides the solution construction in several stages in which it takes choices that are locally optimal. But if stages are not optimal substructures of the original problem, then normally it doesn't lead to the best solution.
EDIT:
There are some greedy algorithms that have been proven to be optimal (e.g. Dijkstra, Kruskal, Prim etc.).
So, to be more correct, the main difference between greedy and dynamic programming is that the former is not exhaustive on the space of solutions while the latter is.
In fact greedy algorithms are short-sighted on that space, and each choice made during solution construction is never reconsidered.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment