当前位置： >>
算法设计与分析-贪婪算法
第 1 章 贪婪算法虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决 许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下， 为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达 到要求，这时就必须寻求另外的方法来求解该问题。 本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货 箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方 案。 1.1 最优化问题 本章及后续章节中的许多例子都是最优化问题 optimization problem） 每个最优化问题都包含一组限 （ ， 制条件（ c o n s t r a i n t）和一个优化函数（ optimization function） ，符合限制条件的问题求解方案称为可 行解（ feasible solution） ，使优化函数取得最佳值的可行解称为最优解（optimal solution） 。 例 1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐 不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到 n 种不同的饮料。根据以前关于 这 n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种 饮料赋予一个满意度值：饮用 1 盎司第 i 种饮料，对它作出相对评价，将一个数值 si 作为满意度赋予第 i 种饮料。 通常， 这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要， 但是不幸的是： 具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设 ai 是第 i 种饮料的总量（以盎 司为单位） ，而此婴儿需要 t 盎司的饮料来解渴，那么，需要饮用 n 种不同的饮料各多少量才能满足婴儿解 渴的需求呢？ 设各种饮料的满意度已知。令 xi 为婴儿将要饮用的第 i 种饮料的量，则需要解决的问题是： 找到一组实数 xi（1≤i≤n） ，使 n ?i = 1si xi 最大，并满足：n ?i=1xi =t 及 0≤xi≤ai 。 需要指出的是：如果 n ?i = 1ai & t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使 婴儿解渴。 对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输 出作如下形式的描述： 输入：n，t，si ，ai（其中 1≤i≤n，n 为整数，t、si 、ai 为正实数） 。 输出：实数 xi（1≤i≤n） ，使 n ?i= 1si xi 最大且 n ?i=1xi =t（0≤xi≤ai） 。如果 n ?i = 1ai &t，则输出适 当的错误信息。 在这个问题中，限制条件是 n ?i= 1xi =t 且 0≤xi≤ai，1≤i≤n。而优化函数是 n ?i= 1si xi 。任何满足 限制条件的一组实数 xi 都是可行解，而使 n ?i= 1si xi 最大的可行解是最优解。 例 1-2 [装载问题] 有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一 样，但货箱的重量都各不相同。设第 i 个货箱的重量为 wi（1≤i≤n） ，而货船的最大载重量为 c，我们的 目的是在货船上装入最多的货物。 这个问题可以作为最优化问题进行描述：设存在一组变量 xi ，其可能取值为 0 或 1。如 xi 为 0，则货 箱 i 将不被装上船；如 xi 为 1，则货箱 i 将被装上船。我们的目的是找到一组 xi ，使它满足限制条件 n ?i = 1wi xi ≤c 且 x i ? {0, 1}, 1 ≤i≤n。相应的优化函数是 n ?i= 1xi 。 满足限制条件的每一组 xi 都是一个可行解，能使 n ?i= 1xi 取得最大值的方案是最优解。 例 1-3 [最小代价通讯网络] 城市及城市之间所有可能的通信连接可被视作一个无向图，图的每条边都 被赋予一个权值，权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点（城市） 的连通子图都是一个可行解。设所有的权值都非负，则所有可能的可行解都可表示成无向图的一组生成树， 而最优解是其中具有最小代价的生成树。1在这个问题中，需要选择一个无向图中的边集合的子集，这个子集必须满足如下限制条件：所有的边 构成一个生成树。而优化函数是子集中所有边的权值之和。 1.2 算法思想 在贪婪算法（greedy method）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的 决策（在一定的标准下） 。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（ greedy criterion） 。 例 1-4 [找零钱] 一个小孩买了价值少于 1 美元的糖，并将 1 美元的钱交给售货员。售货员希望用数目 最少的硬币找给小孩。假设提供了数目不限的面值为 2 5 美分、1 0 美分、5 美分、及 1 美分的硬币。售货 员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零 钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数） ，所选择的硬币不应使零钱总数 超过最终所需的数目。 假设需要找给小孩 6 7 美分， 首先入选的是两枚 2 5 美分的硬币， 第三枚入选的不能是 2 5 美分的硬币， 否则硬币的选择将不可行（零钱总数超过 6 7 美分） ，第三枚应选择 1 0 美分的硬币，然后是 5 美分的，最 后加入两个 1 美分的硬币。 贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的 数目） 。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习 1） 。 例 1-5 [机器调度] 现有 n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时 间为 si，完成时间为 fi ，si & fi 。[si , fi ] 为处理任务 i 的时间范围。两个任务 i，j 重指两个任务的时间 范围区间有重叠，而并非是指 i，j 的起点或终点重合。例如：区间[ 1，4 ]与区间[ 2，4 ]重叠，而与区间[ 4， 7 ]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分 配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。 假设有 n= 7 件任务，标号为 a 到 g。它们的开始与完成时间如图 13-1a 所示。若将任务 a 分给机器 M1， 任务 b 分给机器 M2，. . .，任务 g 分给机器 M7，这种分配是可行的分配，共使用了七台机器。但它不是 最优分配，因为有其他分配方案可使利用的机器数目更少，例如：可以将任务 a、b、d 分配给同一台机器， 则机器的数目降为五台。 一种获得最优分配的贪婪方法是逐步分配任务。每步分配一件任务，且按任务开始时间的非递减次序 进行分配。若已经至少有一件任务分配给某台机器，则称这台机器是旧的；若机器非旧，则它是新的。在 选择机器时，采用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则将任务分给旧 的机器。否则，将任务分配给一台新的机器。 根据例子中的数据，贪婪算法共分为 n = 7 步，任务分配的 顺序为 a、f、b、c、g、e、d。第一步没有旧机器，因此将 a 分配给一台新机器（比如 M1） 。这台机器在 0 到 2 时刻处于忙状态。在第二步，考虑任务 f。由于当 f 启动时旧机器仍处于忙状态，因此将 f 分配给一 台新机器(设为 M2 )。第三步考虑任务 b, 由于旧机器 M1 在 Sb = 3 时刻已处于闲状态，因此将 b 分配给 M1 执行，M1 下一次可用时刻变成 fb = 7，M2 的可用时刻变成 ff = 5。第四步，考虑任务 c。由于没有旧 机器在 Sc = 4 时刻可用，因此将 c 分配给一台新机器（M3） ，这台机器下一次可用时间为 fc = 7。第五步 考虑任务 g， 将其分配给机器 M2， 第六步将任务 e 分配给机器 M1, 最后在第七步， 任务 2 分配给机器 M3。 （注意：任务 d 也可分配给机器 M2） 。 上述贪婪算法能导致最优机器分配的证明留作练习（练习 7） 。可按如下方式实现一个复杂性为 O (nl o gn)的贪婪算法： 首先采用一个复杂性为 O (nl o gn)的排序算法 （如堆排序） Si 的递增次序排列各个任务， 按 然后使用一个关于旧机器可用时间的最小堆。 例 1-6 [最短路径] 给出一个有向网络，路径的长度定义为路径所经过的各边的耗费之和。要求找一条 从初始顶点 s 到达目的顶点 d 的最短路径。 贪婪算法分步构造这条路径， 每一步在路径中加入一个顶点。 假设当前路径已到达顶点 q， 且顶点 q 并 不是目的顶点 d。加入下一个顶点所采用的贪婪准则为：选择离 q 最近且目前不在路径中的顶点。这种贪2婪算法并不一定能获得最短路径。例如，假设在图 1 3 - 2 中希望构造从顶点 1 到顶点 5 的最短路径，利用 上述贪婪算法，从顶点 1 开始并寻找目前不在路径中的离顶点 1 最近的顶点。到达顶点 3，长度仅为 2 个 单位，从顶点 3 可以到达的最近顶点为 4，从顶点 4 到达顶点 2，最后到达目的顶点 5。所建立的路径为 1 , 3 , 4 , 2 , 5，其长度为 1 0。这条路径并不是有向图中从 1 到 5 的最短路径。事实上，有几条更短的路径存 在，例如路径 1，4，5 的长度为 6。 根据上面三个例子，回想一下前几章所考察的一些应用，其中有几种算法也是贪婪算法。例如，霍夫 曼树算法，利用 n- 1 步来建立最小加权外部路径的二叉树，每一步都将两棵二叉树合并为一棵，算法中所 使用的贪婪准则为：从可用的二叉树中选出权重最小的两棵。L P T 调度规则也是一种贪婪算法，它用 n 步 来调度 n 个作业。首先将作业按时间长短排序，然后在每一步中为一个任务分配一台机器。选择机器所利 用的贪婪准则为：使目前的调度时间最短。将新作业调度到最先完成的机器上（即最先空闲的机器） 。 注意到在机器调度问题中，贪婪算法并不能保证最优，然而，那是一种直觉的倾向且一般情况下结果 总是非常接近最优值。它利用的规则就是在实际环境中希望人工机器调度所采用的规则。算法并不保证得 到最优结果，但通常所得结果与最优解相差无几，这种算法也称为启发式方法（ h e u r i s t i c s )。因此 L P T 方法是一种启发式机器调度方法。定理 9 - 2 陈述了 L P T 调度的完成时间与最佳调度的完成时间之间的 关系，因此 L P T 启发式方法具有限定性能（ bounded performance ） 。具有限定性能的启发式方法称为近 似算法（ a p p r o x i m a t i o na l g o r i t h m） 。 本章的其余部分将介绍几种贪婪算法的应用。在有些应用中，贪婪算法所产生的结果总是最优的解 决方案。但对其他一些应用，生成的算法只是一种启发式方法，可能是也可能不是近似算法。 1.3.1 货箱装船 这个问题来自例 1 - 2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。根据这种思 想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序可以保证所选的货箱总重 量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择最轻的货箱，然后选次轻的货箱，如此 下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。 例 1-7 假设 n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用贪婪算法时，所考察货箱的 顺序为 7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱 7 , 3 , 6 , 8 , 4 , 1 的总重量为 3 9 0 个单位且已被装载，剩下的装载能力 为 1 0 个单位， 小于剩下的任何一个货箱。 在这种贪婪解决算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ] 且?xi = 6。 定理 1-1 利用贪婪算法能产生最佳装载。 证明可以采用如下方式来证明贪婪算法的最优性： x = [x1 , ..., xn ]为用贪婪算法获得的解， y =[ y1 , ..., 令 令 yn ]为任意一个可行解，只需证明 n ?i= 1xi ≥n ?i= 1yi 。不失一般性，可以假设货箱都排好了序：即 wi≤ wi + 1（1≤i≤n） 。然后分几步将 y 转化为 x，转换过程中每一步都产生一个可行的新 y，且 n ?i = 1yi 大 于等于未转化前的值，最后便可证明 n ?i = 1xi ≥n ?j = 1yi 。 根据贪婪算法的工作过程， 可知在[0, n] 的范围内有一个 k， 使得 xi =1, i≤k 且 xi =0, i&k。 寻找[ 1 ,n] 范围内最小的整数 j，使得 xj≠yj 。若没有这样的 j 存在，则 n ?i= 1xi =n ?i = 1yi 。如果有这样的 j 存在， 则 j≤k，否则 y 就不是一个可行解，因为 xj≠yj ，xj = 1 且 yj = 0。令 yj = 1，若结果得到的 y 不是可行解， 则在[ j+ 1 ,n]范围内必有一个 l 使得 yl = 1。令 yl = 0，由于 wj≤wl ，则得到的 y 是可行的。而且，得到 的新 y 至少与原来的 y 具有相同数目的 1。 经过数次这种转化， 可将 y 转化为 x。 由于每次转化产生的新 y 至少与前一个 y 具有相同数目的 1， 因此 x 至少与初始的 y 具有相同的数目 1。 货箱装载算法的 C + +代码实现见程序 1 3 - 1。 由于贪婪算法按 货箱重量递增的顺序装载，程序 1 3 - 1 首先利用间接寻址排序函数 I n d i r e c t S o r t 对货箱重量进行排序 （见 3 . 5 节间接寻址的定义）随后货箱便可按重量递增的顺序装载。 ， 由于间接寻址排序所需的时间为 O (nl o gn)（也可利用 9 . 5 . 1 节的堆排序及第 2 章的归并排序） ，算法其余部分所需时间为 O (n)，因此程序 1 3 -31 的总的复杂性为 O (nl o gn)。 程序 13-1 货箱装船 template&class T& void ContainerLoading(int x[], T w[], T c, int n) {// 货箱装船问题的贪婪算法 // x[i] = 1 当且仅当货箱 i 被装载， 1&=i&=n // c 是船的容量, w 是货箱的重量 // 对重量按间接寻址方式排序 // t 是间接寻址表 int *t = new int [n+1]; I n d i r e c t S o r t ( w, t, n); // 此时, w[t[i]] &= w[t[i+1]], 1&=i&n // 初始化 x for (int i = 1; i &= i++) x[i] = 0; // 按重量次序选择物品 for (i = 1; i &= n && w[t[i]] &= i++) { x[t[i]] = 1; c -= w[t[i]];} // 剩余容量 delete [] } 1.3.2 0/1 背包问题 在 0 / 1 背包问题中，需对容量为 c 的背包进行装载。从 n 个物品中选取装入背包的物品，每件物品 i 的重量为 wi ，价值为 pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是 指所装入的物品价值最高，即 n ?i=1pi xi 取得最大值。约束条件为 n ?i =1wi xi≤c 和 xi?[ 0 , 1 ] ( 1≤i≤n)。 在这个表达式中，需求出 xt 的值。xi = 1 表示物品 i 装入背包中，xi =0 表示物品 i 不装入背包。0 / 1 背 包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形 式为：船作为背包，货箱作为可装入背包的物品。 例 1-8 在杂货店比赛中你获得了第一名，奖品是一车免 费杂货。店中有 n 种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为 c，物品 i 需占 用 wi 的空间，价值为 pi 。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量， 且同一种物品不得拿走多件。这个问题可仿照 0 / 1 背包问题进行建模，其中车对应于背包，货物对应于物 品。 0 / 1 背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中 利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大 的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量） ，然后是下一个价值最大的物品， 如此继续下去。这种策略不能保证得到最优解。例如，考虑 n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。当 利用价值贪婪准则时，获得的解为 x= [ 1 , 0 , 0 ]，这种方案的总价值为 2 0。而最优解为[ 0 , 1 , 1 ]，其总价 值为 3 0。 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对 于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑 n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为 x =[1,0], 比最优解[ 0 , 1 ]要差。 还可以利用另一方案，价值密度 pi /wi 贪婪算法，这种选择准则为：从剩余物品中选择可装入包的4pi /wi 值最大的物品，这种策略也不能保证得到最优解。利用此策略试解 n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。 我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧， 0 / 1 背包问题是一个 N P-复杂问 题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按 pi /wi 非递（增）减的次序装 入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数 时候能很好地接近最后算法。在 6 0 0 个随机产生的背包问题中，用这种启发式贪婪算法来解有 2 3 9 题为 最优解。有 5 8 3 个例子与最优解相差 1 0 %，所有 6 0 0 个答案与最优解之差全在 2 5 %以内。该算法能在 O (nl o gn)时间内获得如此好的性能。我们也许会问，是否存在一个 x (x&1 0 0 )，使得贪婪启发法的结果与 最优值相差在 x%以内。答案是否定的。为说明这一点，考虑例子 n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和 c= y。 贪婪算法结果为 x=[1,0], 这种方案的值为 1 0。对于 y≥1 0 / 9，最优解的值为 9 y。因此，贪婪算法的值与 最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %，对于大的 y，这个值趋近于 1 0 0 %。但是可以建立 贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的 x% (x&100) 之内。首先将最多 k 件 物品放入背包， 如果这 k 件物品重量大于 c， 则放弃它。 否则， 剩余的容量用来考虑将剩余物品按 pi /wi 递 减的顺序装入。通过考虑由启发法产生的解法中最多为 k 件物品的所有可能的子集来得到最优解。 例 13-9 考虑 n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。 k= 0 时， 当 背包按物品价值密度非递减顺序装入， 首先将物品 1 放入背包，然后是物品 2，背包剩下的容量为 5 个单元，剩下的物品没有一个合适的，因此 解为 x = [ 1 , 1 , 0 , 0 ]。此解获得的价值为 1 6。 现在考虑 k = 1 时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }产生与 k= 0 时相同的结果，考虑子集{ 3 }，置 x3 为 1。此时还剩 5 个单位的容量，按价值密度非递增顺序来考虑如何 利用这 5 个单位的容量。首先考虑物品 1，它适合，因此取 x1 为 1，这时仅剩下 3 个单位容量了，且剩余 物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为 x = [ 1 , 0 , 1 , 0 ]，获得的价值为 1 8。 若从子集{ 4 }开始，产生的解为 x = [ 1 , 0 , 0 , 1 ]，获得的价值为 1 9。考虑子集大小为 0 和 1 时获得的最 优解为[ 1 , 0 , 0 , 1 ]。这个解是通过 k= 1 的贪婪启发式算法得到的。 若 k= 2， 除了考虑 k& 2 的子集， 还必需考虑子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。 首先从最后一个子集开始， 它是不可行的， 故将其抛弃， 剩下的子集经求解分别得到如下结果： 1 , 1 , 0 , 0 ] , [ [ 1 , 0 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ]，这些结果中最后一个价值为 2 3，它的值比 k= 0 和 k= 1 时获得的解要高，这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为 k 阶优 化方法（k - o p t i m a l） 。也就是，若从答案中取出 k 件物品，并放入另外 k 件，获得的结果不会比原来 的好，而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当 k= 1 时，保证最终结果在最佳值的 5 0 %以内；当 k= 2 时，则在 3 3 . 3 3 %以内等等，这种启发式方法的执行时间随 k 的增大而增加，需要测 试的子集数目为 O (nk )，每一个子集所需时间为 O (n)，因此当 k &0 时总的时间开销为 O (nk+1 )。实际观 察到的性能要好得多。 1.3.3 拓扑排序 一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如， 汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等 等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示 ――称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边(i, j) 表示先后关系： 任务 j 开始前任务 i 必须完成。图 1 - 4 显示了六个任务的工程，边（ 1 , 4）表示任务 1 在任务 4 开始前完 成，同样边（ 4 , 6）表示任务 4 在任务 6 开始前完成，边（1 , 4）与（4 , 6）合起来可知任务 1 在任务 6 开始前完成，即前后关系是传递的。由此可知，边（1 , 4）是多余的，因为边（1 , 3）和（3 , 4）已暗示了 这种关系。 在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费5品（自行车、小孩的秋千装置，割草机等等） 。我们可根据所建议的顺序来装配。在由任务建立的有向图中， 边（ i, j）表示在装配序列中任务 i 在任务 j 的前面，具有这种性质的序列称为拓扑序列（topological orders 或 topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序（topological sorting） 。图 1 - 4 的任务有向图有多种拓扑序列，其中的三种为 1 2 3 4 5 6，1 3 2 4 5 6 和 2 1 5 3 4 6，序列 1 4 2 3 5 6 就不 是拓扑序列，因为在这个序列中任务 4 在 3 的前面，而任务有向图中的边为（ 3 , 4） ，这种序列与边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列， 每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点：从剩下的顶点中，选择顶点 w，使 得 w 不存在这样的入边（ v,w） ，其中顶点 v 不在已排好的序列结构中出现。注意到如果加入的顶点 w 违 背了这个准则（即有向图中存在边（ v,w）且 v 不在已构造的序列中） ，则无法完成拓扑排序，因为顶点 v 必须跟随在顶点 w 之后。贪婪算法的伪代码如图 1 3 - 5 所示。while 循环的每次迭代代表贪婪算法的一个 步骤。 现在用贪婪算法来求解图 1 - 4 的有向图。首先从一个空序列 V 开始，第一步选择 V 的第一个顶点。 此时，在有向图中有两个候选顶点 1 和 2，若选择顶点 2，则序列 V = 2，第一步完成。第二步选择 V 的第 二个顶点，根据贪婪准则可知候选顶点为 1 和 5，若选择 5，则 V = 2 5。下一步，顶点 1 是唯一的候选， 因此 V = 2 5 1。第四步，顶点 3 是唯一的候选，因此把顶点 3 加入 V 得到 V = 2 5 1 3。在最后两步分别加入顶点 4 和 6 ，得 V = 2 5 1 3 4 6。 1. 贪婪算法的正确性 为保证贪婪算法算的正确性，需要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若 算法没有失败，V 即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理 1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环 qj qj + 1.qk qj , 则它没有拓扑序列，因 为该序列暗示了 qj 一定要在 qj 开始前完成。 定理 1-2 如果图 1 3 - 5 算法失败，则有向图含有环路。 证明注意到当失败时| V |&n, 且没有候选顶点能加入 V 中， 因此至少有一个顶点 q1 不在 V 中， 有向图中必 包含边（ q2 , q1）且 q2 不在 V 中，否则， q1 是可加入 V 的候选顶点。同样，必有边（q3 , q2）使得 q3 不在 V 中，若 q3 = q1 则 q1 q2 q3 是有向图中的一个环路；若 q3 ≠q1，则必存在 q4 使（q4 , q3）是有向 图的边且 q4 不在 V 中，否则，q3 便是 V 的一个候选顶点。若 q4 为 q1 , q2 , q3 中的任何一个，则又可 知有向图含有环，因为有向图具有有限个顶点数 n，继续利用上述方法，最后总能找到一个环路。 2. 数据结构的选择 为将图 1 - 5 用 C + +代码来实现，必须考虑序列 V 的描述方法，以及如何找出可加入 V 的候选顶点。一种 高效的实现方法是将序列 V 用一维数组 v 来描述的，用一个栈来保存可加入 V 的候选顶点。另有一个一 维数组 I n D e g r e e，I n D e g r e e[ j ]表示与顶点 j 相连的节点 i 的数目，其中顶点 i 不是 V 中的成员，它 们之间的有向图的边表示为（ i, j） 。当 I n D e g r e e[ j ]变为 0 时表示 j 成为一个候选节点。序列 V 初始时 为空。I n D e g r e e[ j ]为顶点 j 的入度。每次向 V 中加入一个顶点时，所有与新加入顶点邻接的顶点 j， 其 I n D e g r e e[ j ]减 1。对于有向图 1 - 4，开始时 I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由于顶点 1 和 2 的 I n D e g r e e 值为 0，因此它们是可加入 V 的候选顶点，由此，顶点 1 和 2 首先入栈。每一步，从 栈中取出一个顶点将其加入 V，同时减去与其邻接的顶点的 I n D e g r e e 值。若在第一步时从栈中取出顶 点 2 并将其加入 V， 便得到了 v [ 0 ] = 2， I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。 和 由于 I n D e g r e e [ 5 ] 刚刚变为 0，因此将顶点 5 入栈。 程序 1 3 - 2 给出了相应的 C + +代码，这个代码被定义为 N e t w o r k 的一个成员函数。而且，它对于 有无加权的有向图均适用。但若用于无向图（不论其有无加权）将会得到错误的结果，因为拓扑排序是针 对有向图来定义的。 为解决这个问题， 利用同样的模板来定义成员函数 AdjacencyGraph, AdjacencyWGraph， L i n k e d G r a p h 和 L i n k e d W G r a p h。这些函数可重载 N e t w o r k 中的函数并可输出错误信息。如 果找到拓扑序列，则 Topological 函数返回 t r u e；若输入的有向图无拓扑序列则返回 f a l s e。当找到拓扑 序列时，将其返回到 v [ 0 :n- 1 ]中。63. Network:Topological 的复杂性 第一和第三个 f o r 循环的时间开销为(n )。若使用（耗费）邻接矩阵,则第二个 for 循环所用的时间为(n2 )； 若使用邻接链表,则所用时间为(n+e)。 在两个嵌套的 while 循环中， 外层循环需执行 n 次， 每次将顶点 w 加 入到 v 中，并初始化内层 while 循环。使用邻接矩阵时，内层 w h i l e 循环对于每个顶点 w 需花费(n)的时 间；若利用邻接链表，则这个循环需花费 dwout 的时间，因此，内层 while 循环的时间开销为(n2 )或(n+e)。 所以，若利用邻接矩阵，程序 1 3 - 2 的时间复杂性为(n2 )，若利用邻接链表则为(n+e)。 程序 13-2 拓扑排序 bool Network::Topological(int v[]) {// 计算有向图中顶点的拓扑次序 // 如果找到了一个拓扑次序，则返回 t r u e，此时，在 v [ 0 : n - 1 ]中记录拓扑次序 // 如果不存在拓扑次序，则返回 f a l s e int n = Ve r t i c e s ( ) ; // 计算入度 int *InDegree = new int [n+1]; InitializePos(); // 图遍历器数组 for (int i = 1; i &= i++) // 初始化 InDegree[i] = 0; for (i = 1; i &= i++) {// 从 i 出发的边 int u = Begin(i); while (u) { InDegree[u]++; u = NextVe r t e x ( i ) ; } } // 把入度为０的顶点压入堆栈 LinkedStack&int& S; for (i = 1; i &= i++) if (!InDegree[i]) S.Add(i); // 产生拓扑次序 i = 0; // 数组 v 的游标 while (!S.IsEmpty()) {// 从堆栈中选择 // 下一个顶点 S.Delete(w); v[i++] = int u = Begin(w); while (u) {// 修改入度 InDegree[u]--; if (!InDegree[u]) S.Add(u); u = NextVe r t e x ( w ) ; } } DeactivatePos(); delete [] InD return (i == n); }71.3.4 二分覆盖 二分图是一个无向图，它的 n 个顶点可二分为集合 A 和集合 B，且同一集合中的任意两个顶点在图中 无边相连（即任何一条边都是一个顶点在集合 A 中，另一个在集合 B 中） 。当且仅当 B 中的每个顶点至少 与 A 中一个顶点相连时，A 的一个子集 A' 覆盖集合 B（或简单地说，A' 是一个覆盖） 。覆盖 A' 的大小即 为 A' 中的顶点数目。当且仅当 A' 是覆盖 B 的子集中最小的时，A' 为最小覆盖。 例 1-10 考察如图 1 - 6 所示的具有 1 7 个顶点的二分图， A={1, 2, 3, 16, 17}和 B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集 A' = { 1 , 1 6 , 1 7 }是 B 的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例 1 2 - 3 中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的翻译 人员进行翻译”这一类的问题。 二分覆盖问题类似于集合覆盖 s e t - c o v e r） （ 问题。 在集合覆盖问题中给出了 k 个集合 S= {S1 , S2 ,., Sk }，每个集合 Si 中的元素均是全集 U 中的成员。当且仅当èi S'Si =U 时，S 的子集 S' 覆盖 U，S '中的集 合数目即为覆盖的大小。当且仅当没有能覆盖 U 的更小的集合时，称 S' 为最小覆盖。可以将集合覆盖问 题转化为二分覆盖问题（反之亦然） ，即用 A 的顶点来表示 S1 , ., Sk ，B 中的顶点代表 U 中的元素。当且 仅当 S 的相应集合中包含 U 中的对应元素时，在 A 与 B 的顶点之间存在一条边。 例 1 - 11 令 S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }， S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4， S5 }是一个大小为 3 的覆盖，没有更小的覆盖， S' 即为最小覆盖。这个集合覆盖问题可映射为图 1-6 的二 分图，即用顶点 1，2，3，1 6 和 1 7 分别表示集合 S1，S2，S3，S4 和 S5，顶点 j 表示集合中的元素 j，4 ≤j≤1 5。 集合覆盖问题为 N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是 N P-复杂 问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一 种可能是分步建立覆盖 A' ，每一步选择 A 中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从 A 中选 取能覆盖 B 中还未被覆盖的元素数目最多的顶点。 例 1-12 考察图 1 - 6 所示的二分图，初始化 A' = 且 B 中没有顶点被覆盖，顶点 1 和 1 6 均能覆盖 B 中 的六个顶点，顶点 3 覆盖五个，顶点 2 和 1 7 分别覆盖四个。因此，在第一步往 A' 中加入顶点 1 或 1 6， 若加入顶点 1 6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。顶 点 1 能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }） ，顶点 2 覆盖一个( { 4 } )，顶点 3 覆盖一个（{ 1 0 }） ，顶点 1 6 覆盖零个，顶点 1 7 覆盖四个{ 4 , 9 , 1 0 , 11 }。下一步可选择 1 或 1 7 加入 A' 。若选择顶点 1，则顶点 { 1 0 , 11} 仍然未被覆盖，此时顶点 1，2，1 6 不覆盖其中任意一个，顶点 3 覆盖一个，顶点 1 7 覆盖两个， 因此选择顶点 1 7，至此所有顶点已被覆盖，得 A' = { 1 6 , 1 , 1 7 }。 图 1 - 7 给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算 法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。 1. 数据结构的选取及复杂性分析 为实现图 13 - 7 的算法，需要选择 A' 的描述方法及考虑如何记录 A 中节点所能覆盖的 B 中未覆盖节点的 数目。由于对集合 A' 仅使用加法运算，则可用一维整型数组 C 来描述 A '，用 m 来记录 A' 中元素个数。 将 A' 中的成员记录在 C[ 0 :m-1] 中。对于 A 中顶点 i，令 N e wi 为 i 所能覆盖的 B 中未覆盖的顶点数目。 逐步选择 N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各 N e wi 值。 在这种更新中，检查 B 中最近一次被 V 覆盖的顶点，令 j 为这样的一个顶点，则 A 中所有覆盖 j 的顶点 的 N e wi 值均减 1。 例 1-13 考察图 1 - 6， 初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。 假设在例 1 - 1 2 中，第一步选择顶点 1 6，为更新 N e wi 的值检查 B 中所有最近被覆盖的顶点，这些顶点为 5 , 6 , 8 , 1 2 , 1 4 和 1 5。当检查顶点 5 时，将顶点 2 和 1 6 的 N e wi 值分别减 1，因为顶点 5 不再是被顶点 2 和 1 6 覆8盖的未覆盖节点；当检查顶点 6 时，顶点 1 , 2 ,和 1 6 的相应值分别减 1；同样，检查顶点 8 时，1，2，3 和 1 6 的值分别减 1；当检查完所有最近被覆盖的顶点，得到的 N e wi 值为（4，1，0，4） 。下一步选择顶 点 1，最新被覆盖的顶点为 4，7，9 和 1 3；检查顶点 4 时，N e w1 , N e w2, 和 N e w1 7 的值减 1；检查 顶点 7 时，N e w1 的值减 1，因为顶点 1 是覆盖 7 的唯一顶点。 为了实现顶点选取的过程，需要知道 N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个 目的，N e w 是一个整型数组，New[i] 即等于 N e wi，且 c o v 为一个布尔数组。若顶点 i 未被覆盖则 c o v [ i ]等于 f a l s e，否则 c o v [ i ]为 t r u e。现将图 1 - 7 的伪代码进行细化得到图 1 - 8。 m=0; //当前覆盖的大小 对于 A 中的所有 i，New[i]=Degree[i] 对于 B 中的所有 i，C o v [ i ] = f a l s e while (对于 A 中的某些 i,New[i]&0) { 设 v 是具有最大的 N e w [ i ]的顶点； C[m++]=v; for ( 所有邻接于 v 的顶点 j) { if (!Cov[j]) { Cov[j]= 对于所有邻接于 j 的顶点，使其 N e w [ k ]减 1 }}} if (有些顶点未被覆盖) 失败 else 找到一个覆盖 图 1-8 图 1-7 的细化 更新 N e w 的时间为 O (e)，其中 e 为二分图中边的数目。若使用邻接矩阵，则需花(n2 ) 的时间来寻找图 中的边，若用邻接链表，则需(n+e) 的时间。实际更新时间根据描述方法的不同为 O (n2 ) 或 O (n+e)。逐 步选择顶点所需时间为(S i z e O f A)，其中 S i z e O f A=| A |。因为 A 的所有顶点都有可能被选择，因此所 需步骤数为 O ( S i z e O f A )，覆盖算法总的复杂性为 O ( S i z e O f A 2+n2) = O ( n2)或 O (S i z e Of A2+n + e)。 2. 降低复杂性 通过使用有序数组 N e wi、最大堆或最大选择树（max selection tree）可将每步选取顶点 v 的复杂性降 为( 1 )。但利用有序数组，在每步的最后需对 N e wi 值进行重新排序。若使用箱子排序，则这种排序所需 时间为(S i z e O f B ) ( S i z e O fB =|B| ) （见 3 . 8 . 1 节箱子排序） 。由于一般 S i z e O f B 比 S i z e O f A 大 得多，因此有序数组并不总能提高性能。 如果利用最大堆，则每一步都需要重建堆来记录 N e w 值的变化，可以在每次 N e w 值减 1 时进行重 建。 这种减法操作可引起被减的 N e w 值最多在堆中向下移一层， 因此这种重建对于每次 N e w 值减 1 需( 1 ) 的时间，总共的减操作数目为 O (e)。因此在算法的所有步骤中，维持最大堆仅需 O (e)的时间，因而利用 最大堆时覆盖算法的总复杂性为 O (n2 )或 O (n+e)。 若利用最大选择树，每次更新 N e w 值时需要重建选择树，所需时间为(log S i z e O f A)。重建的最好 时机是在每步结束时，而不是在每次 N e w 值减 1 时，需要重建的次数为 O (e)，因此总的重建时间为 O (e log S i z e OfA)，这个时间比最大堆的重建时间长一些。然而，通过维持具有相同 N e w 值的顶点箱子，也 可获得和利用最大堆时相同的时间限制。由于 N e w 的取值范围为 0 到 S i z e O f B，需要 S i z e O f B+ 1 个箱子，箱子 i 是一个双向链表，链接所有 N e w 值为 i 的顶点。在某一步结束时，假如 N e w [ 6 ]从 1 2 变到 4， 则需要将它从第 1 2 个箱子移到第 4 个箱子。 利用模拟指针及一个节点数组 n o d e （其中 n o d e [ i ] 代表顶点 i，n o d e [ i ] . l e f t 和 n o d e [ i ] . r i g h t 为双向链表指针） ，可将顶点 6 从第 1 2 个箱子移到第 4 个箱子，从第 1 2 个箱子中删除 n o d e [ 0 ]并将其插入第 4 个箱子。利用这种箱子模式，可得覆盖启发式算9法的复杂性为 O (n2 )或 O(n+e)。 （取决于利用邻接矩阵还是线性表来描述图） 。 3. 双向链接箱子的实现 为了实现上述双向链接箱子，图 1 - 9 定义了类 U n d i r e c t e d 的私有成员。N o d e Ty p e 是一个具有 私有整型成员 l e f t 和 r i g h t 的类，它的数据类型是双向链表节点，程序 1 3 - 3 给出了 U n d i r e c t e d 的 私有成员的代码。 void CreateBins (int b, int n) 创建 b 个空箱子和 n 个节点 void DestroyBins() { delete [] delete []} void InsertBins(int b, int v) 在箱子 b 中添加顶点 v void MoveBins(int bMax, int ToBin, int v) 从当前箱子中移动顶点 v 到箱子 To B i n int * b i n [ i ]指向代表该箱子的双向链表的首节点 N o d e Type * n o d e [ i ]代表存储顶点 i 的节点 图 1-9 实现双向链接箱子所需的 U n d i r e c t e d 私有成员 程序 13-3 箱子函数的定义 void Undirected::CreateBins(int b, int n) {// 创建 b 个空箱子和 n 个节点 node = new NodeType [n+1]; bin = new int [b+1]; // 将箱子置空 for (int i = 1; i &= i++) bin[i] = 0; } void Undirected::InsertBins(int b, int v) {// 若 b 不为０，则将 v 插入箱子 b if (!b) // b 为 0，不插入 node[v].left = // 添加在左端 if (bin[b]) node[bin[b]].left = node[v].right = bin[b]; bin[b] = } void Undirected::MoveBins(int bMax, int ToBin, int v) {// 将顶点 v 从其当前所在箱子移动到 To B i n . // v 的左、右节点 int l = node[v]. int r = node[v]. // 从当前箱子中删除 if (r) node[r].left = node[v]. if (l & bMax || bin[l] != v) // 不是最左节点10node[l].right = else bin[l] = // 箱子 l 的最左边 // 添加到箱子 To B i n I n s e r t B i n s ( ToBin, v); } 函数 C r e a t e B i n s 动态分配两个数组： n o d e 和 b i n，n o d e [i ]表示顶点 i, bin[i ]指向其 N e w 值为 i 的双向链表的顶点, f o r 循环将所有双向链表置为空。如果 b≠0，函数 InsertBins 将顶点 v 插入箱子 b 中。 因为 b 是顶点 v 的 New 值，b = 0 意味着顶点 v 不能覆盖 B 中当前还未被覆盖的任何顶点，所以，在建 立覆盖时这个箱子没有用处，故可以将其舍去。当 b≠0 时，顶点 n 加入 New 值为 b 的双向链表箱子的最 前面，这种加入方式需要将 node[v] 加入 bin[b] 中第一个节点的左边。由于表的最左节点应指向它所属的 箱子， 因此将它的 node[v].left 置为 b。 若箱子不空， 则当前第一个节点的 left 指针被置为指向新节点。 node[v] 的右指针被置为 b i n [ b ]，其值可能为 0 或指向上一个首节点的指针。最后， b i n [ b ]被更新为指向表中 新的第一个节点。MoveBins 将顶点 v 从它在双向链表中的当前位置移到 New 值为 ToBin 的位置上。其 中存在 bMa x，使得对所有的箱子 b i n[ j ]都有：如 j&bMa x，则 b i n [ j ]为空。代码首先确定 n o d e [ v ] 在当前双向链表中的左右节点，接着从双链表中取出 n o d e [ v ]，并利用 I n s e r t B i n s 函数将其重新插 入到 b i n [ To B i n ]中。 4. Undirected::BipartiteCover 的实现 函数的输入参数 L 用于分配图中的顶点（分配到集合 A 或 B） [i ] = 1 表示顶点 i 在集合 A 中，L[ i ] 。L = 2 则表示顶点在 B 中。函数有两个输出参数： C 和 m，m 为所建立的覆盖的大小， C [ 0 , m - 1 ]是 A 中 形成覆盖的顶点。若二分图没有覆盖，函数返回 f a l s e；否则返回 t r u e。完整的代码见程序 1 3 - 4。 程序 13-4 构造贪婪覆盖 bool Undirected::BipartiteCover(int L[], int C[], int& m) {// 寻找一个二分图覆盖 // L 是输入顶点的标号, L[i] = 1 当且仅当 i 在Ａ中 // C 是一个记录覆盖的输出数组 // 如果图中不存在覆盖，则返回 f a l s e // 如果图中有一个覆盖，则返回 // 在 m 中返回覆盖的大小; 在 C [ 0 : m - 1 ]中返回覆盖 int n = Ve r t i c e s ( ) ; // 插件结构 int SizeOfA = 0; for (int i = 1; i &= i++) // 确定集合 A 的大小 if (L[i] == 1) SizeOfA++; int SizeOfB = n - SizeOfA; CreateBins(SizeOfB, n); int *New = new int [n+1]; / /顶点 i 覆盖了Ｂ中 N e w [ i ]个未被覆盖的顶点 bool *Change = new bool [n+1]; // Change[i]为 t r u e 当且仅当 New[i] 已改变 bool *Cov = new bool [n+1]; // Cov[i] 为 true 当且仅当顶点 i 被覆盖 InitializePos(); LinkedStack&int& S; // 初始化 for (i = 1; i &= i++) { Cov[i] = Change[i] =11if (L[i] == 1) {// i 在 A 中 New[i] = Degree(i); // i 覆盖了这么多 InsertBins(New[i], i);}} // 构造覆盖 int covered = 0, // 被覆盖的顶点 MaxBin = SizeOfB; // 可能非空的最大箱子 m = 0; // C 的游标 while (MaxBin & 0) { // 搜索所有箱子 // 选择一个顶点 if (bin[MaxBin]) { // 箱子不空 int v = bin[MaxBin]; // 第一个顶点 C[m++] = // 把 v 加入覆盖 // 标记新覆盖的顶点 int j = Begin(v), while (j) { if (!Cov[j]) {// j 尚未被覆盖 Cov[j] = covered++; // 修改 N e w k = Begin(j); while (k) { New[k]--; // j 不计入在内 if (!Change[k]) { S.Add(k); // 仅入栈一次 Change[k] =} k = NextVe r t e x ( j ) ; } } j = NextVe r t e x ( v ) ; } // 更新箱子 while (!S.IsEmpty()) { S.Delete(k); Change[k] = MoveBins(SizeOfB, New[k], k);} } else MaxBin--; } DeactivatePos(); DestroyBins(); delete [] N delete [] C delete [] C return (covered == SizeOfB); } 程序 1 3 - 4 首先计算出集合 A 和 B 的大小、 初始化必要的双向链表结构、 创建三个数组、 初始化图遍历器、12并创建一个栈。然后将数组 C o v 和 C h a n g e 初始化为 f a l s e，并将 A 中的顶点根据它们覆盖 B 中顶点 的数目插入到相应的双向链表中。 为了构造覆盖，首先按 SizeOfB 递减至 1 的顺序检查双向链表。当发现一个非空的表时，就将其第一 个顶点 v 加入到覆盖中，这种策略即为选择具有最大 Ne o v [ j ]置为 t r u e，表示顶点 j 现在已被覆盖，同 时将已被覆盖的 B 中的顶点数目加 1。 由于 j 是最近被覆 w 值的顶点。 将所选择的顶点加入覆盖数组 C 并 检查 B 中所有与它邻接的顶点。若顶点 j 与 v 邻接且还未被覆盖，则将 C 盖的，所有 A 中与 j 邻接的顶 点的 New 值减 1。 下一个 while 循环降低这些 New 值并将 New 值被降低的顶点保存在一个栈中。 当所有 与顶点 v 邻接的顶点的 Cov 值更新完毕后，N e w 值反映了 A 中每个顶点所能覆盖的新的顶点数，然而 A 中的顶点由于 New 值被更新，处于错误的双向链表中，下一个 while 循环则将这些顶点移到正确的表中。 1.3.5 单源最短路径 在这个问题中，给出有向图 G，它的每条边都有一个非负的长度（耗费） a [i ][ j ]，路径的长度即为 此路径所经过的边的长度之和。对于给定的源顶点 s，需找出从它到图中其他任意顶点（称为目的）的最短 路径。图 13-10a 给出了一个具有五个顶点的有向图，各边上的数即为长度。假设源顶点 s 为 1，从顶点 1 出发的最短路径按路径长度顺序列在图 13-10b 中，每条路径前面的数字为路径的长度。 利用 E. Dijkstra 发明的贪婪算法可以解决最短路径问题，它通过分步方法求出最短路径。每一步产生一个 到达新的目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径 的顶点中，选择路径长度最短的目的顶点。也就是说， D i j k s t r a 的方法按路径长度顺序产生最短路径。 首先最初产生从 s 到它自身的路径，这条路径没有边，其长度为 0。在贪婪算法的每一步中，产生下一个 最短路径。一种方法是在目前已产生的最短路径中加入一条可行的最短的边，结果产生的新路径是原先产 生的最短路径加上一条边。这种策略并不总是起作用。另一种方法是在目前产生的每一条最短路径中，考 虑加入一条最短的边，再从所有这些边中先选择最短的，这种策略即是 D i j k s t r a 算法。 可以验证按长度顺序产生最短路径时， 下一条最短路径总是由一条已产生的最短路径加上一条边形成。 实际上，下一条最短路径总是由已产生的最短路径再扩充一条最短的边得到的，且这条路径所到达的顶点 其最短路径还未产生。例如在图 1 3 - 1 0 中，b 中第二条路径是第一条路径扩充一条边形成的；第三条路 径则是第二条路径扩充一条边；第四条路径是第一条路径扩充一条边；第五条路径是第三条路径扩充一条 边。 通过上述观察可用一种简便的方法来存储最短路径。可以利用数组 p，p [ i ]给出从 s 到达 i 的路径中 顶点 i 前面的那个顶点。在本例中 p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。从 s 到顶点 i 的路径可反向创建。从 i 出 发按 p[i],p[p[i]],p[p[p[i]]], .的顺序， 直到到达顶点 s 或 0。 在本例中， 如果从 i = 5 开始， 则顶点序列为 p[i]=4, p[4]=3, p[3]=1=s，因此路径为 1 , 3 , 4 , 5。 为能方便地按长度递增的顺序产生最短路径， 定义 d [ i ]为在已产生的最短路径中加入一条最短边的长 度，从而使得扩充的路径到达顶点 i。最初，仅有从 s 到 s 的一条长度为 0 的路径，这时对于每个顶点 i， d [ i ]等于 a [ s ] [ i ]（a 是有向图的长度邻接矩阵） 。为产生下一条路径，需要选择还未产生最短路径的下 一个节点，在这些节点中 d 值最小的即为下一条路径的终点。当获得一条新的最短路径后，由于新的最短 路径可能会产生更小的 d 值，因此有些顶点的 d 值可能会发生变化。 综上所述，可以得到图 1 3 - 11 所示的伪代码， 1) 将与 s 邻接的所有顶点的 p 初始化为 s，这个初始 化用于记录当前可用的最好信息。也就是说，从 s 到 i 的最短路径，即是由 s 到它自身那条路径再扩充一 条边得到。当找到更短的路径时， p [ i ]值将被更新。若产生了下一条最短路径，需要根据路径的扩充边 来更新 d 的值。 1) 初始化 d[i ] =a[s] [i ]（1≤i≤n） ， 对于邻接于 s 的所有顶点 i，置 p[i ] =s, 对于其余的顶点置 p[i ] = 0； 对于 p[i]≠0 的所有顶点建立 L 表。 2) 若 L 为空，终止，否则转至 3 )。133) 从 L 中删除 d 值最小的顶点。 4) 对于与 i 邻接的所有还未到达的顶点 j，更新 d[ j ]值为 m i n{d[ j ], d[i ] +a[i ][ j ] }；若 d[ j ]发生了变化 且 j 还未 在 L 中，则置 p[ j ] = 1，并将 j 加入 L，转至 2。 图 1 - 11 最短路径算法的描述 1. 数据结构的选择 我们需要为未到达的顶点列表 L 选择一个数据结构。 L 中可以选出 d 值最小的顶点。 从 如果 L 用最小 堆（见 9 . 3 节）来维护，则这种选取可在对数时间内完成。由于 3) 的执行次数为 O ( n )，所以所需时间 为 O ( n l o g n )。 由于扩充一条边产生新的最短路径时， 可能使未到达的顶点产生更小的 d 值， 所以在 4) 中 可能需要改变一些 d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于 执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为 O ( n2 l o g n )。 若 L 用无序的链表来维护，则 3) 与 4) 花费的时间为 O ( n2 )，3) 的每次执行需 O(|L | ) =O( n )的时间，每 次减操作需( 1 )的时间（需要减去 d[j] 的值，但链表不用改变） 。利用无序链表将图 1 - 11 的伪代码细化为 程序 1 3 - 5，其中使用了 C h a i n (见程序 3 - 8 )和 C h a i n I t e r a t o r 类（见程序 3 - 1 8） 。 程序 13-5 最短路径程序 template&class T& void AdjacencyWDigraph&T&::ShortestPaths(int s, T d[], int p[]) {// 寻找从顶点 s 出发的最短路径, 在 d 中返回最短距离 // 在 p 中返回前继顶点 if (s & 1 || s & n) throw OutOfBounds(); Chain&int& L; // 路径可到达顶点的列表 ChainIterator&int& I; // 初始化 d, p, L for (int i = 1; i &= i++){ d[i] = a[s][i]; if (d[i] == NoEdge) p[i] = 0; else {p[i] = L.Insert(0,i);} } // 更新 d, p while (!L.IsEmpty()) {// 寻找具有最小 d 的顶点 v int *v = I.Initialize(L); int *w = I.Next(); while (w) { if (d[*w] & d[*v]) v = w = I.Next();} // 从 L 中删除通向顶点 v 的下一最短路径并更新 d int i = *v; L.Delete( *v); for (int j = 1; j &= j++) { if (a[i][j] != NoEdge && (!p[j] || d[j] & d[i] + a[i][j])) { // 减小 d [ j ]14d[j] = d[i] + a[i][j]; // 将 j 加入 L if (!p[j]) L.Insert(0,j); p[j] =} } } } 若 N o E d g e 足够大，使得没有最短路径的长度大于或等于 N o E d g e，则最后一个 for 循环的 i f 条件可 简化为：if (d[j] & d[i] + a[i][j])) NoEdge 的值应在能使 d[j]+a[i][j] 不会产生溢出的范围内。 2. 复杂性分析 程序 1 3 - 5 的复杂性是 O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有 可能在最短路径中。因此这种算法的最小可能时间为 O ( e )。由于使用耗费邻接矩阵来描述图，仅决定哪 条边在有向图中就需 O ( n2 )的时间。因此，采用这种描述方法的算法需花费 O ( n2 )的时间。不过程序 1 3 - 5 作了优化（常数因子级） 。即使改变邻接表，也只会使最后一个 f o r 循环的总时间降为 O ( e )（因为只 有与 i 邻接的顶点的 d 值改变） 。从 L 中选择及删除最小距离的顶点所需总时间仍然是 O( n2 )。 1.3.6 最小耗费生成树 在例 1 - 2 及 1 - 3 中已考察过这个问题。因为具有 n 个顶点的无向网络 G 的每个生成树刚好具有 n-1 条边，所以问题是用某种方法选择 n-1 条边使它们形成 G 的最小生成树。至少可以采用三种不同的贪婪策 略来选择这 n-1 条边。这三种求解最小生成树的贪婪算法策略是： K r u s k a l 算法，P r i m 算法和 S o l l i n 算法。 1. Kruskal 算法 (1) 算法思想 K r u s k a l 算法每次选择 n- 1 条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具 有最小耗费的边加入已选择的边的集合中。 注意到所选取的边若产生环路则不可能形成一棵生成树。 r u s K k a l 算法分 e 步，其中 e 是网络中边的数目。按耗费递增的顺序来考虑这 e 条边，每次考虑一条边。当考 虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 考察图 1-12a 中的网络。初始时没有任何边被选择。图 13-12b 显示了各节点的当前状态。边（ 1 , 6）是 最先选入的边，它被加入到欲构建的生成树中，得到图 1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树 中（如图 1 3 - 1 2 d 所示） 。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图 1 3 - 1 2 e。 下一步考虑边（ 2，3）并将其加入树中（如图 1 3 - 1 2 f 所示） 。在其余还未考虑的边中， （7，4）具有最 小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树 中，得到的树如图 13-12g 所示。下一步考虑边（ 7，5） ，由于会产生环路，将其丢弃。最后考虑边（ 6， 5）并将其加入树中，产生了一棵生成树，其耗费为 9 9。图 1 - 1 3 给出了 K r u s k a l 算法的伪代码。 / /在一个具有 n 个顶点的网络中找到一棵最小生成树 令 T 为所选边的集合，初始化 T= 令 E 为网络中边的集合 w h i l e(E≠ )&&(| T |≠n- 1 ) { 令(u,v)为 E 中代价最小的边 E=E- { (u,v) } / /从 E 中删除边 i f( (u,v)加入 T 中不会产生环路)将（ u,v）加入 T } i f(| T | = =n-1) T 是最小耗费生成树15e l s e 网络不是互连的，不能找到生成树 图 13-13 Kruskao 算法的伪代码 (2) 正确性证明 利用前述装载问题所用的转化技术可以证明图 1 3 - 1 3 的贪婪算法总能建立一棵最小耗费生成树。需 要证明以下两点： 1) 只要存在生成树，K r u s k a l 算法总能产生一棵生成树； 2) 产生的生成树具有最小 耗费。令 G 为任意加权无向图（即 G 是一个无向网络） 。从 1 2 . 11 . 3 节可知当且仅当一个无向图连通时 它有生成树。而且在 Kruskal 算法中被拒绝（丢弃）的边是那些会产生环路的边。删除连通图环路中的一 条边所形成的图仍是连通图，因此如果 G 在开始时是连通的，则 T 与 E 中的边总能形成一个连通图。也就 是若 G 开始时是连通的，算法不会终止于 E= 和| T |& n- 1。 现在来证明所建立的生成树 T 具有最小耗费。由于 G 具有有限棵生成树，所以它至少具有一棵最小生 成树。令 U 为这样的一棵最小生成树， T 与 U 都刚好有 n- 1 条边。如果 T=U, 则 T 就具有最小耗费，那 么不必再证明下去。因此假设 T≠U，令 k(k &0) 为在 T 中而不在 U 中的边的个数，当然 k 也是在 U 中而 不在 T 中的边的数目。 通过把 U 变换为 T 来证明 U 与 T 具有相同的耗费，这种转化可在 k 步内完成。每 一步使在 T 而不在 U 中的边的数目刚好减 1。 而且 U 的耗费不会因为转化而改变。 经过 k 步的转化得到的 U 将与原来的 U 具有相同的耗费，且转化后 U 中的边就是 T 中的边。由此可知， T 具有最小耗费。每步 转化包括从 T 中移一条边 e 到 U 中，并从 U 中移出一条边 f。边 e 与 f 的选取按如下方式进行： 1) 令 e 是在 T 中而不在 U 中的具有最小耗费的边。由于 k &0，这条边肯定存在。 2) 当把 e 加入 U 时，则会形成唯一的一条环路。令 f 为这条环路上不在 T 中的任意一条边。 由于 T 中不含环路，因此所形成的环路中至少有一条边不在 T 中。 从 e 与 f 的选择方法中可以看出， V=U+ {e} -{ f } 是一棵生成树，且 T 中恰有 k- 1 条边不在 V 中出现。 现在来证明 V 的耗费与 U 的相同。显然，V 的耗费等于 U 的耗费加上边 e 的耗费再减去边 f 的耗费。若 e 的耗费比 f 的小，则生成树 V 的耗费比 U 的耗费小，这是不可能的。如果 e 的耗费高于 f，在 K r u s k a l 算法中 f 会在 e 之前被考虑。由于 f 不在 T 中，Kruskal 算法在考虑 f 能否加入 T 时已将 f 丢弃，因此 f 和 T 中耗费小于或等于 f 的边共同形成环路。通过选择 e，所有这些边均在 U 中，因此 U 肯定含有环路， 但是实际上这不可能，因为 U 是一棵生成树。e 的代价高于 f 的假设将会导致矛盾。剩下的唯一的可能是 e 与 f 具有相同的耗费，由此可知 V 与 U 的耗费相同。 (3) 数据结构的选择及复杂性分析 为了按耗费非递减的顺序选择边，可以建立最小堆并根据需要从堆中一条一条地取出各边。当图中有 e 条边时，需花(e) 的时间初始化堆及 O ( l o ge) 的时间来选取每一条边。边的集合 T 与 G 中的顶点一起 定义了一个由至多 n 个连通子图构成的图。用顶点集合来描述每个子图，这些顶点集合没有公共顶点。为 了确定边（ u,v）是否会产生环路，仅需检查 u,v 是否在同一个顶点集中（即处于同一子图） 。如果是，则 会形成一个环路；如果不是，则不会产生环路。因此对于顶点集使用两个 F i n d 操作就足够了。当一条边 包含在 T 中时，2 个子图将被合并成一个子图，即对两个集合执行 U n i o n 操作。集合的 F i n d 和 U n i o n 操作可利用 8 . 1 0 . 2 节的树（以及加权规则和路径压缩）来高效地执行。F i n d 操作的次数最多为 2e，Un i o n 操作的次数最多为 n- 1（若网络是连通的，则刚好是 n- 1 次） 。加上树的初始化时间，算法中这部分的 复杂性只比 O (n+e) 稍大一点。 对集合 T 所执行的唯一操作是向 T 中添加一条新边。T 可用数组 t 来实现。添加操作在数组 的一端进行，因为最多可在 T 中加入 n- 1 条边，因此对 T 的操作总时间为 O (n)。 总结上述各个部分的执行时间，可得图 1 3 - 1 3 算法的渐进复杂性为 O (n+el o ge)。 (4) 实现 利用上述数据结构，图 1 - 1 3 可用 C + +代码来实现。首先定义 E d g e N o d e 类（见程序 1 3 - 6 )，它是最16小堆的元素及生成树数组 t 的数据类型。 程序 13-6 Kruskal 算法所需要的数据类型 template class EdgeNode { public: operator T() const {} private: T//边的高度 int u,//边的端点 }; 为了更简单地使用 8 . 1 0 . 2 节的查找和合并策略，定义了 U n i o n F i n d 类，它的构造函数是程序 8 - 1 6 的初始化函数，U n i o n 是程序 8 - 1 6 的加权合并函数，F i n d 是程序 8 - 1 7 的路径压缩搜索函数。 为了编写与网络描述无关的代码，还定义了一个新的类 U N e t Wo r k，它包含了应用于无向网络的所有函 数。这个类与 U n d i r e c t e d 类的差别在于 U n d i r e c t e d 类中的函数不要求加权边，而 U N e t Wo r k 要求边必须带有权值。U N e t Wo r k 中的成员需要利用 N e t w o r k 类中定义的诸如 B e g i n 和 N e x t Ve r t e x 的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的 权值。这些遍历函数以及有向和无向加权网络的其他函数一起构成了 W N e t w o r k 类（见程序 1 3 - 7） 。 程序 13-7 WNetwork 类 template class WNetwork : virtual public Network { public : virtual void First(int i, int& j, T& c)=0; virtual void Next(int i, int& j, T& c)=0; }; 象 B e g i n 和 N e x t Ve r t e x 一样， 可在 A d j a c e n c y W D i g r a p h 及 L i n k e d W D i g r a p h 类中加入 函数 F i r s t 与 N e x t。 现在 A d j a c e n c y W D i g r a p h 及 L i n k e d W D i g r a p h 类都需要从 W N e t Wo r k 中派生而来。由于 A d j a c e n c y W G r a p h 类和 L i n k e d W G r a p h 类需要访问 U N e t w o r k 的成 员，所以这两个类还必须从 U N e t Wo r k 中派生而来。U N e t Wo r k : : K r u s k a l 的代码见程序 1 3 - 8， 它要求将 Edges() 定义为 N e t Work 类的虚成员，并且把 U N e t Wo r k 定义为 E d g e N o d e 的友元） 。如 果没有生成树，函数返回 f a l s e，否则返回 t r u e。注意当返回 true 时，在数组 t 中返回最小耗费生成树。 程序 13-8 Kr u s k a l 算法的 C + +代码 template bool UNetwork::Kruskal(EdgeNode t[]) {// 使用 K r u s k a l 算法寻找最小耗费生成树 // 如果不连通则返回 false // 如果连通，则在 t [ 0 : n - 2 ]中返回最小生成树 int n = Ve r t i c e s ( ) ; int e = Edges(); / /设置网络边的数组 InitializePos(); // 图遍历器 EdgeNode *E = new EdgeNode [e+1]; int k = 0; // E 的游标 for (int i = 1; i &= i++) { // 使所有边附属于 i17
T First(i, j, c); while (j) { // j 邻接自 i if (i & j) {// 添加到达 E 的边 E[++k].weight = E[k].u = E[k].v =} Next(i, j, c); } } // 把边放入最小堆 MinHeap & H(1); H.Initialize(E, e, e); UnionFind U(n); // 合并/搜索结构 // 根据耗费的次序来抽取边 k = 0; // 此时作为 t 的游标 while (e && k & n - 1) { // 生成树未完成，尚有剩余边 EdgeN H.DeleteMin(x); // 最小耗费边 e--; int a = U.Find(x.u); int b = U.Find(x.v); if (a != b) {// 选择边 t[k++] = U.Union(a,b);} } DeactivatePos(); H.Deactivate(); return (k == n - 1); } 2. Prim 算法 与 Kr u s k a l 算法类似，P r i m 算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准 则是：从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所 有步骤中选择的边形成一棵树。相反，在 Kruskal 算法中所有入选的边集合最终形成一个森林。 P r i m 算法从具有一个单一顶点的树 T 开始，这个顶点可以是原图中任意一个顶点。然后往 T 中加入一条 代价最小的边（ u , v）使 Tè{ (u , v) }仍是一棵树，这种加边的步骤反复循环直到 T 中包含 n- 1 条边。注 意对于边（ u , v） ，u、v 中正好有一个顶点位于 T 中。P r i m 算法的伪代码如图 1 -1 4 所示。在伪代码中 也包含了所输入的图不是连通图的可能， 在这种情况下没有生成树。 1 - 1 5 显示了对图 1-12a 使用 P r i m 图 算法的过程。把图 1 - 1 4 的伪代码细化为 C + +程序及其正确性的证明留作练习（练习 3 1） 。 / /假设网络中至少具有一个顶点 设 T 为所选择的边的集合，初始化 T=18设 T V 为已在树中的顶点的集合，置 T V= { 1 } 令 E 为网络中边的集合 w h i l e(E& & ) & & (| T | & & n-1) { 令（u , v）为最小代价边，其中 u T V, v T V i f（没有这种边） b re a k E=E- { (u,v) } / /从 E 中删除此边 在 T 中加入边（ u , v） } if (| T | = =n- 1 ) T 是一棵最小生成树 else 网络是不连通的，没有最小生成树 图 13-14 Prim 最小生成树算法 如果根据每个不在 T V 中的顶点 v 选择一个顶点 n e ar (v)，使得 n e ar (v) ? TV 且 c o st (v, n e ar (v) )的值 是所有这样的 n e ar (v) 节点中最小的，则实现 P r i m 算法的时间复杂性为 O (n2 )。下一条添加到 T 中的 边是这样的边：其 cost (v, near (v)) 最小，且 v T V。 3. Sollin 算法 S o l l i n 算法每步选择若干条边。在每步开始时，所选择的边及图中的 n 个顶点形成一个生成树的森 林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择 的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当 有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条 边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。 图 1 - 6 给出了初始状态为图 1-12a 时，使用 S o l l i n 算法的步骤。初始入选边数为 0 时的情形如图 13-12a 时,森林中的每棵树均是单个顶点。 顶点 1， .， 所选择的边分别是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)， 2， 7 其中不同的边是( 1 , 6 )， 2 , 7 )，(3,4) 和( 5 , 4 )， ( 将这些边加入入选边的集合后所得到的结果如图 1 3 - 1 6 a 所示。下一步具有顶点集{ 1 , 6 }的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形 成一棵生成树， 构建好的生成树见图 1 3 - 6 b。 o l l i n 算法的 C + +程序实现及其正确性证明留作练习 S （练 习 3 2 )。第 2 章 分而治之算法君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将 首先介绍怎样在算法设计领域应用这一古老的策略，然后将利用这一策略解决如下问题：最小最大问题、 矩阵乘法、残缺棋盘、排序、选择和计算一个几何问题――找出二维空间中距离最近的两个点。 本章给出了用来分析分而治之算法复杂性的数学方法，并通过推导最小最大问题和排序问题的复杂性下限 来证明分而治之算法对于求解这两种问题是最优的（因为算法的复杂性与下限一致） 。 2.1 算法思想 分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 1) 把它分成两个 或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。 小问题通常与原问题相似，可以递归地使用分而治之策略来解决。 例 2-1 [找出伪币] 给你一个装有 1 6 个硬币的袋子。1 6 个硬币中有一个是伪造的，并且那个伪造的硬币比 真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较 两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币 1 与硬币 2 的重量。 假如硬币 1 比硬币 2 轻，则硬币 1 是伪造的；假如硬币 2 比硬币 1 轻，则硬币 2 是伪造的。这样就完成了 任务。假如两硬币重量相等，则比较硬币 3 和硬币 4。同样，假如有一个硬币轻一些，则寻找伪币的任务19完成。假如两硬币重量相等，则继续比较硬币 5 和硬币 6。按照这种方式，可以最多通过 8 次比较来判断 伪币的存在并找出这一伪币。 另外一种方法就是利用分而治之方法。假如把 1 6 硬币的例子看成一个大的问题。第一步，把这一问 题分成两个小问题。 随机选择 8 个硬币作为第一组称为 A 组， 剩下的 8 个硬币作为第二组称为 B 组。 这样， 就把 1 6 个硬币的问题分成两个 8 硬币的问题来解决。第二步，判断 A 和 B 组中是否有伪币。可以利用仪 器来比较 A 组硬币和 B 组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重 量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果 得出原先 1 6 个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论 A 组还是 B 组中有 伪币，都可以推断这 1 6 个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。 现在假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币， 那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较 两次就可以找到伪币。这样，1 6 硬币的问题就被分为两个 8 硬币（A 组和 B 组）的问题。通过比较这两组 硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪 币。假设 B 是轻的那一组，因此再把它分成两组，每组有 4 个硬币。称其中一组为 B1，另一组为 B2。比 较这两组，肯定有一组轻一些。如果 B1 轻，则伪币在 B1 中，再将 B1 又分成两组，每组有两个硬币，称 其中一组为 B1a，另一组为 B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此 不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 例 2-2 [金块问题] 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。 按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式， 除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的 金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望 用最少的比较次数找出最轻和最重的金块。 假设袋中有 n 个金块。可以用函数 M a x（程序 1 - 3 1）通过 n-1 次比较找到最重的金块。找到最重的 金块后，可以从余下的 n-1 个金块中用类似的方法通过 n-2 次比较找出最轻的金块。这样，比较的总次数 为 2n-3。程序 2 - 2 6 和 2 - 2 7 是另外两种方法，前者需要进行 2n-2 次比较，后者最多需要进行 2n-2 次比 较。 下面用分而治之方法对这个问题进行求解。当 n 很小时，比如说， n≤2，识别出最重和最轻的金块， 一次比较就足够了。当 n 较大时（n＞2） ，第一步，把这袋金块平分成两个小袋 A 和 B。第二步，分别找 出在 A 和 B 中最重和最轻的金块。设 A 中最重和最轻的金块分别为 HA 与 LA，以此类推，B 中最重和最 轻的金块分别为 HB 和 LB。第三步，通过比较 HA 和 HB，可以找到所有金块中最重的；通过比较 LA 和 LB，可以找到所有金块中最轻的。在第二步中，若 n＞2，则递归地应用分而治之方法。 假设 n= 8。这个袋子被平分为各有 4 个金块的两个袋子 A 和 B。为了在 A 中找出最重和最轻的金块，A 中 的 4 个金块被分成两组 A1 和 A2。每一组有两个金块，可以用一次比较在 A 中找出较重的金块 HA1 和较 轻的金块 LA1。经过另外一次比较，又能找出 HA 2 和 LA 2。现在通过比较 HA1 和 HA2，能找出 HA；通 过 LA 1 和 LA2 的比较找出 LA。这样，通过 4 次比较可以找到 HA 和 LA。同样需要另外 4 次比较来确定 HB 和 LB。通过比较 HA 和 HB（LA 和 LB） ，就能找出所有金块中最重和最轻的。因此，当 n= 8 时，这 种分而治之的方法需要 1 0 次比较。如果使用程序 1 - 3 1，则需要 1 3 次比较。如果使用程序 2 - 2 6 和 2 - 2 7，则最多需要 1 4 次比较。设 c(n)为使用分而治之方法所需要的比较次数。为了简便，假设 n 是 2 的幂。 当 n= 2 时，c(n) = 1。对于较大的 n，c(n) = 2c(n/ 2 ) + 2。当 n 是 2 的幂时，使用迭代方法（见例 2 - 2 0） 可知 c(n) = 3n/ 2 - 2。在本例中，使用分而治之方法比逐个比较的方法少用了 2 5％的比较次数。 例 2-3 [矩阵乘法] 两个 n×n 阶的矩阵 A 与 B 的乘积是另一个 n×n 阶矩阵 C， 可表示为假如每一个 C(i, C j) 都用此公式计算，则计算 C 所需要的操作次数为 n3 m+n2 (n- 1) a，其中 m 表示一次乘法，a 表示一次加 法或减法。20为了得到两个矩阵相乘的分而治之算法，需要： 1) 定义一个小问题，并指明小问题是如何进行乘法运算 的； 2) 确定如何把一个大的问题划分成较小的问题，并指明如何对这些较小的问题进行乘法运算； 3) 最 后指出如何根据小问题的结果得到大问题的结果。为了使讨论简便，假设 n 是 2 的幂（也就是说， n 是 1， 2，4，8，1 6，.） 。 首先，假设 n= 1 时是一个小问题，n& 1 时为一个大问题。后面将根据需要随时修改这个假设。对于 1 ×1 阶的小矩阵，可以通过将两矩阵中的两个元素直接相乘而得到结果。 考察一个 n& 1 的大问题。可以将这样的矩阵分成 4 个 n/ 2×n/ 2 阶的矩阵 A1，A2，A3，和 A4。当 n 大于 1 且 n 是 2 的幂时，n/ 2 也是 2 的幂。因此较小矩阵也满足前面对矩阵大小的假设。矩阵 Bi 和 Ci 的定义 与此类似. 根据上述公式，经过 8 次 n/ 2×n/ 2 阶矩阵乘法和 4 次 n/ 2×n/ 2 阶矩阵的加法，就可以计算出 A 与 B 的乘积。因此，这些公式能帮助我们实现分而治之算法。在算法的第二步，将递归使用分而治之算法把 8 个小矩阵再细分（见程序 2 - 1 9） 。算法的复杂性为(n3 )，此复杂性与程序 2 - 2 4 直接使用公式（2 - 1）所 得到的复杂性是一样的。事实上，由于矩阵分割和再组合所花费的额外开销，使用分而治之算法得出结果 的时间将比用程序 2 - 2 4 还要长。 为了得到更快的算法， 需要简化矩阵分割和再组合这两个步骤。 一种方案是使用 S t r a s s e n 方法得到 7 个小矩阵。这 7 个小矩阵为矩阵 D, E, ., J，矩阵 D 到 J 可以通过 7 次矩阵乘法， 6 次矩阵加法，和 4 次 矩阵减法计算得出。前述的 4 个小矩阵可以由矩阵 D 到 J 通过 6 次矩阵加法和两次矩阵减法得出. 用上述方案来解决 n= 2 的矩阵乘法。将某矩阵 A 和 B 相乘得结果 C，如下所示： 因为 n& 1，所以将 A、B 两矩阵分别划分为 4 个小矩阵，每个矩阵为 1×1 阶，仅包含一个元素。1×1 阶 矩阵的乘法为小问题，因此可以直接进行运算。利用计算 D～J 的公式，得： D= 1（6-8）=-2 E= 4（7-5）= 8 F=（3 + 4）5 = 3 5 G=（1 + 2）8 = 2 4 H=（3-1） + 6）= 2 2 （5 I=（2-4） + 8）=-3 0 （7 J=（1 + 4） + 8）= 6 5 （5 根据以上结果可得： 对于上面这个 2×2 的例子， 使用分而治之算法需要 7 次乘法和 1 8 次加/减法运算。 而直接使用公式 - 1） （2 ， 则需要 8 次乘法和 7 次加/减法。要想使分而治之算法更快一些，则一次乘法所花费的时间必须比 11 次加/ 减法的时间要长。假定 S t r a s s e n 矩阵分割方案仅用于 n≥8 的矩阵乘法，而对于 n&8 的矩阵乘法则直接 利用公式（2 - 1） 进行计算。 n= 8 时，8×8 矩阵相乘需要 7 次 4×4 矩阵乘法和 1 8 次 4×4 矩阵加/减法。 则 每次矩阵乘法需花费 6 4m+ 4 8a 次操作， 每次矩阵加法或减法需花费 1 6a 次操作。 因此总的操作次数为 7 ( 6 4m+ 4 8a) + 1 8 ( 1 6a) = 4 4 8m+ 6 2 4a。而使用直接计算方法，则需要 5 1 2m+ 4 4 8a 次操作。要使 S t r a s s e n 方法比直接计算方法快，至少要求 5 1 2-4 4 8 次乘法的开销比 6 2 4-4 4 8 次加/减法的开销大。或者说 一次乘法的开销应该大于近似 2 . 7 5 次加/减法的开销。假定 n&1 6 的矩阵是一个“小”问题，S t r a s s e n 的分解方案仅仅用于 n≥1 6 的情况，对于 n&1 6 的矩阵相乘，直接利用公式（ 2 - 1） 。则当 n= 1 6 时使用 分而治之算法需要 7 ( 5 1 2m+ 4 4 8a) +1 8 ( 6 4a) = 3 5 8 4m+ 4 2 8 8a 次操作。 直接计算时需要 4 0 9 6m+ 3 8 4 0a 次操作。若一次乘法的开销与一次加/减法的开销相同，则 S t r a s s e n 方法需要 7 8 7 2 次操作及用于 问题分解的额外时间， 而直接计算方法则需要 7 9 3 6 次操作加上程序中执行 f o r 循环以及其他语句所花费 的时间。即使直接计算方法所需要的操作次数比 St r a s s e n 方法少，但由于直接计算方法需要更多的额外 开销，因此它也不见得会比 S t r a s s e n 方法快。n 的值越大，Strassen 方法与直接计算方法所用的操作次 数的差异就越大，因此对于足够大的 n，Strassen 方法将更快。设 t (n) 表示使用 Strassen 分而治之方法所 需的时间。因为大的矩阵会被递归地分割成小矩阵直到每个矩阵的大小小于或等于 k（k 至少为 8，也许更21大，具体值由计算机的性能决定）. 用迭代方法计算，可得 t(n) = (nl og27 )。因为 l og27 ≈2 . 8 1，所以与 直接计算方法的复杂性(n3 )相比，分而治之矩阵乘法算法有较大的改进。 注意事项 分而治之方法很自然地导致了递归算法的使用。在许多例子里，这些递归算法在递归程序中得到了很好 的运用。实际上，在许多情况下，所有为了得到一个非递归程序的企图都会导致采用一个模拟递归栈。不 过在有些情况下，不使用这样的递归栈而采用一个非递归程序来完成分而治之算法也是可能的，并且在这 种方式下，程序得到结果的速度会比递归方式更快。解决金块问题的分而治之算法（例 2 - 2）和归并排序 方法（ 2 . 3 节）就可以不利用递归而通过一个非递归程序来更快地完成。 例 2-4 [金块问题] 用例 2 - 2 的算法寻找 8 个金块中最轻和最重金块的工作可以用二叉树来表示。这棵树的 叶子分别表示 8 个金块（a, b,., h)，每个阴影节点表示一个包含其子树中所有叶子的问题。因此，根节点 A 表示寻找 8 个金块中最轻、最重金块的问题，而节点 B 表示找出 a,b,c 和 d 这 4 个金块中最轻和最重金块 的问题。 算法从根节点开始。 由根节点表示的 8 金块问题被划分成由节点 B 和 C 所表示的两个 4 金块问题。 在 B 节点，4 金块问题被划分成由 D 和 E 所表示的 2 金块问题。可通过比较金块 a 和 b 哪一个较重来解 决 D 节点所表示的 2 金块问题。在解决了 D 和 E 所表示的问题之后，可以通过比较 D 和 E 中所找到的轻 金块和重金块来解决 B 表示的问题。接着在 F，G 和 C 上重复这一过程，最后解决问题 A。 可以将递归的分而治之算法划分成以下的步骤： 1) 从图 2 - 2 中的二叉树由根至叶的过程中把一个大问题划分成许多个小问题，小问题的大小为 1 或 2。 2) 比较每个大小为 2 的问题中的金块，确定哪一个较重和哪一个较轻。在节点 D、E、F 和 G 上完成这种 比较。大小为 1 的问题中只有一个金块，它既是最轻的金块也是最重的金块。 3) 对较轻的金块进行比较以确定哪一个金块最轻，对较重的金块进行比较以确定哪一个金块最重。对于节 点 A 到 C 执行这种比较。 根据上述步骤， 可以得出程序 1 4 - 1 的非递归代码。 该程序用于寻找到数组 w [ 0 : n - 1 ]中的最小数和最大 数，若 n & 1，则程序返回 f a l s e，否则返回 t r u e。 当 n≥1 时，程序 1 4 - 1 给 M i n 和 M a x 置初值以使 w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。 首先处理 n≤1 的情况。若 n&1 且为奇数，第一个重量 w [ 0 ]将成为最小值和最大值的候选值，因此将有偶 数个重量值 w [ 1 : n - 1 ]参与 f o r 循环。当 n 是偶数时，首先将两个重量值放在 for 循环外进行比较，较 小和较大的重量值分别置为 Min 和 Max，因此也有偶数个重量值 w[2:n-1]参与 for 循环。 在 for 循环中， 外层 if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。 此工作与前面提到的分而治之 算法步骤中的 2) 相对应，而内层的 i f 负责找出较小重量值和较大重量值中的最小值和 最大值，这个工作对应于 3 )。for 循环将每一对重量值中较小值和较大值分别与当前的最小值 w [ M i n ] 和最大值 w [ M a x ]进行比较，根据比较结果来修改 M i n 和 M a x（如果必要） 。 下面进行复杂性分析。注意到当 n 为偶数时，在 for 循环外部将执行一次比较而在 f o r 循环内部执行 3 ( n / 2 - 1 )次比较，比较的总次数为 3 n / 2 - 2。当 n 为奇数时，f o r 循环外部没有执行比较，而内部执行了 3(n-1)/2 次比较。因此无论 n 为奇数或偶数，当 n&0 时，比较的总次数为「3n/2ù-2 次。 程序 14-1 找出最小值和最大值的非递归程序 template bool MinMax(T w[], int n, T& Min, T& Max) {// 寻找 w [ 0 : n - 1 ]中的最小和最大值 // 如果少于一个元素，则返回 f a l s e // 特殊情形： n &= 1 if (n & 1) if (n == 1) {Min = Max = 0;} / /对 Min 和 M a x 进行初始化22
// 循环起点 if (n % 2) {// n 为奇数 Min = Max = 0; s = 1;} else {// n 为偶数，比较第一对 if (w[0] & w[1]) { Min = 1; Max = 0;} else {Min = 0; Max = 1;} s = 2;} // 比较余下的数对 for (int i = i & i += 2) { // 寻找 w[i] 和 w [ i + 1 ]中的较大者 // 然后将较大者与 w [ M a x ]进行比较 // 将较小者与 w [ M i n ]进行比较 if (w[i] & w[i+1]) { if (w[i] & w[Max]) Max = if (w[i+1] & w[Min]) Min = i + 1;} else { if (w[i+1] & w[Max]) Max = i + 1; if (w[i] & w[Min]) Min =} } } 练习 1. 将例 1 4 - 1 的分而治之算法扩充到 n& 1 个硬币的情形。需要进行多少次重量的比较？ 2. 考虑例 1 4 - 1 的伪币问题。假设把条件“伪币比真币轻”改为“伪币与真币的重量不同” ，同样假定袋 中有 n 个硬币。 1) 给出相应分而治之算法的形式化描述，该算法可输出信息“不存在伪币”或找出伪币。算法应递归地将 大的问题划分成两个较小的问题。需要多少次比较才能找到伪币（如果存在伪币）？ 2) 重复 1) ，但把大问题划分为三个较小问题。 3. 1) 编写一个 C++ 程序，实现例 1 4 - 2 中寻找 n 个元素中最大值和最小值的两种方案。使用递归来完成 分而治之方案。 2) 程序 2 - 2 6 和 2 - 2 7 是另外两个寻找 n 个元素中最大值和最小值的代码。试分别计算出每段程序所需 要的最少和最大比较次数。 3) 在 n 分别等于 1 0 0，1 0 0 0 或 10 000 的情况下，比较 1） 、2）中的程序和程序 1 4 - 1 的运行时间。对 于程序 2 - 2 7，使用平均时间和最坏情况下的时间。1）中的程序和程序 2 - 2 6 应具有相同的平均时间和最 坏情况下的时间。 4) 注意到如果比较操作的开销不是很高，分而治之算法在最坏情况下不会比其他算法优越，为什么？它的 平均时间优于程序 2 - 2 7 吗？为什么？ 4. 证明直接运用公式（1 4 -2）~（1 4 - 5）得出结果的矩阵乘法的分而治之算法的复杂性为(n3 )。因此相应23的分而治之程序将比程序 2 - 2 4 要慢。 5. 用迭代的方法来证明公式（1 4 - 6）的递归值为(n l og27)。 *6. 编写 S t r a s s e n 矩阵乘法程序。利用不同的 k 值（见公式（1 4 - 6） ）进行实验，以确定 k 为何值时 程序性能最佳。比较程序及程序 2 - 2 4 的运行时间。可取 n 为 2 的幂来进行比较。 7. 当 n 不是 2 的幂时，可以通过增加矩阵的行和列来得到一个大小为 2 的幂的矩阵。假设使用最少的行数 和列数将矩阵扩充为 m 阶矩阵，其中 m 为 2 的幂。 1) 求 m / n。 2) 可使用哪些矩阵项组成新的行和列，以使新矩阵 A' 和 B' 相乘时，原来的矩阵 A 和 B 相乘的结果会出 现在 C' 的左上角？ 3) 使用 S t r a s s e n 方法计算 A' * B' 所需要的时间为(m2.81 )。给出以 n 为变量的运行时间表达式。 2.2 应用 2.2.1 残缺棋盘 残缺棋盘（defective chessboard）是一个有 2k×2k 个方格的棋盘，其中恰有一个方格残缺。图 2 - 3 给 出 k≤2 时各种可能的残缺棋盘，其中残缺的方格用阴影表示。注意当 k= 0 时，仅存在一种可能的残缺棋 盘（如图 1 4 - 3 a 所示） 。事实上，对于任意 k，恰好存在 22k 种不同的残缺棋盘。 残缺棋盘的问题要求用三格板（t r i o m i n o e s）覆盖残缺棋盘（如图 1 4 - 4 所示） 。在此覆盖中，两个三 格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。在这种限制条件下，所需要的三 格板总数为( 22k -1 ) / 3。可以验证( 22k -1 ) / 3 是一个整数。k 为 0 的残缺棋盘很容易被覆盖，因为它没有 非残缺的方格，用于覆盖的三格板的数目为 0。当 k= 1 时，正好存在 3 个非残缺的方格，并且这三个方格 可用图 1 4 - 4 中的某一方向的三格板来覆盖。 用分而治之方法可以很好地解决残缺棋盘问题。这一方法可将覆盖 2k×2k 残缺棋盘的问题转化为覆 盖较小残缺棋盘的问题。 2k×2k 棋盘一个很自然的划分方法就是将它划分为如图 1 4 - 5 a 所示的 4 个 2k - 1 ×2k - 1 棋盘。注意到当完成这种划分后， 4 个小棋盘中仅仅有一个棋盘存在残缺方格（因为原来的 2k× 2k 棋盘仅仅有一个残缺方格） 。首先覆盖其中包含残缺方格的 2k - 1×2k - 1 残缺棋盘，然后把剩下的 3 个 小棋盘转变为残缺棋盘，为此将一个三格板放在由这 3 个小棋盘形成的角上，如图 14-5b 所示，其中原 2k ×2k 棋盘中的残缺方格落入左上角的 2k - 1×2k - 1 棋盘。可以采用这种分割技术递归地覆盖 2k×2k 残 缺棋盘。当棋盘的大小减为 1×1 时，递归过程终止。此时 1×1 的棋盘中仅仅包含一个方格且此方格残缺， 所以无需放置三格板。 可以将上述分而治之算法编写成一个递归的 C++ 函数 Ti l e B o a r d (见程序 1 4 - 2 )。 该函数定义了一 个全局的二维整数数组变量 B o a r d 来表示棋盘。B o a r d [ 0 ] [ 0 ]表示棋盘中左上角的方格。该函数还定 义了一个全局整数变量 t i l e，其初始值为 0。函数的输入参数如下： ? tr 棋盘中左上角方格所在行。 ? tc 棋盘中左上角方格所在列。 ? dr 残缺方块所在行。 ? dl 残缺方块所在列。 ? size 棋盘的行数或列数。 Ti l e B o a r d 函数的调用格式为 Ti l e B o a r d（0,0, dr, dc,size)，其中 s i z e = 2k。覆盖残缺棋盘所需要的 三格板数目为( s i z e2 -1 ) / 3。函数 TileBoard 用整数 1 到( s i z e2-1 ) / 3 来表示这些三格板，并用三格板的 标号来标记被该三格板覆盖的非残缺方格。 令 t (k) 为函数 Ti l e B o a r d 覆盖一个 2k×2k 残缺棋盘所需要的时间。当 k= 0 时，s i z e 等于 1，覆 盖它将花费常数时间 d。当 k & 0 时，将进行 4 次递归的函数调用，这些调用需花费的时间为 4t (k-1 )。除 了这些时间外， if 条件测试和覆盖 3 个非残缺方格也需要时间，假设用常数 c 表示这些额外时间。可以24得到以下递归表达式： 程序 14-2 覆盖残缺棋盘 void TileBoard(int tr, int tc, int dr, int dc, int size) {// 覆盖残缺棋盘 if (size == 1) int t = tile++, // 所使用的三格板的数目 s = size/2; //