分而治之，动态规划和贪心算法！ [英] Divide and conquer, dynamic programming and greedy algorithms!
问题描述
当我有一个最佳的substructur无子问题股subsubproblems问题，那么我可以使用分而治之的算法来解决它？
但是，当子问题股subsubproblems（重叠子问题），那么我可以用动态规划来解决这个问题？
这是正确的？
和如何贪婪算法类似，动态规划？
当我有最佳的一个问题 substructur无子问题股 subsubproblems那么我可以用一个鸿沟 而治之算法来解决呢？
是的，只要你可以找到各种子问题的优化算法。
但子问题股时， subsubproblems（重叠 子问题），那么我可以使用动态 编程来解决这个问题？
这是正确的？
是的。动态规划是基本上分割和安培的家族的一种特殊情况;征服的算法，其中所有子问题是相同的。
和如何贪婪算法相似 以动态规划？
他们是不同的。照片 动态编程为您提供了最佳的解决方案。照片 贪婪算法通常会在少量的时间的好/公平的解决方案，但它并不能保证达到最佳。
这是假设的，相似的，因为它通常把解决建设中，需要选择是局部最优的几个阶段。但如果阶段是不原问题的最优子结构，则通常不会导致最佳的解决方案。
编辑：
正如所指出@rrenaud，有已被证明是最优的（例如Dijkstra算法，采用Kruskal，普里姆等）一些贪心算法。
所以，为了更正确，贪婪和动态规划之间的主要区别在于，前者并不详尽上解的空间，而后者则是。
事实上贪心算法是短视的空间和解决方案在建筑期间做每一个选择是永远不会重新考虑。
When I have a problem with optimal substructur and no subproblem shares subsubproblems then I can use a divide and conquer algorithm to solve it?
But when the subproblem shares subsubproblems (overlapping subproblems) then I can use dynamic programming to solve the problem?
Is this correct?
And how is greedy algorithms similar to dynamic programming?
When I have a problem with optimal substructur 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:
As pointed out by @rrenaud, 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.
这篇关于分而治之，动态规划和贪心算法！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
