Imp*_*ter 69
基于维基百科的文章.
贪婪算法是一种算法,它遵循问题求解启发式,在每个阶段进行局部最优选择,希望找到全局最优.在许多问题中,贪婪策略通常不会产生最优解,但是贪婪的启发式算法可能会产生局部最优解,在合理的时间内逼近全局最优解.
我们可以做出目前最好的选择,然后解决后来出现的子问题.贪婪算法做出的选择可能取决于目前为止做出的选择,而不取决于未来的选择或子问题的所有解决方案.它迭代地使一个接一个的贪婪选择,将每个给定的问题减少为一个较小的问题.
动态编程背后的想法非常简单.一般来说,为了解决给定的问题,我们需要解决问题的不同部分(子问题),然后结合子问题的解决方案来达到整体解决方案.通常在使用更天真的方法时,会产生并解决许多子问题.动态编程方法只寻求解决每个子问题一次,从而减少计算次数:一旦计算出给定子问题的解,就存储或"备忘":下次需要相同的解决方案时,只是抬起头来.当重复子问题的数量随着输入的大小呈指数增长时,这种方法特别有用.
我们可以做出目前最好的选择,然后解决后来出现的子问题.贪婪算法做出的选择可能取决于目前为止做出的选择,而不取决于未来的选择或子问题的所有解决方案.它迭代地使一个接一个的贪婪选择,将每个给定的问题减少为一个较小的问题.换句话说,贪婪算法从不重新考虑其选择.
这是与动态编程的主要区别,动态编程是详尽的,并保证找到解决方案.在每个阶段之后,动态编程基于前一阶段做出的所有决策做出决策,并可能重新考虑前一阶段的解决方案算法路径.
例如,假设您必须在高峰时段内在特定城市尽可能快地从A点到达B点.动态编程算法将查看整个流量报告,查看您可能采取的所有可能的道路组合,然后才会告诉您哪种方式最快.当然,您可能需要等待一段时间,直到算法结束,然后才能开始驾驶.您将采用的路径是最快的路径(假设外部环境没有任何变化).
另一方面,贪婪的算法将立即开始你的驾驶,并将选择在每个交叉路口看起来最快的道路.你可以想象,这种策略可能不会带来最快的到达时间,因为你可能会走一些"简单"的街道,然后发现自己无可救药地陷入交通拥堵.
在数学优化中,贪婪算法解决具有拟阵特性的组合问题.
动态规划适用于表现出重叠子问题和最优子结构特性的问题.
nbr*_*bro 16
我想引用一段描述贪婪算法和动态编程算法之间的主要区别,这些算法由Cormen的" 算法导论"(第3版),第15.3章,第381页中所述:
贪婪算法和动态编程之间的一个主要区别在于,贪婪算法不是首先找到子问题的最优解,而是做出明智的选择,而是首先做出贪婪的选择,当时看起来最好的选择,然后解决由此产生的子问题,无需费心去解决所有可能相关的较小子问题.