54

就使用而言，动态编程和贪婪方法之间的主要区别是什么？

据我了解，贪婪方法有时会给出最佳解决方案；在其他情况下，动态规划方法给出了最优解。

为了使用一种方法（或另一种方法）来获得最佳解决方案，是否必须满足任何特定条件？

4

6 回答 6

83

基于维基百科的文章。

贪婪的方法

贪心算法是一种遵循问题求解启发式的算法，在每个阶段做出局部最优选择，希望找到全局最优。在许多问题中，贪心策略通常不会产生最优解，但贪婪启发式算法可能会产生局部最优解，在合理时间内逼近全局最优解。

我们可以做出目前看起来最好的任何选择，然后解决以后出现的子问题。贪心算法做出的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个又一个贪婪的选择，将每个给定的问题减少为一个较小的问题。

动态规划

动态规划背后的想法非常简单。一般来说，要解决一个给定的问题，我们需要解决问题的不同部分（子问题），然后结合子问题的解决方案来达到一个整体的解决方案。通常，当使用更幼稚的方法时，会多次生成和解决许多子问题。动态规划方法试图只解决每个子问题一次，从而减少计算次数：一旦计算了给定子问题的解决方案，它就会被存储或“记忆化”：下次需要相同的解决方案时，它简直是抬头。当重复子问题的数量作为输入大小的函数呈指数增长时，这种方法特别有用。

区别

贪心选择属性

我们可以做出目前看起来最好的任何选择，然后解决以后出现的子问题。贪心算法做出的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或子问题的所有解决方案。它迭代地做出一个又一个贪婪的选择，将每个给定的问题减少为一个较小的问题。换句话说，贪心算法永远不会重新考虑它的选择。

这是与动态规划的主要区别，动态规划是详尽的并且保证能找到解决方案。在每个阶段之后，动态规划都会根据前一阶段做出的所有决策做出决策，并且可能会重新考虑前一阶段的算法路径来解决问题。

例如，假设您必须在给定城市的高峰时段尽可能快地从 A 点到达 B 点。动态规划算法将查看整个交通报告，查看您可能采取的所有可能的道路组合，然后才会告诉您哪种方式最快。当然，您可能需要等待一段时间，直到算法完成，然后才能开始驾驶。您将采取的路径将是最快的路径（假设外部环境没有任何变化）。

另一方面，贪心算法会立即让您开车，并会在每个路口选择看起来最快的道路。正如您可以想象的那样，这种策略可能不会导致最快的到达时间，因为您可能会走一些“轻松”的街道，然后发现自己陷入了交通堵塞。

其他一些细节...

在数学优化中，贪心算法解决具有拟阵性质的组合问题。

动态规划适用于具有重叠子问题和最优子结构性质的问题。

于 2013-09-12T13:29:14.300 回答
23

我想引用一段描述贪心算法和动态规划算法之间的主要区别的段落，该算法在Cormen的《算法简介》（第 3 版）第 15.3 章第 381 页中所述：

贪心算法和动态规划之间的一个主要区别是，贪心算法不是首先找到子问题的最佳解决方案，然后做出明智的选择，而是首先做出贪婪的选择，即当时看起来最好的选择，然后解决结果子问题，无需费心解决所有可能相关的较小子问题。

于 2015-07-20T11:05:21.217 回答
1

贪心方法和动态规划之间的区别如下：

  1. 贪婪方法从不重新考虑其选择，而动态编程可能会考虑先前的状态。

  2. 贪心算法效率较低，而动态编程效率更高。

  3. 贪心算法对子问题进行局部选择，而动态编程将解决所有子问题，然后选择一个会导致最佳解决方案的子问题。

  4. 贪心算法一次做出决定，而动态编程在每个阶段都做出决定。

于 2018-10-27T01:28:11.117 回答
0

简单来说，我们可以说在Dynamic Programming（在网络上发送消息时遇到问题）可以首先检查花费最短时间的路径，然后开始旅程，

另一方面，当场Greedy algorithm采取行动optimal decision而不考虑下一步，然后在下一步再次改变决定，依此类推......

Notes: Dynamic programming是可靠的，而贪心算法并不总是可靠的。

于 2016-07-19T06:05:13.383 回答
0

参考Biswajit Roy：动态规划先规划后围棋。而贪心算法使用贪心选择，它先去然后不断地计划。

于 2018-11-06T16:53:44.377 回答
-1

贪心方法和动态规划之间的主要区别在于，贪心方法只能生成一个最优决策序列，而动态规划可能会生成多个最优决策序列。

于 2018-10-25T03:26:58.377 回答