Greedy Algorithm 这个命名一看到时就觉得很有意思！为什么叫做贪婪呢？

什么是贪婪算法？

贪婪算法根据Wikipedia的定义：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

这听起来和印象中的“贪婪”似乎差很多嘛！不是七宗罪里那个贪婪嘛。我们通常理解的贪婪，是对财物、钱等物品充满非同寻常的强烈欲望。不过，换个角度来理解，会有点不同。假如我们忽视全局和总体规划，就是说我们放弃做某件事的最优选择，只是盯着眼前的一点一滴得失，即是当前的最优选择，往往贪婪的人也就是因为无法控制欲望，不能退后一步看问题，是短视的。这样来看，两种解释似乎融会贯通起来了。

不过贪婪算法可不是无用的东西。它是解决NP问题的有效方式之一。

要是对算法什么的不感兴趣，直接略过，来聊聊 “#贪婪是坏的吗？” 也很有趣。

NP问题

NP = Non-Deterministic Polynomial （多项式复杂程度的非确定性问题）。

不是学数学的话，定义挺起来挺绕口的。简单来说的话，先有 P问题（确定性多项式算法），这类问题我们可以根据公式推导，得出结果，譬如计算 5*25／36+323。而 NP问题 问题，我们没有公式可以按部就班地通过计算得到结果。比如，寻找质数，我们没有公式可以一步步推算下一个质数应该是多少？比如经典的旅行商问题，有一个旅行商需要前往N个城市，怎么能找到最佳路径保证行程最短？再比如广播电台问题，在N家电台里，选择最小数量的电台，并做到播出的范围覆盖整个国家。对于这些无解的NP问题，数学家而言要么找到一个解决的算法，要么得证明为什么无解。作为七个“千僖年数学难题”中的一个，我们就不必杀死脑细胞求解了。

识别NP问题

虽然不用求解，可识别NP问题，却是非常有必要的！毕竟知道什么问题属于NP，我们就可以节省一些脑细胞了。《算法图解》提示了我们一些蛛丝马迹：

• 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。（比如商旅问题里的城市数量增加）
• 涉及“所有组合”的问题通常是NP问题
• 不能将问题分成小问题，必须考虑各种可能的情况。可能是NP问题
• 如果问题涉及序列（如商旅问题里的城市序列）且难以解决，可能是NP问题
• 如果问题涉及集合（如广播电台集合）且难以解决，可能是NP问题
• 如果问题可以转换为集合覆盖或者商旅问题，那肯定是NP问题

近似算法

对付NP问题，我们既然找不到最优解，那么一个“差不多，足够好”的解就可以满足条件了。贪婪算法就是个不错的解决方案。

对于旅行商问题，我们可以每次选择去最近的城市。对于广播电台问题，我们可以每次找到覆盖了最多的还没有播出地区的电台即可。

于是当前的最优选择，已经足够好了，而且速度快，是实际可行的操作。所以“贪婪”也不见得那么坏呀？至少在算法里的确不坏。那我们生活中的贪婪呢？

贪婪是坏的嘛？

其实不止贪婪，我们所谓的七宗原罪：“暴食”、“贪婪”、“懒惰”、“嫉妒”、“骄傲”、“淫欲”、“愤怒” 都值得在回头想想。

我们身边都是超过了身体需求，摄取无度的Foodie，那么是否可以说人人都“暴食”，或者是追求美好生活？做程序的都知道，最好的Hacker都是最“懒惰”的，才能创造出“智能”的机器；没有“贪婪”“嫉妒”我想经济就别想发展起来了。仔细掰掰就会发现，这些原罪本身也就像“科技”一样，是中立无态度的，更多像是催化剂和助推器，于是用到好的地方就造福，用到坏的地方就做恶 …

既然叫做原罪，即使人而为人就无法摆脱的，无法逃避的。记得知乎有个文章提过，能感受到多种负面情绪的人，比只有正面情绪的人健康，更少被诊断出抑郁。负面情绪更能积极地促使我们行动，相比起追逐更多快乐的动机，我们摆脱眼下的难耐的痛苦的动机往往更加强烈。

当然这七宗罪并不能和负面情绪完全画上等号。他们既是负面的情绪，也包括负面情绪的带来的实际动作。负面情绪比这7个多多了，譬如还有很危险的空洞情绪：

• 无望感（hopelessness）： 信念遭到破坏，失去控制感，产生“怎么努力也没用”、“希望的不会发生”的预期。如此一来，我们可能会放弃采取行动。更糟糕的是，放弃尝试和努力可能导致我们的预期成真，形成恶性循环。
• 无价值感（worthlessness）： 来源于没完没了的自我批评，认为自我的存在没有任何意义和价值。于是不由自主地去追逐财富、权力、名望这些普遍被认可的外在事物。然而，即使他们拥有了这些，内心依然是空虚的。

如果是由这样的情感反馈到七宗罪的行动当中，那可就真是“罪”了。

无论如何，Greedy Algorithm还真是个不错的名字，很有趣！它也印证了上面的讨论，对于那些无解的问题，即使是贪婪的，也比放弃尝试或者一门心思把时间荒废空洞里更值得推崇。