「贪心算法」的算法思路是什么，它存在什么缺陷？ 第1页

「贪心算法」顾名思义，就是说算法就像一个贪婪、鼠目寸光的人，在每次要做决策时，都做出当前看来最好的选择，最终所有选择形成一个解。

说它贪婪，是因为每次要做选择的时候，一定会选择现在看来是最优的选择；说它鼠目寸光，是因为每次做选择时，只考虑当前的局面而不考虑长远的利益。说到这儿，贪心算法的优点和缺点就不难看出了：

• 优点：做决策所需的计算复杂度较低。每次做决策的时候，都不用考虑长远的事情，拍脑袋就做出看起来最好的那个选择，自然不用算计很多呀。
• 缺点：最终得到的解不一定是最优解。这算法不懂得深谋远虑，自然可能走不到最好的结果啦。

那么「贪」它就一定不好吗？作为计算机珂学家，我们除了想感性的认识这个算法之外，还想弄清楚两件事情：

1. 什么情况下，贪心算法可以得到最优解？
2. 如果不是最优解，贪心算法得到的较优解有多好？

首先，我们通过几个例子研究一下在什么样的情况下贪心算法可以达到最优解。

我们先看一个比较简单的找零问题。

问题A：假设 Bob 有无限张100元、50元、20元、10元、5元、1元的纸币，现在 Bob 想给 Alice 找零 元，请问 Bob 最少要给她多少张纸币？

解法：我们从高面值往低面值依次尝试，对于每种面值都给 Alice 尽可能多的当前面值纸币，直到待找零金额小于当前面值。这种找零方法就是给出纸币最少的方法。

我们发现当问题足够简单，简单到没有必要有全局的考虑时，显然贪心算法可以有很好的效果，高效得到最优解。

我们再看一个较为复杂的问题（摘自 NOIP 2012）：

问题B：国王和 位大臣都在自己的左、右手上面分别写下一个整数。国王站在队伍的最前面，并安排所有的大臣排成一列队伍。每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数。请你安排大臣队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。

解法：将大臣左手与右手的数字相乘后从小到大排序，最优解时大臣应有的顺序。

这个问题乍一看情形十分复杂，直接考虑大臣们在序列中的顺序是困难的。我们转化一下考虑问题的角度，假设我们已经有了一个序列，然后交换这个序列中的大臣，使得获得奖赏最多的大臣的奖励不断减少，可以证明这样操作能够收敛到最优解。

进而，我们就可以很容易地导出现在这个贪心算法。这说明即使问题相对复杂，我们凭借对问题的理解使用优秀的策略，贪心算法依旧可以达到最优解。

最后，我们来看一看经典的背包问题。

问题C：你有一个可以承受重量上限为 的背包和 个物品，第 个物品的价值为 ，重量为 。在物品不可以分割且背包不可以超负荷的情况下，如何可以最大化背包中物品的价值。

面对这个问题，即使再优秀的贪心策略，也没有办法保证得到最优解。大致的想法是追求高价值（性价比）的物品是我们想要的，但同时不浪费过多背包的容积也是需要的，单一的贪心策略就无法兼顾了，这时候就必须使用动态规划算法才能够得到问题的最优解。

经过刚才的三个问题，可以明显的感觉到当在问题中，当前做选择不会影响未来做选择时，这个问题往往时可以通过贪心算法得到最优解的。总的来说，我们选择的贪心策略必须没有后效性，贪心算法往往能够达到最优解，而这一点性质是由问题和策略共同决定的。

继而，我们再来了解一下贪心算法如果不能达到最优解， 较优解可以有多好呢？（这里我们讨论一种特殊情况）

这里需要引入一个概念：子模性(Submodularity)。如果一个函数 ，对于 与 ，满足 ，那么这个函数就具有子模性。

在子模性的基础上，如果这个函数还满足单调性(Monotonicity)与非负性(Nonnegativity)。即在上文的环境中，函数还满足 。

如果原问题可以抽象成一个集合 的子集选择问题，即我们的目标是要找到一个集合 使得 最大，同时能够证明评估函数 具有子模性、单调性与非负性。

那么对于这个问题使用简单的贪心策略，每次选择都选择一个能够最大化当前评估函数的元素加入解集合，即对于第 次选择，解集合更新为 。最终，贪心算法得到的解 满足 。

贪心算法求得的较优解总能够满足是最优解的一个 近似。

这部分公式浓度有点高，所以我选择举一个例子：放置传感器。我们在一个房间里放置 个传感器，每个传感器的作用范围都是一个大小为 的圆，如何规划一个传感器放置策略使得所有传感器的总作用范围尽可能大。

在这个问题中，我们使用简单的贪心策略，放每个传感器的时候都选择可以最大化当前传感器独自作用范围的位置，就可以得到一个最优解的 近似。虽然我们没有得到最优解，但是我们可以以很低的计算代价得到一个最优解的近似，也是非常不错的。

所以，「贪」它就一定不好吗？

参考文献：

1. Submodularity in ML: New Directions
2. 怎么理解次模函数 submodular function？

《算法导论》第 16 章贪心算法开头的内容：

贪心算法在每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。

缺陷也很明显，就是很多时候局部最优的累积并不能保证实现全局最优。

举个简单的例子：

大学的时候你努力学习，把学分绩刷得很高；毕业进了单位，安心干活；提拔的时候按照要求，认真准备材料。

看起来每一步都是当前的局部最优解，但能不能达到全局最优呢？人无远虑，必有近忧，把眼光放长远，才不会被眼前的事情蒙蔽了双眼。

坚持劝退，让高位接盘的既得利益者颤抖吧。