在使用上，动态规划和贪心算法的主要区别是什么?
据我了解，贪心算法有时会给出最优解；而在其他情况下，动态规划会给出最优解。
是否需要满足特定条件以使用一种方法（或另一种方法）获得最优解？
6个回答
91
基于维基百科的文章。
贪心算法
贪心算法是一种遵循问题解决启发式的算法，在每个阶段都采取本地最优选择，希望找到全局最优解。在许多问题中，贪心策略通常不会产生最优解，但是贪心启发式可以在合理时间内产生近似全局最优解的局部最优解。
我们可以在每个阶段做出任何看起来最好的选择，然后解决随后出现的子问题。贪心算法所做的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或所有子问题的解决方案。它迭代地一个接一个地做出贪心选择，将每个给定的问题化简为一个较小的问题。
动态规划
动态规划背后的思想非常简单。通常，为了解决给定问题，我们需要解决问题的不同部分（子问题），然后组合子问题的解决方案以达到整体解决方案。使用更加天真的方法时，很多子问题都会被重复生成和解决。动态规划方法仅寻求解决每个子问题一次，从而减少计算量：一旦计算出给定子问题的解决方案，它就被存储或“记忆化”：下一次需要相同解决方案时，只需查找即可。当重复子问题的数量随输入大小的增长呈指数级增长时，此方法特别有用。
差异
贪心选择性质
我们可以在每个阶段做出任何看起来最好的选择，然后解决随后出现的子问题。贪心算法所做的选择可能取决于到目前为止所做的选择，但不取决于未来的选择或所有子问题的解决方案。它迭代地一个接一个地做出贪心选择，将每个给定的问题化简为一个较小的问题。换句话说，贪心算法永远不会重新考虑其选择。
这是与动态规划最大的区别，动态规划是穷举法，能保证找到解决方案。每个阶段后，动态规划都会根据之前所有阶段作出的决策来做出决策，并可能重新考虑先前阶段的算法路径。
例如，假设你必须在拥堵时间内尽快从A点到达B点。 动态规划算法将查看整个交通报告，研究你可能采取的所有道路组合，然后只告诉你哪条路线最快。 当然，你可能需要等待一段时间，直到算法完成，然后才能开始行驶。 你将采取的路径将是最快的（假设外部环境没有变化）。
另一方面，贪心算法会立即让你开始行驶，并选择在每个十字路口看起来最快的道路。 你可以想象，这种策略可能不会导致最快到达时间，因为你可能会走一些“容易”的街道，然后发现自己在交通堵塞中陷入困境。
其他细节...
在数学优化中，贪心算法解决了具有拟阵属性的组合问题。
动态规划适用于具有重叠子问题和最优子结构属性的问题。
- Imposter
25
我想引用一段文字，它描述了在Cormen的书算法导论（第三版）第15.3章第381页中所述的贪心算法和动态规划算法之间的主要区别：
贪心算法和动态规划算法之间的一个主要区别是，贪心算法不是首先找到子问题的最优解，然后做出明智的选择，而是首先做出一种贪心选择——看起来最好的选择，然后解决产生的子问题，而不必解决所有可能相关的更小的子问题。
- nbro
1
下面给出贪心算法和动态规划之间的区别：
贪心算法从不重新考虑其选择，而动态规划可能考虑先前的状态。
贪心算法效率较低，而动态规划效率更高。
贪心算法具有子问题的局部选择性，而动态规划将解决所有子问题，然后选择导致最优解的一个。
贪心算法在一次决策中做出决定，而动态规划在每个阶段都做出决策。
- rashedcs
0
简单来说，在动态规划中（在网络上发送消息时出现问题），我们可以首先检查需要最短时间的路径，然后开始旅程。
另一方面，贪心算法会立即做出最优决策，而不考虑下一步，然后在下一步再次改变其决策，以此类推...
注意：动态规划是可靠的，而贪心算法并不总是可靠。
另一方面，贪心算法会立即做出最优决策，而不考虑下一步，然后在下一步再次改变其决策，以此类推...
注意：动态规划是可靠的，而贪心算法并不总是可靠。
- Imad Gohar
0
参考Biswajit Roy的观点： 动态规划首先进行规划，然后再执行。 而贪心算法则是采用贪心策略，首先执行，然后不断规划。
- Abhay SIngh
-1
贪心算法和动态规划的主要区别在于，贪心算法仅生成一个最优决策序列，而动态规划可能生成多个最优决策序列。
- user10555437
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接