## 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 最短路径算法，可以很好地解决这个问题。