10.4 贪心法

考虑一个应用问题：假设需要在油库 A 和加油站 B、C、D、E、F、G、H 之间修建输油管道，油库和各加油站的位置如图 10.6 所示，图中的虚线表示可能的管道铺设路线，虚线旁标注的数值表示所需铺设的管道的长度（千米）②。例如油库 A 与加油站 B 之间需要铺设 35 千米的管道。

图 10.6 油库及加油站位置示意图

显然没有必要在所有可能路线上铺设管道，而只需要各加油站直接或间接与油库连通即可。假设人手和资金比较紧张，工程只能分批分期进行，每期建设一条管道。我们该如何规划整个工程呢？

① 术语称为引用传递，以区别于普通的值传递。参见第 6 章。

② 此处的长度数据不一定是两点之间的直线距离，所以不要根据三角不等式（三角形中两边之和大于第三边）得出数据不合理的结论。

指导思想当然是又快又省钱。一种想法是尽可能快地使加油站投入使用，每一期工程都使一个加油站能够供油。那么，第一期必须在油库 A 与某个加油站之间铺设管道，问题是选哪个加油站呢？显然应该选择 B，因为在从 A 可直接到达的 B、C、D、E 中，AB 是最短的管道，可以在最短时间内建成，当然花费也是最少的。接下来考虑第二期工程时，可以选择一个从 A 或者 B 可到达的加油站，注意此时所选加油站不必与油库 A 直接相通，间接连通也能保证供油。C、D、E、G 都是从 A 或 B 可通达的加油站，其中 C 是最近的，因此我们选择 C，并铺设 B 和 C 之间的 15 千米管道。在工程的第三期，需要选择一个能与 A、B 或 C 可到达的加油站，这次最短的是 C 和 D 之间的 5 千米管道，因此选择 D 并铺设 CD 管道。到目前为止，工程进展如图 10.7 所示，图中实线段表示已经铺设的管道，B、C、D 都能供油了。

图 10.7 第三期工程后的状况依此类推，在接下去的第四期到第七期工程中，可以分别铺设 CG、GH、FH 和 FE 之间的管道。至此，所有加油站都通过输油管道与油库 A 连通了，如图 10.8 所示。工程规划者一定很满意，因为他们觉得自己在每一期建设中都选择了当时情况下最短的线路，从而能以最快时间完成那一期工程，使一个新加油站投入运营。当工程完工时，铺设管道的总长度是 150 千米。

图 10.8 完工后的状况

下面考虑另一种工程建设方案。工程规划者并不追求各加油站尽快投入使用，而一心只想以最小的投资完成工程。这时的指导思想是，每一期工程都尽可能选择当前所有线路中最短的线路来铺设管道，并确保最终能将油库和所有加油站连通起来。

按照这个思路，首先应该选择铺设 CD 管道，因为这条管道的长度是 5 千米，是所有管道线路中最短的。完成 CD 管道之后，剩余线路中最短的管道是 10 千米的 FH，因此选择它作为第二条铺设的管道。依此类推，接下去应该分别铺设 BC（15 千米）、GH（20 千米）和 CG（25 千米）等管道，至此工程现状如图 10.9 所示。

图 10.9 铺设五条最短管道之后的状况

按照上述思路接下来应该铺设当前最短的 CF 管道（30 千米），但由于 C 和 F 已经连入了输油管道系统，再铺设 CF 管道属于重复建设，因此我们放弃 CF 而选择铺设 AB 管道（35 千米）。最后一步铺设 EF 管道（40 千米），至此油库和所有加油站都连通了，如图 10.10 所示。

图 10.10 完工后的状况读者一定已经发现，第二种以省钱为指导思想的建设方案与第一种以尽快投入运营为指

导思想的建设方案所导致的输油管道系统是一样的，两者都铺设了总长度为 150 千米的管道。问题是这两种建设方案到底是不是最优的呢？会不会有一种管道总长度更小的方案呢？读者不妨试试其他选择，最终会发现任何其他将油库和加油站连接在一起的方案都导致总长度超过 150 千米的管道系统。所以，我们讨论的两种方案都导致了最优的（即总长度最小）输油管道系统。

不难看出，实际中的许多问题都可以利用上述方案来解决，如下水道系统、芯片设计、交通网、通信网等等。这些问题可以抽象成图论中的“最小支撑树”问题，上面两种解决方案其实是解决最小支撑树问题的两个著名算法的应用。

第一种方案称为 Prim 算法，其思想是从一个地点（如油库）出发，一个接一个地将其他地点（如加油站）连入系统，其中每一步都尽可能选择最短连接路线。Prim 算法的伪代码如下：

Prim 算法
1\. 初始时所有地点标记为不可通达。
2\. 选择一个特定地点，标记为可通达。
3\. 重复下列步骤，直至所有地点都被标记为可通达：
    选择距离最近的两个地点，其中一个地点的标记是可通达，另一个地点的标记是不可通 达。然后将这两个地点连接起来，并将原先不可通达的地点改标为可通达。

第二种策略称为 Kruskal 算法，其思想是每一步将当前距离最近且尚未连通的两个地点连接起来。如果某一步的当前最小长度线路所涉及的两个地点已经连通了，则放弃这个路线，接着考虑其后线路。算法伪代码如下：

Kruskal 算法 
重复以下步骤，直至所有地点都直接或间接地连通：
    将当前距离最近并且尚未连通的两个地点连接起来。

Prim 算法和 Kruskal 算法虽然是不同的解决方法，但他们都能产生最小支撑树。这两个算法其实反映了一个共同的算法设计方法——贪心法。贪心法指的是这样一种问题求解策略：在求解过程的每一步都尽量作出在当前情况下局部最优的选择，以期最终能得到全局最优解。例如 Prim 算法在每一步都选择当前与已连通部分最近的地点，Kruskal 算法在每一步都尽可能选择当前最短的线路，两者的最终目标都是构造最小支撑树。

贪心算法的一般模式是通过迭代（循环）来一步一步地进行贪心选择，从而产生一个局部最优解，并将问题简化为更小的问题，最终的全局解由所有局部解组成。即：

贪心算法模式
算法： 
输入：一个候选对象集合
输出：由某些候选对象组成的全局解 
重复以下步骤，直至得到全局解：
    从候选对象中选择当前最优者，并加入到局部解中

在迭代的每一步，贪心选择可以依赖于此前的迭代步骤中已经作出的选择，但不能依赖于未来的选择。打个比方，贪心选择就像一个每次只计算一步棋的棋手，他总是选择当前能获得最大利益的一步棋，而不考虑这步棋会不会在以后造成损失。显然，一步棋的好坏不能只取决于当前利益，而是要着眼全局。在贪心策略下，以后即使认识到前面某一步棋不佳，也是不允许悔棋的。可见，贪心算法具有“只看眼前利益”和“落子无悔”的两大特点。

当然，好的棋手是不会采用贪心策略来下棋的，他们会计算未来的很多步棋，然后选择全局最优的着法。这说明贪心策略只能对某些问题（如上述最小支撑树问题）能产生全局最优解，对另一些问题则不然。不过，贪心算法的优点是能够较快地找出解法，产生的结果经常也是接近全局最优解的；而一心追求全局最优解则有可能导致无法在合理的时间内达到目标，就像棋手如果指望算无遗策，那就要花费大量时间来计算着法，这几乎是不可能的。

最后顺便提一下，在前面的输油管道问题中，为了从油库 A 向加油站 E 供油，采用贪心算法设计出的方案是将 A 经 B、C、G、H、F 来与 E 连通，这条管线的总长度为 145 千米。而假如直接在 A 和 E 之间修一条管道的话只需要 80 千米！可见，如果待解决的问题是修建从油库到每一个加油站的最短管道，前述两个算法是不合适的。事实上，存在另一个采用贪心法设计的著名算法——Dijkstra 最短路径算法，可以很好地解决这个问题。