图 10.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 完工后的状况 读者一定已经发现，第二种以省钱为指导思想的建设方案与第一种以尽快投入运营为指

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

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

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

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

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

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

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

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