algorithm - 使用动态规划或贪心方法解决问题？

Question

问题应该具有哪些属性，以便我可以决定使用动态编程或贪婪方法的方法？

Answer 1

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

这种问题的一个例子是矩阵链乘法。

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

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

Answer 2

Cormen、Leiserson、Rivest 和 Stein 的算法书的第二版有一节 (16.4)，标题为“贪心方法的理论基础”，讨论了贪心方法何时产生最佳解决方案。它涵盖了许多实际感兴趣的案例，但并非所有产生最佳结果的贪心算法都可以根据该理论来理解。

我还看到了一篇题为“从动态编程到贪心算法”的论文，链接在这里，其中讨论了某些贪心算法可以看作是动态编程的改进。通过快速扫描，您可能会感兴趣。

Answer 3

知道它确实有严格的规定。正如有人已经说过的，有些事情应该打开红灯，但最终只有经验才能告诉你。

Answer 4

当可以根据每个阶段可用的本地信息做出决策时，我们应用贪心方法。我们确信遵循每个阶段的决策集，我们会找到最佳解决方案。然而，在动态方法中，我们可能不确定在一个阶段做出决定，因此我们携带一组可能的决定，其中一个可能的元素可能会用于解决方案。