当我遇到一个具有最优子结构且没有子问题共享子子问题的问题时，我可以使用分治算法来解决它吗？
但是当子问题共享子子问题（重叠子问题）时，我可以使用动态规划来解决问题吗？
这样正确吗？
贪心算法和动态规划有何相似之处？
2个回答
8
当我遇到具有最优子结构而没有子问题共享子子问题的问题时，我可以使用分治算法来解决它吗？
是的，只要您可以找到每种子问题的最优算法。
但是当子问题共享子子问题（重叠子问题）时，我可以使用动态规划来解决问题吗？这正确吗？
是的。动态规划基本上是分治算法家族的一个特例，其中所有子问题都相同。
贪心算法与动态规划有何相似之处？
它们是不同的。动态规划提供最优解。贪心算法通常在很短的时间内给出一个好/公平的解决方案，但不能保证达到最优解。
它是“类似于”，因为它通常将解决方案构建分成几个阶段，在这些阶段中，它采取局部最优选择。但是，如果阶段不是原始问题的最优子结构，则通常不会导致最佳解决方案。
编辑：
正如@rrenaud指出的那样，已经证明了一些贪心算法是最优的（例如Dijkstra、Kruskal、Prim等）。因此，更正确地说，贪心和动态规划之间的主要区别在于前者对解决方案空间不是穷举的，而后者是。实际上，贪心算法在该空间上是短视的，并且在解决方案构建过程中做出的每个选择都不会重新考虑。
是的，只要您可以找到每种子问题的最优算法。
但是当子问题共享子子问题（重叠子问题）时，我可以使用动态规划来解决问题吗？这正确吗？
是的。动态规划基本上是分治算法家族的一个特例，其中所有子问题都相同。
贪心算法与动态规划有何相似之处？
它们是不同的。动态规划提供最优解。贪心算法通常在很短的时间内给出一个好/公平的解决方案，但不能保证达到最优解。
它是“类似于”，因为它通常将解决方案构建分成几个阶段，在这些阶段中，它采取局部最优选择。但是，如果阶段不是原始问题的最优子结构，则通常不会导致最佳解决方案。
编辑：
正如@rrenaud指出的那样，已经证明了一些贪心算法是最优的（例如Dijkstra、Kruskal、Prim等）。因此，更正确地说，贪心和动态规划之间的主要区别在于前者对解决方案空间不是穷举的，而后者是。实际上，贪心算法在该空间上是短视的，并且在解决方案构建过程中做出的每个选择都不会重新考虑。
- digEmAll
4
3有些贪心算法是最优的。例如Dijkstra的最短路径算法或最大子数组和问题。贪心算法往往不会在不同的可能性上分支，而动态规划算法则倾向于在不同的可能最优选择上进行分支，然后确定哪个选择是最好的。 - Rob Neuhaus
请问您能否解释一下“动态规划基本上是分治算法家族的一个特例，其中所有子问题都是相同的”这句话？我不理解什么是相同的子问题。 - saplingPro
@grassPro：我的意思是，动态规划需要一个可分解成相同类型子问题的问题，因为您始终使用相同的例程递归地解决主问题和子问题。 - digEmAll
2我学到的一个经验法则是，动态规划适用于可以分解为“离散、重叠子集”的问题。重叠部分是使动态规划起作用的关键。 - Andrew
-2
动态规划使用自底向上的方法，保存先前的解决方案并引用它，这将使我们在所有可用解决方案中得出最优解，而贪心算法使用自顶向下的方法，因此它从局部可用解决方案中获取最优解，不会考虑之前的层级解决方案，导致解决方案不够优化。
动态规划=自底向上，最优解
贪心算法=自顶向下，不够优化，时间消耗较少。
- PRIIYANCA
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接