43

在我正在使用的《算法设计与分析简介》一书中，据说动态规划关注的是最优性原理，“任何优化问题实例的最优解都由其子实例的最优解组成”。

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

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

4

7 回答 7

53

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

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

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

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

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

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

回应关于动态规划与“重新考虑决策”有关的评论：这显然不适用于任何线性动态规划算法，如最大子数组问题或上面的斐波那契问题。

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

于 2012-12-04T23:18:59.200 回答
12

不同之处在于，动态编程要求您记住较小状态的答案，而贪心算法是本地的，因为所需的所有信息都处于当前状态。当然，也有一些交集。

于 2012-12-04T23:13:21.740 回答
9

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

贪心算法做出的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个又一个贪婪的选择，将每个给定的问题减少为一个较小的问题。换句话说，贪心算法永远不会重新考虑它的选择。这是与动态规划的主要区别，动态规划是详尽的并且保证能找到解决方案。在每个阶段之后，动态规划都会根据前一阶段做出的所有决策做出决策，并且可能会重新考虑前一阶段的算法路径来解决问题。

于 2012-12-05T00:14:43.790 回答
6

DP 算法使用以下事实（对于某些问题） - 大小问题的最佳解决方案由大小问题的n最佳解决方案组成n'<n，并使用它自下而上构建解决方案，从最小问题到所需尺寸。

它非常符合递归的相同原理（将问题简化为较小的子问题，并递归调用），实际上 - DP 解决方案通常表示为递归公式。

贪心算法正在查看一个局部点，并在这一点上对数据进行一些选择。对于某些问题（例如，没有负权重的最短路径） - 这种本地选择将导致最佳解决方案。

两种方法之间差异的一个很好的例子是最短路径问题：

  • Dijsktra 的算法是一种贪心方法（在每一步，选择路径当前最小化的节点 - 选择是基于算法的本地状态贪心地完成的）。
  • Bellman-Ford 算法是一种 DP 解决方案（“放松”所有边缘，有效地减少了问题）
于 2012-12-04T23:10:54.283 回答
1

贪心法：

  1. 贪心方法侧重于扩展部分构造的解决方案。
  2. 它提供了许多结果，例如可行的解决方案。
  3. 更高效

动态规划：

  1. 关注最优性原则。
  2. 它提供了具体的答案。
  3. 效率较低
于 2013-08-28T18:23:18.097 回答
0

DP和greedy的区别在于DP会在每个子问题上寻找全局最优，而greedy只会寻找局部最优。所以，关于这种情况：

假设你正在爬一座山，你想爬得尽可能高。山上的路有好几条支路，在每个路口你需要决定走哪条支路，这是这个攀登问题的子问题（目标相同，只是起点不同）

For the greedy algorithm, you will always choose whichever one seems more steeply up. This is a local optimal decision and is not guaranteed to lead to the best result

For the DP, at each intersection, you should already know the highest altitude each branch will lead you to (suppose your evaluation order is reversed, a.k.a from end points to the starting point), and choose the one with the largest altitude. This decision is build upon the global optimum of the future subproblems and there for will be globally optimum for this subproblem

于 2017-04-20T21:19:14.583 回答
-1

贪婪和动态解决方案的概念并不相互排斥，我认为这在大多数答案中造成了很多混乱。我相信阿米特的回答强调最重要的属性：贪婪的解决方案会根据本地信息做出决策。因此，贪婪的解决方案最终可能会找到局部最优而不是全局最优。动态解决方案将问题分解为更小的子问题，然后聚合结果以获得更大更复杂问题的答案。那么-问题是否可能既是动态的又是贪婪的? 答案是——是的，这是可能的。一个例子是 Dijkstra 的算法。对于此算法，您在每一步都做出了贪婪的选择，但您将问题简化为更简单的子问题。

还有一些不是 DP-s 的贪心算法的例子：比如爬山是一种贪心算法，它不会将一个问题分解为多个子问题——它总是只解决一个子问题。还有一些不贪心的 DP 示例 - 例如，使用记忆化计算第 n 个斐波那契数不是贪心的。

于 2015-09-18T13:51:52.193 回答