动态规划和贪心算法有何不同？

Question

动态规划和贪心算法有何不同？

algorithmdynamic-programminggreedy

44

在我使用的书籍 Introduction to the Design & Analysis of Algorithms 中，动态规划 被认为专注于 最优原理，"任何优化问题的最佳解决方案都由其子实例的最佳解决方案组成"。

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

既然两者都涉及局部最优性，难道一个不属于另一个子集吗？

- Irwin

1

LOL，你们把旧问题标记为新问题的副本？这没有任何意义。 - Irwin

我已经投票重新开放 - 从时间上看这没有意义。 - rayryeng

@Irwin，另一个问题的浏览量比这个多得多。 - nbro

7个回答

12

不同之处在于动态规划要求你记住较小状态的答案，而贪心算法在当前状态中只需要全部必需的信息。当然，两者也有些交集。

- bcurcio

9

关键区别在于贪心算法“静态”地组成解决方案，即解决方案中的每个局部选择都可以在不需要知道其他局部选择的情况下完成。然而，动态规划算法创建可能的子问题解决方案集，并且只有在考虑完所有子问题后才生成全局问题的单个解决方案。维基百科关于贪心算法页面很好地解释了这一点：

“贪心算法的选择可能取决于到目前为止做出的选择，但不取决于未来的选择或所有子问题的解决方案。它迭代地进行一个贪心选择又一个贪心选择，将每个给定的问题缩小为一个较小的问题。换句话说，贪心算法从不重新考虑其选择。这是与动态规划的主要区别，后者是穷举的并保证找到解决方案。在每个阶段之后，动态规划根据上一阶段所做的所有决策做出决策，并可能重新考虑前一阶段的算法路径以获得解决方案。”

- Kyle Strand

6

DP算法利用这样一个事实(对于某些问题)——问题规模为n的最优解由问题规模为n'<n的最优解组成，并利用此方法自下而上地构建解决方案，从最小的问题到所需的规模。

它很好地符合了递归原理(将问题缩小为更小的子问题，并进行递归调用)，事实上，DP解决方案通常表示为递归公式。

贪心算法看着一个局部点并根据该点的数据做出一些选择。对于某些问题(例如没有负权重的最短路径)，这种局部选择将导致最优解。

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

迪杰斯特拉算法是一种贪心算法（在每一步中，选择路径当前最小的节点-根据算法的局部状态贪心地进行选择）
贝尔曼-福德算法是一种动态规划解决方案（"放松"所有边，有效地减少问题规模）

- amit

3

Dijkstra算法是动态规划的一个例子，即使根据你的定义也是如此：正在解决的子问题是从应用于每个节点的根函数到该节点的距离。甚至在你提供的维基百科页面上有三个参考文献表明了这一点。 - Neil G

2

很抱歉，每个自底向上的DP算法都可以重写为记忆化的自顶向下形式，我怀疑反过来也是如此。记忆化DP只是递归的一种形式，在其中你已经注意到某些子问题出现了多次，所以通过仅解决每个子问题一次并记住答案来节省时间。贪心算法只是递归的一种形式，在其中你只考虑解决每个子问题的一种方式而不是所有可能的方式，要么是因为你可以证明你不需要，要么是因为你只对“足够好”的启发式解决方案感兴趣。 - j_random_hacker

那么，@j_random_hacker，你是在说所有的都只是递归技巧吗？这比我想要的要更加普遍。 - Irwin

1

@Irwin：或许那样说有点令人困惑，抱歉。迭代通常可以替代其中任意一种，而且可能更简单、更快（或者不是），但两种方法都可以（像所有重复的方式一样）使用递归来执行，这有时是最清晰的思考方式。如果你确实要编写每种方法的递归解决方案，最明显的区别将是 DP 方法会多次遇到相同的子问题。 - j_random_hacker

@Irwin：如果你会Python，那么你可能会对这个记忆化装饰器感兴趣，它可以将许多递归解决方案转换为它们的动态规划等效解。 - Neil G

1

@j_random_hacker 你的评论有什么作用来否定amit的答案。它是正确的，并强调了贪心算法最重要的部分 - 它基于局部信息做出选择。当前接受的答案强调的差异与此无关，也不正确。 - Ivaylo Strandjev

1

贪心算法：

贪心算法专注于扩展部分构建的解决方案。
它提供了许多结果，如可行解。
更有效率

动态规划：

专注于最优原则。
它提供具体答案。
效率较低

- Prashant Kumbharkar

0

DP和贪心算法的区别在于，DP会在每个子问题中寻找全局最优解，而贪心只会寻找局部最优解。因此，考虑以下情景：

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

对于贪心算法，你总是选择看起来更陡峭的那条路。这是一个局部最优决策，不能保证会导致最佳结果。

对于DP，在每个交叉口处，你应该已经知道每个分支将带你到的最高海拔（假设你的评估顺序是反向的，即从终点到起点），并选择海拔最高的那个。这个决策建立在未来子问题的全局最优解之上，因此对于这个子问题来说是全局最优的。

- NoSegfault

-1

贪心和动态规划的概念并不是互相排斥的，我认为这导致了大多数答案中的混淆。我相信amit的答案强调了最重要的特性：贪心算法基于局部信息做出决策。因此，贪心算法可能会找到一个局部最优解而不是全局最优解。

动态规划将问题分解成较小的子问题，然后聚合结果以获得更复杂问题的答案。那么，一个问题是否可能既是动态规划又是贪心算法呢？答案是肯定的。一个例子就是Dijkstra算法。对于这个算法，你在每一步都做出贪心选择，但是你将问题简化为一个更简单的子问题。

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

- Ivaylo Strandjev

你对Dijkstra算法的理解是错误的，我在评论中已经解释了原因：没有堆的Dijkstra算法将成为一种贪心算法。堆引入了一种依赖关系，即当对子问题（到顶点的最短路径）的解决方案做出决策时，用于促进对其他子问题的决策。这就是为什么Dijkstra算法不仅仅是一种贪心算法（否则你必须独立地做出决策）。这与你链接的Quora上排名第一的答案相符。 - Neil G

1

这是不正确的（我怀疑您由于误解而对正确答案进行了负评）。对于未来的读者，请参见与Neil G的聊天记录。 - Kyle Strand

1

我没有给任何人投反对票。如果你认为这不正确，请详细说明。我认为聊天记录并没有证明我错了，但我们也没有达成谁是正确的共识。 - Ivaylo Strandjev

1

我会在有时间的时候阅读您的评论。与此同时，您可以自由地为他提供支持。尽管如此，我仍然坚信我的答案是正确的。 - Ivaylo Strandjev

1

根据这个答案，这里提供以上聊天记录的链接，而不是聊天室本身：http://chat.stackoverflow.com/transcript/90030 - Kyle Strand

显示剩余2条评论

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

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

- Neil G · Accepted Answer

动态规划适用于具有以下特性的问题：

重叠子问题
最优子结构

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

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

考虑问题“用美元、镍和便士找零钱”。这是一个贪心问题。它表现出最优子结构，因为您可以解决美元的数量。然后，解决镍的数量。然后是便士的数量。然后，您可以有效地组合这些子问题的解决方案。它实际上没有表现出重叠子问题，因为解决每个子问题对其他问题的帮助不大（也许有点）。

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

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

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