每日科技名词|贪婪算法

情毒

贪婪算法

greedy algorithm

又称：贪心算法

定义：一种不追求全局最优解，只在每一步求得局部最优解的算法。

学科：计算机科学技术_理论计算机科学_算法设计与分析

相关名词：算法 最优子结构性


图片来源： 视觉中国

【延伸阅读】

贪婪算法是一种用于优化问题的简单、直观的算法。该算法在每个步骤进行最优选择，试图找到解决整个问题的总体最优方法。贪婪算法每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，在一些最优解问题的求解上表现得更简单、更迅速。

如果求解问题具有贪婪选择属性与最优子结构属性，则可以使用贪婪算法解决。贪婪选择属性是指通过在每个步骤中选择最优选择，可以得到一个全局（总体）最优解。最优子结构是指如果整个问题的最优解包含子问题的最优解，那么问题就有最优子结构。

想象我们要进行一场徒步旅行，目标是到达可能的最高峰。在开始之前我们已经有了地图，但是地图上显示了多条可能的路径。我们没有时间去评估每条路径，就采取贪婪算法，只选择坡度最大的路径。这似乎是一个很好的远足策略，但它总是最好的吗？旅行结束后，我们再次查看远足地图，可能会发现那里有一条泥泞的河，穿过它就能更容易到达峰顶。这意味着贪婪算法总是选择最好的即时路径，而不一定是最终的最佳路径。在优化解决方案方面，这意味着贪婪的解决方案在尝试寻找局部最优解时，可能错过了一个全局最优解。

有很多经典的应用，比如霍夫曼编码，普利姆和克鲁斯卡尔最小生成树算法，还有迪杰斯特拉单源最短路径算法，都是使用了这种思维。然而，在许多问题中，贪婪算法并不会产生最优解，因为贪婪算法没有考虑到所有的数据，当前结果都是基于它前一步的数据而计算出的局部最优结论，缺乏瞻前顾后和统筹全局的能力。所以在贪婪算法失败的问题中，动态规划可能会是更好的选择。

（延伸阅读作者：大连理工大学计算机科学与技术学院教授 杨鑫）