【译】贪心和动态规划算法

2 minute read

这是一个来自stack overflow的问题。

动态规划算法和贪心算法在使用上的主要区别是什么? 就我的理解来看,贪心算法有时候会给出最优解;在其他情况下,动态规划算法给出最优解(我觉得只要能使用动态规划算法,应该总是最优吧)。有没有在某种特定的情况下,我们必须使用一种或另一种才能获得最优解呢?

基于维基百科的文章.

贪心算法

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

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

动态规划算法

动态规划算法背后的思想非常简单。 一般来说,要解决一个给定的问题,我们便需要解决不同子问题, 然后子问题的解合并起来就是整体的解。通常当使用简单的方法时,会生成许多子问题并会产生重复计算。动态规划方法便寻求解决每个子问题只计算 一次,从而减少计算的次数:一旦计算出给定子问题的解决方案,它就会被存储或 记忆化:下一次再需要解的时候,便可以很简单的就查找到。当重复子问题的数量随着输入的大小呈指数增长时,这种方法特别有用。

不同

(根据)贪心算法的属性,我们可以做任何看起来最好的选择,然后解决后面出现的子问题。由贪心算法做出的选择可能取决于目前做出的选择,但不取决于未来的选择或子问题的所有解决方案。I它迭代地做出一个又一个贪婪的选择,将每个给定的问题简化成一个更小的问题。换句话说,一个贪婪算法永远不会重新考虑它的选择。

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

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

另一方面,贪婪算法会让你立即开始驾驶,并且会选择在每个路口看起来最快的那条路。正如你所能想象的,这种策略可能不会导致最快的到达时间,因为你可能会走一些“容易”的街道,然后发现自己无可救药地陷入交通堵塞。

一些其他细节…

在数学优化中,贪婪算法解决具有matroids属性的组合问题。 动态规划适用于具有重叠子问题性质和最优子结构的问题。

stackoverflow

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.