动态编程与贪婪算法有何不同？

Question

在这本书里，我用的是设计导论

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

由于两者都涉及局部最优性，因此其中一个不是另一个的子集吗？

Answer 1

关键区别在于贪婪算法“静态”地组成解决方案，即解决方案中的每个局部选择都可以最终确定，而无需了解所做的其他局部选择。然而，动态算法为子问题创建了一组可能的解决方案，并且仅在考虑了所有子问题后才生成全局问题的单个解决方案。关于贪婪算法的维基百科页面说得很好：

贪婪算法做出的选择可能依赖于迄今为止做出的选择，但不依赖于未来的选择或子问题的所有解决方案。它反复地做出一个又一个贪婪的选择，将每个给定的问题简化成一个更小的问题。换句话说，贪婪的算法永远不会重新考虑它的选择。这是与动态规划的主要区别，动态规划是详尽的，并保证找到解决方案。在每个阶段之后，动态规划基于前一阶段做出的所有决策做出决策，并可能重新考虑前一阶段的算法解决方案。

Answer 2

不同的是，动态编程要求您记住较小状态的答案，而贪婪算法是局部的，因为所需的所有信息都处于当前状态。当然，有一些交叉点。

Answer 3

动态规划适用于表现出以下特性的问题:

< li >重叠的子问题，以及 < li >最佳子结构。

最优子结构意味着你可以贪婪地解决子问题，并结合解决方案来解决更大的问题。动态规划和贪婪算法之间的区别在于，动态规划有重叠的子问题，这些子问题使用记忆来解决。“记忆化”是一种技术，通过这种技术，子问题的解决方案被用来更快地解决其他子问题。

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

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

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

对于动态规划与“重新考虑决策”有关的评论：对于任何线性动态规划算法，如最大子阵列问题或上述斐波那契问题，这显然是不正确的。

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