algorithm - 动态规划和贪心法有什么区别？

Question

动态规划和贪心法在使用方面的主要区别是什么？

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

是否有任何特定条件必须满足才能使用一种(或另一种)方法获得最佳解决方案？

Answer 1

基于维基百科的文章。

贪心法

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

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

动态编程

动态规划背后的思想非常简单。一般来说，要解决一个给定的问题，我们需要解决问题的不同部分(子问题)，然后将子问题的解决方案组合起来以达到整体解决方案。通常在使用更朴素的方法时，会多次生成和解决许多子问题。动态规划方法试图仅解决一次每个子问题，从而减少计算次数:一旦计算出给定子问题的解决方案，它就会被存储或“备忘录” -ized”:下次需要相同的解决方案时，只需查找即可。当重复子问题的数量作为输入大小的函数呈指数增长时，这种方法特别有用。

区别

贪心选择属性

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

这是与动态规划的主要区别，动态规划是穷举的并且保证找到解决方案。每一个阶段结束后，动态规划都会根据前一阶段的所有决策进行决策，并可能重新考虑前一阶段的算法求解路径。

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

另一方面，贪心算法会立即让您开始驾驶，并会在每个十字路口选择看起来最快的道路。您可以想象，这种策略可能不会带来最快的到达时间，因为您可能会走一些“轻松”的街道，然后发现自己无可救药地陷入交通拥堵。

一些其他细节...

在数学优化中，贪心算法解决具有 matroids 属性的组合问题.

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