algorithm - 动态规划与贪心算法有何不同？

Question

在我使用的书中Introduction to the Design & Analysis of Algorithms ，据说动态规划专注于最优性原则，“优化问题的任何实例的最优解都由其子实例的最优解码成”。

然而，贪婪技术侧重于扩展部分构建的解决方案，直到您找到完整问题的解决方案。然后说，它一定是“在该步上所有可行选择中的最佳本地选择”。

由于两者都涉及局部最优性，所以一个不是另一个的子集吗？

Answer 1

动态规划适用于具有以下性质的问题:

• 重叠的子问题，以及
• 最优子结构。

最优子结构意味着您可以贪婪地解决子问题并将解决方案组合起来解决更大的问题。 动态规划和贪心算法的区别在于，动态规划存在重叠的子问题，而这些子问题是使用记忆化解决的。 “记忆化”是一种利用子问题的解决方案更快地解决其他子问题的技术。

这个答案引起了一些关注，所以我会举一些例子。

考虑“用美元、镍币和便士找零”这个问题。这是一个贪婪的问题。它展示了最佳子结构，因为您可以解决美元数量问题。然后，求解镍的数量。然后是便士的数量。然后，您可以有效地组合这些子问题的解决方案。它并没有真正表现出重叠的子问题，因为解决每个子问题对其他问题没有多大帮助(可能有一点)。

考虑“斐波那契数列”这个问题。它展示了最佳子结构，因为您可以有效地(通过加法)从 F(9) 和 F(8) 求解 F(10)。这些子问题重叠，因为它们都共享 F(7)。如果在求解 F(8) 时记住 F(7) 的结果，则可以更快地求解 F(9)。

回应有关动态规划与“重新考虑决策”有关的评论:对于任何线性动态规划算法，如 the maximum subarray problem，这显然不是真的。或上面的斐波那契问题。

从本质上讲，将具有最优子结构的问题想象成一个有向无环图，其节点代表子问题(其中整个问题由入度为零的节点代表)，其有向边代表子问题之间的依赖关系。然后，贪心问题是一棵树(除根以外的所有节点都有单位入度)。动态规划问题有一些入度大于一的节点。这说明了重叠的子问题。