使用动态规划或贪心算法解决问题的方案？

Question

4

问题应该具备哪些属性，以便我可以决定使用动态规划还是贪心算法？

- Eric

1

听起来有点像一道作业题。 - Jon W

4个回答

1

Cormen、Leiserson、Rivest和Stein的《算法》第二版有一节（16.4）名为“贪心方法的理论基础”的章节，讨论了何时贪心方法可以得到最优解。它涵盖了许多实际感兴趣的案例，但并不是所有能够产生最优结果的贪心算法都能用这个理论来理解。

我也遇到了一篇名为“从动态规划到贪心算法”的论文，链接在这里。该论文提到了某些贪心算法可以被看作是动态规划的改进。快速浏览后，可能会对您有所帮助。

- user486972

0

这是一个非常严格的规则，需要深入了解。正如其他人所说，有些事情应该引起警惕，但最终只有经验才能告诉你。

- bluehallu

0

当每个阶段只有局部信息可用时，我们采用贪心算法。我们确信在每个阶段遵循一组决策后，我们将找到最优解。然而，在动态方法中，我们可能不能确定在一个阶段做出决策，因此我们会带上一组可能的决策，其中一个可能的元素可能会导致解决方案。

- teena garg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- danben · Accepted Answer

动态规划问题表现出最优子结构。这意味着问题的解可以表示为严格较小的子问题的解的函数。

其中一个例子是矩阵链乘法。

贪心算法只能在局部最优选择导致完全最优解时使用。这可能更难立即看到，但一般来说更容易实现，因为您只需要考虑一件事情（贪心选择）而不是多个（所有较小子问题的解决方案）。

Kruskal算法是寻找最小生成树的著名贪心算法之一。