第8章 贪婪算法

本章内容

学习如何处理不可能完成的任务：没有快速算法的问题（ NP完全问题）。

学习识别NP完全问题，以免浪费时间去寻找解决它们的快速算法。

学习近似算法，使用它们可快速找到NP完全问题的近似解。

学习贪婪策略——一种非常简单的问题解决策略。

8.1 教室调度问题

假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。

你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。

你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？

这个问题好像很难，不是吗？实际上，算法可能简单得让你大吃一惊。具体做法如下。

(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。

(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。

重复这样做就能找出答案！下面来试一试。美术课的结束时间最早，为10:00 a.m.，因此它就是第一堂课。

接下来的课必须在10:00 a.m.后开始，且结束得最早。

英语课不行，因为它的时间与美术课冲突，但数学课满足条件。最后，计算机课与数学课的时间是冲突的，但音乐课可以。

因此将在这间教室上如下三堂课。

很多人都跟我说，这个算法太容易、太显而易见，肯定不对。但这正是贪婪算法的优点——简单易行！贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。信不信由你，对于这个调度问题，上述简单算法找到的就是最优解！

显然，贪婪算法并非在任何情况下都行之有效，但它易于实现！下面再来看一个例子。

8.2 背包问题

假设你是个贪婪的小偷，背着可装35磅（ 1磅≈ 0.45千克）重东西的背包，在商场伺机盗窃各种可装入背包的商品。

你力图往背包中装入价值最高的商品，你会使用哪种算法呢？

同样，你采取贪婪策略，这非常简单。

(1) 盗窃可装入背包的最贵商品。

(2) 再盗窃还可装入背包的最贵商品，以此类推。

只是这次这种贪婪策略不好使了！例如，你可盗窃的商品有下面三种。

你的背包可装35磅的东西。音响最贵，你把它给偷了，但背包没有空间装其他东西了。

你偷到了价值3000美元的东西。且慢！如果不是偷音响，而是偷笔记本电脑和吉他，总价将为3500美元！

在这里， 贪婪策略显然不能获得最优解，但非常接近。下一章将介绍如何找出最优解。不过小偷去购物中心行窃时，不会强求所偷东西的总价最高，只要差不多就行了。

从这个示例你得到了如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。

练习

8.1 你在一家家具公司工作，需要将家具发往全国各地，为此你需要将箱子装上卡车。每个箱子的尺寸各不相同，你需要尽可能利用每辆卡车的空间，为此你将如何选择要装上卡车的箱子呢？请设计一种贪婪算法。使用这种算法能得到最优解吗？

8.2 你要去欧洲旅行，总行程为7天。对于每个旅游胜地，你都给它分配一个价值——表示你有多想去那里看看，并估算出需要多长时间。你如何将这次旅行的价值最大化？

请设计一种贪婪算法。使用这种算法能得到最优解吗？

下面来看最后一个例子。在这个例子中，你别无选择，只能使用贪婪算法。

8.3 集合覆盖问题

假设你办了个广播节目，要让全美50个州的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费 用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。

每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。

如何找出覆盖全美50个州的最小广播台集合呢？听起来很容易，但其实非常难。具体方法如下。

(1) 列出每个可能的广播台集合，这被称为幂集（ power set） 。可能的子集有2n个。

(2) 在这些集合中，选出覆盖全美50个州的最小集合。

问题是计算每个可能的广播台子集需要很长时间。由于可能的集合有2n个，因此运行时间为O(2n)。如果广播台不多，只有5～10个，这是可行的。但如果广播台很多，结果将如何呢？随着广播台的增多，需要的时间将激增。假设你每秒可计算10个子集，所需的时间将如下。

没有任何算法可以足够快地解决这个问题！怎么办呢？

近似算法

贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。

(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖的州，也没有关系。

(2) 重复第一步，直到覆盖了所有的州。

这是一种近似算法（ approximation algorithm） 。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：

速度有多快；

得到的近似解与最优解的接近程度。

贪婪算法是不错的选择，它们不仅简单，而且通常运行速度很快。在这个例子中，贪婪算法的运行时间为O(n2)，其中n为广播台数量。

下面来看看解决这个问题的代码。

\1. 准备工作

出于简化考虑，这里假设要覆盖的州没有那么多，广播台也没有那么多。 首先，创建一个列表，其中包含要覆盖的州。 states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) 我使用集合来表示要覆盖的州。集合类似于列表，只是同样的元素只能出现一次，即集合不 能包含重复的元素。例如，假设你有如下列表。 >>> arr = [1, 2, 2, 3, 3, 3] 并且你将其转换为集合。 >>> set(arr) set([1, 2, 3]) 在这个集合中， 1、 2和3都只出现一次。 还需要有可供选择的广播台清单，我选择使用散列表来表示它。 stations = {} stations["kone"] = set(["id", "nv", "ut"]) stations["ktwo"] = set(["wa", "id", "mt"]) stations["kthree"] = set(["or", "nv", "ca"]) stations["kfour"] = set(["nv", "ut"]) stations["kfive"] = set(["ca", "az"]) 其中的键为广播台的名称，值为广播台覆盖的州。在该示例中，广播台kone覆盖了爱达荷州、 内达华州和犹他州。所有的值都是集合。你马上将看到，使用集合来表示一切可以简化工作。 最后，需要使用一个集合来存储最终选择的广播台。 final_stations = set() \2. 计算答案 接下来需要计算要使用哪些广播台。根据右边的示意图， 你能确定应使用哪些广播台吗？ 正确的解可能有多个。你需要遍历所有的广播台，从中选 择覆盖了最多的未覆盖州的广播台。我将这个广播台存储在 best_station中。 best_station = None states_covered = set() for station, states_for_station in stations.items(): 你传入一个数组，它被转换为集合

states_covered是一个集合，包含该广播台覆盖的所有未覆盖的州。 for循环迭代每个广 播台，并确定它是否是最佳的广播台。下面来看看这个for循环的循环体。 covered = states_needed & states_for_station

if len(covered) > len(states_covered): best_station = station	你没见过的语法！它计算交集

states_covered = covered 其中有一行代码看起来很有趣。 covered = states_needed & states_for_station 它是做什么的呢？ \3. 集合 假设你有一个水果集合。 还有一个蔬菜集合。 有这两个集合后，你就可以使用它们来做些有趣的事情。 下面是你可以对集合执行的一些操作。

并集意味着将集合合并。 交集意味着找出两个集合中都有的元素（在这里，只有西红柿符合条件）。 差集意味着将从一个集合中剔除出现在另一个集合中的元素。 下面是一个例子。 >>> fruits = set(["avocado", "tomato", "banana"]) >>> vegetables = set(["beets", "carrots", "tomato"]) >>> fruits | vegetables set(["avocado", "beets", "carrots", "tomato", "banana"]) >>> fruits & vegetables set(["tomato"]) >>> fruits – vegetables set(["avocado", "banana"]) >>> vegetables – fruits 这里小结一下： 集合类似于列表，只是不能包含重复的元素； 你可执行一些有趣的集合运算，如并集、交集和差集。 \4. 回到代码 回到前面的示例。 下面的代码计算交集。 covered = states_needed & states_for_station covered是 一 个 集 合 ， 包 含 同 时 出 现 在states_needed和 states_for_station中的州；换言之，它包含当前广播台覆盖的 一系列还未覆盖的州！接下来，你检查该广播台覆盖的州是否比 best_station多。 if len(covered) > len(states_covered): best_station = station states_covered = covered 如果是这样的，就将best_station设置为当前广播台。最后，你在for循环结束后将 best_station添加到最终的广播台列表中。 并集 交集 差集 你觉得这行代码是做什么的呢？

final_stations.add(best_station) 你还需更新states_needed。由于该广播台覆盖了一些州，因此不用再覆盖这些州。 states_needed -= states_covered 你不断地循环，直到states_needed为空。这个循环的完整代码如下。 while states_needed: best_station = None states_covered = set() for station, states in stations.items(): covered = states_needed & states if len(covered) > len(states_covered): best_station = station states_covered = covered states_needed -= states_covered final_stations.add(best_station) 最后，你打印final_stations，结果类似于下面这样。 >>> print final_stations set(['ktwo', 'kthree', 'kone', 'kfive']) 结果符合你的预期吗？选择的广播台可能是2、 3、 4和5，而不是预期的1、 2、 3和5。下面来 比较一下贪婪算法和精确算法的运行时间。 练习 下面各种算法是否是贪婪算法。 8.3 快速排序。 8.4 广度优先搜索。 8.5 狄克斯特拉算法。

8.4 NP 完全问题

为解决集合覆盖问题，你必须计算每个可能的集合。

这可能让你想起了第1章介绍的旅行商问题。在这个问题中，旅行商需要前往5个不同的城市。

他需要找出前往这5个城市的最短路径，为此，必须计算每条可能的路径。

前往5个城市时，可能的路径有多少条呢？

8.4.1 旅行商问题详解

我们从城市数较少的情况着手。假设只涉及两个城市，因此可供选择的路线有两条。

这两条路线相同还是不同
你可能认为这两条路线相同，难道从旧金山到马林的距离与从马林到旧金山的距离不同 吗？不一定。有些城市（如旧金山）有很多单行线，因此你无法按原路返回。你可能需要离开 原路行驶一两英里才能找到上高速的匝道。因此，这两条路线不一定相同。

你可能心存疑惑：在旅行商问题中，必须从特定的城市出发吗？例如，假设我是旅行商。我 居住在旧金山，需要前往其他4个城市，因此我将从旧金山出发。 但有时候，不确定要从哪个城市出发。假设联邦快递将包裹从芝加哥发往湾区，包裹将通过 航运发送到联邦快递在湾区的50个集散点之一，再装上经过不同配送点的卡车。该通过航运发送 到哪个集散点呢？在这个例子中，起点就是未知的。因此，你需要通过计算为旅行商找出起点和 最佳路线。 在这两种情况下，运行时间是相同的。但出发城市未定时更容易处理，因此这里以这种情况为例。 涉及两个城市时，可能的路线有两条。 \1. 3个城市 现在假设再增加一个城市，可能的路线有多少条呢？ 如果从伯克利出发，就需前往另外两个城市。

从每个城市出发时，都有两条不同的路线，因此总共有6条路线。 因此涉及3个城市时，可能的路线有6条。 \2. 4个城市 我们再增加一个城市——弗里蒙特。现在假设从弗里蒙特出发。 130 第 8 章 贪婪算法 从弗里蒙特出发时，有6条可能的路线。这些路线与前面只有3个城市时计算的6条路线很像， 只是现在所有的路线都多了一个城市——弗里蒙特！这里有一个规律。假设有4个城市，你选择 一个出发城市——弗里蒙特后，还余下3个城市。而你知道，涉及3个城市时，可能的路线有6条。 从弗里蒙特出发时，有6条可能的路线，但还可以从其他任何一个城市出发。 可能的出发城市有4个， 从每个城市出发时都有6条可能的路线，因此可能的路线有4 × 6 = 24条。 你看出规律了吗？每增加一个城市，需要计算的路线数都将增加。 涉及6个城市时，可能的路线有多少条呢？如果你说720条，那就对了。 7个城市为5040条， 8 个城市为40 320条。 这被称为阶乘函数（ factorial function） ，第3章介绍过。 5! = 120。假设有10个城市，可能的 路线有多少条呢？ 10! = 3 628 800。换句话说，涉及10个城市时，需要计算的可能路线超过300万 条。正如你看到的，可能的路线数增加得非常快！因此，如果涉及的城市很多，根本就无法找出 旅行商问题的正确解。 旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短 的那个。这两个问题都属于NP完全问题。

近似求解
对旅行商问题来说，什么样的近似算法不错呢？能找到较短路径的算法就算不错。在继续 往下阅读前，看看你能设计出这样的算法吗？ 我会采取这样的做法：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还 没去的最近的城市。假设旅行商从马林出发。 总旅程为71英里。这条路径可能不是最短的，但也相当短了。

NP完全问题的简单定义是，以难解著称的问题，如旅行商问题和集合覆盖问题。很多非常 聪明的人都认为，根本不可能编写出可快速解决这些问题的算法。

8.4.2 如何识别 NP 完全问题

Jonah正为其虚构的橄榄球队挑选队员。他列了一个清单，指出了对球队的要求：优秀的四分卫，优秀的跑卫，擅长雨中作战，以及能承受压力 等。他有一个候选球员名单，其中每个球员都满足某些要求。 Jonah需要组建一个满足所有这些要求的球队，可名额有限。等等， Jonah突然间意识到，这不就是一个集合覆盖问题吗！

Jonah可使用前面介绍的近似算法来组建球队。

(1) 找出符合最多要求的球员。

(2) 不断重复这个过程，直到球队满足要求（或球队名额已满）。

NP完全问题无处不在！如果能够判断出要解决的问题属于NP完全问题就好了，这样就不用去寻找完美的解决方案，而是使用近似算法即可。但要判断问题是不是NP完全问题很难，易于解决的问题和NP完全问题的差别通常很小。例如，前一章深入讨论了最短路径，你知道如何找出从A点到B点的最短路径。

但如果要找出经由指定几个点的的最短路径，就是旅行商问题——NP完全问题。简言之，没办法判断问题是不是NP完全问题，但还是有一些蛛丝马迹可循的。 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。

涉及“所有组合”的问题通常是NP完全问题。

不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。

如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。

如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。

如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

练习

8.6 有个邮递员负责给20个家庭送信，需要找出经过这20个家庭的最短路径。请问这是一个NP完全问题吗？

8.7 在一堆人中找出最大的朋友圈（即其中任何两个人都相识）是NP完全问题吗？

8.8 你要制作美国地图，需要用不同的颜色标出相邻的州。为此，你需要确定最少需要使用多少种颜色，才能确保任何两个相邻州的颜色都不同。请问这是NP完全问题吗？

8.5 小结

• 贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
• 对于NP完全问题，还没有找到快速解决方案。
• 面临NP完全问题时，最佳的做法是使用近似算法。
• 贪婪算法易于实现、运行速度快，是不错的近似算法。