第五章 贪心算法 §1 基本思想 找零钱 假如售货员需要找给小孩 67 美分的零钱。现在，售货员 手中只有 25 美分、 10 美分、 5 美分和 1 美分的硬币。在小孩的催促 下，售货员想尽快将钱找给小孩。她的做法是：先找不大于 67 美分 的最大硬币 25 美分硬币，再找不大于 67－ 25＝ 42 美分的最大硬币 25 美分硬币，再找不大于 42－ 25＝ 17 美分的最大硬币 10 美分硬币， 再找不大于 17－ 10＝ 7 美分的最大硬币 5 美分硬币， 最后售货员再找 出两个 1 美分的硬币。至此，售货员共找给小孩 6 枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货 员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使 自己手中的钱数增加的尽量快些， 所以每一次都尽可能地捡面额大的 硬币。 装载问题 有一艘大船用来装载货物。假设有 n 个货箱，它们的 体积相同，重量分别是 n www ,, 21 L，货船的最大载重量是 c。目标 是在船上装最多货箱该怎样装？如果用 1= i x 表示装第 i 个货箱，而 0= i x 表示不装第 i 个货箱，则上述问题是解优化问题：求 x 1 , x 2 ,??????， x n ， 满足 cx i n i i ≤ ∑ =1 w (5.1) 使得 ∑ = n i i x 1 max (5.2) 贪心方法，顾名思义，是在决策中 总是作出在当前看来是最好的 选择 。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。 但是贪心方法并未考虑整体最 优解，它所作出的选择只是在某种意 义上的局部最优选择。当然，在 采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部 分问题，采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法，我们 将装载问题稍加推广，考虑 0/1 背包问题。 0/1 背包问题 已知容量为 M 的背包和 n 件物品。第 i 件物品的 重量为 w i ，价值是 p i 。因而将物品 i 的一部分 x i 放进背包即获得 p i x i 的价值。问题是：怎样装包使所获得的价值最大。即是如下的优化问 题： ∑ ≤≤ ni ii xp 1 max (5.3) niwpx Mxw iii ni ii ≤≤>>≤≤ ≤ ∑ ≤≤ 1,0,0,10 1 (5.4) 采用贪心方法，有几种原则可循： a.每次捡最轻的物品装； b.每次捡 价值最大的装； c.每次装包时既考虑物品的重量又考虑物品的价值， 也就是说每次捡单位价值 ii wp 最大的装。按原则 a 来装只考虑到多 装些物品，但由于单位价值未必高，总价值不能达到最大；按原则 b 来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的 物品少，未变能够达到总价值最大。比较合理的原则是 c。事实上， 按照原则 c 来装，确实能够达到总价值最大。 0/1背包问题贪心算法 GreedyKnapsack(p, w, M, x, n) //价值数组 p[1:n]、重量数组 w[1:n]， //它们元素的排列顺序是 p[i]/w[i]≥ p[i+1]/w[i+1]; M是背包容量， // x 是解向量 real p[1:n], w[1:n], x[1:n], M, rc; integer i, n; x=0; // 将解向量初始化为零 rc=M; // 是背包剩余容量初始化为 M for i from 1 to n do if w[i] > rc then exit endif x[i]=1; rc=rc-w[i]; endfor if i≤n then x[i]=rc/w[i]; endif end GreedyKnapsack 定理 1 如果 p[1]/w[2]≥p[2]/w[2]≥ ??????≥p[n]/w[n],则 GreedyKnapsack 对于给定的0/1 背包问题实例生成一个最优解。 证明 设x=(x 1 ,x 2 ,??????,x n )是GreedyKnapsack 所生成的解， 但不是 最优解。因而必有某个x i 不为1。不妨设x j 是第一个这样的分量。于 是，当1 ≤ i<j时，x i ＝1；当j<i ≤n 时，x i ＝0；当i=j 时，0 ≤x i <1。 因为 x 不是最优解，则存在解向量 y=(y 1 ,y 2 ,??????,y n ),使得 ∑∑ > iiii xpyp 。不妨假定 Mxw ii = ∑ 。设 k 是使得 y k ≠ x k 的最小 下标， 则y k < x k . 这是因为：当k<j 时，x k =1,上述不等式自然成立； 当k ≥j 时，因为x 1 =y 1 , x 2 =y 2 ,??????, x k-1 = y k-1 ，当k<i ≤n时，x i ＝0，所 以由y k > x k 可推出 Mxwyw iiii => ∑∑ ，y 不是解向量，矛盾。 现在取新的向量z=(z 1 ,z 2 ,??????,z n )满足 z 1 =y 1 , z 2 =y 2 ,??????, z k-1 = y k-1 , z k = x k 0≤z k+1 ≤y k+1 , ??????, 0≤z n ≤y n 而且 )()( 1 kkk nik iii yzwzyw ?=? ∑ ≤≤+ 这样的向量z 是存在的，而且是0/1 背包问题的解，因为 Myw ywyw zwzwywzw ni ii nik ii ki ii nik iikk ki ii ni ii ≤= += ++= ∑ ∑∑ ∑∑∑ ≤≤ ≤≤?≤≤ ≤≤+?≤≤≤≤ 1 11 1111 (5.5) 至此，我们找到一个新的解向量z。以下证明它的总价值不小于 y 的 总价值： ∑ ∑∑ ∑∑∑ ≤≤ ≤≤+≤≤ ≤<≤≤≤≤ = ? ? ? ? ? ? ???+≥ ???+= ni ii kk nik iiikkk ni ii ii nik iiikkkkk ni ii ni ii yp wpwzywyzyp wpwzywpwyzypzp 1 11 11 /)()( /)(/)( (5.6) 中间的不等式是由于当I>k 时有p k /w k ≥p i /w i 而得。 但与 x的不同分量 的个数比 y与x的不同分量的个数至少减少一个。 以z 代替y 进行上 面的讨论，我们又可以找到新的解向量 'z ，如此等等，由于分量的个 数n有限，必到某一步停止，我们能找到解向量y*,它和x有相同的 分量，又与y又有相同的总价值（大于x的总价值） ，矛盾。 这个矛 盾源于x 不是最优解的假设。故，x 是最优解。 贪心算法主要用于处理优化问题。 每个优化问题都是由目标函数 和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函 数取极值的可行解称为最优解。如 0/1 背包问题是一个优化问题，式 (5.3)中的函数是目标函数，而 (5.4)式描述的要求是约束条件，这里优 化是使目标函数取最大值。 贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化，但在局部择优中是朝着 整体优化的方向发展 的。为此，贪心算法首先要确定一个度量准则，每一步都是按这个准 则选取优化方案。如 0/1 背包问题的贪心准则是 选取单位价值 p/w 最 大物品 ，而装载问题的贪心算法选取的准则是 选取最轻的货箱 ，找零 钱问题所用的贪心准则是 选取面值最大的硬币。 对于一个给定的问 题，初看起来，往往有若干中贪心准则可选，但在实际上，其中的多 数都不能使贪心算法达到问题的最优解。 如 0/1 背包问题下面的实例： n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将 物品 1 装包，此时获得效益值 25，包的剩余容量是 2。然后考虑将物 品 2 装包，但物品 2 的重量 15 超出包的剩余容量，只能装入该种物 品的 2/15，此时获得的总效益值为 25+24× 2/15=28.2。这样得到的可 行解（ 1， 2/15， 0）并不是最优解。事实上，如果以单位价值最大为 贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值 (25/18, 24/15, 15/10)=(1.389, 1.6, 1.5)。首先考虑单位价值大的物品装 包，即将物品 2 装包，此时获得效益值 24，背包的剩余容量是 5。然 后考虑装物品 3，由于物品 3 的重量超出背包的剩余容量，只能装入 该物品 5/15=1/2, 至此背包已经装满，所得的总的效益值为 24+15/2=31.5。比前面的装法的效益值大。实践证明，选择能产生最 优解的贪心准则是设计贪心算法的核心问题。 以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i from 1 to n do x=Select(A); if Feasible(solution, x) then solution=Union(solution, x); endif endfor return(solution); end Greedy 这里 Select(A)是按照谈心准则选取 A 种的输入项； Feasible(solution, x)是判断已知的解的部分 solution与新选取的 x的结合 Union(solution, x)是否是可行解。过程 Greedy 描述了用贪心策略设计算法的主要工 作和基本控制流程。 一旦给出一个特定的问题， 就可将 Select， Feasible 和 Union 具体化并付诸实现。 §2 作业排序问题 null 活动安排问题 我们首先从活动安排这一简单课题入手。 该问题要求高效地安排 一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题： 已知 n 个活动 E={1, 2, … ,n }要求使用同一资源，第 k 个活动要求的开始和结束时间为 s k , f k , 其中 s k < f k , k=1, 2, … , n . 活动k 与活动j 称为相容的如果 s k > f j 或者 s j > f k 。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集 。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排 最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结 束时间分别用两个数组 s 和 f 存储，并使得数组中元素的顺序按结束 时间非减排列： f 1 ≤ f 2 ≤… ≤ f n 。 活动安排贪心算法伪代码 GreedyAction(s, f， n) // s[1:n]、 f[1:n]分别代表 n 项活动的起始 //时间和结束时间 , 并且满足 f[1]≤ f[2]≤… ≤ f[n] j=1; solution={1}; //解向量初始化为空集 for i from 2 to n do if s i ≥f j then solution=solution ∪ {j}; // 将 j 加入解中 j=i; endif endfor return(solution); end Greedy 例子 设待安排的 11 个活动的开始时间和结束时间按结束时间的 非减次序排列如下： k 1 2 3 4 5 6 7 8 9 10 11 s[k] 1√ 3 0 5√ 3 5 6 8√ 8 2 12√ f[k] 4 5 6 7 8 9 10 11 12 13 14 解集合为 {1,4,8,11}.容易证明算法 GreedyAction 所得到的解是最 优解。 null 带限期作业安排问题 将活动排序问题加上效益条件，即 是下面的单机作业排序问题。 为使问题简化，我们假定完成每项作业的时间都是都是一样的，比如 都是 1。 问题： 已知 n 项作业 E={1, 2, … ,n }要求使用同台机器完成， 而且每项作业需要的时间都是 1。 第 k 项作业要求在时间 f k 之前完成 , 而且完成这项作业将获得效益 p k ， k=1, 2, … , n 。 E 的子集称为相 容的，如果它们可以被安排由一台机器完成（该台机器在同一时刻至 多完成一个作业） 。带限期作业排序问题就是要在所给的作业集合中 选出总效益值最大的相容子集 。 这个问题可以看作是活动安排问题的推广， 作业 i 的起始时间 为 0≤s i ≤f i -1. 而活动安排问题中的效益值可以认为全是 1。因此，很 容易想到贪心准则应该是尽量选取效益值最大的作业安排。 但由于起 始时间是一个区间， 可以将后面考虑的作业插到前面安排时剩余的空 闲时间片里，这是不同的地方。 带限期作业安排的贪心算法伪代码 GreedyJob(f, p, n) //f[1:n]和 p[1:n]分别代表各项作业的限期和效益 //值，而且 n 项作业的排序满足： p 1 ≥ p 2 ≥ … ≥ p n local J; J={1}; for i from 2 to n do if J ∪ {i} 中的作业是相容的 then J= J ∪ {i}; // 将 i 加入解中 endif endfor end GreedyJob 定理 2 算法 GreedyJob 对于作业排序问题总是得到最优解。 证明：假设贪心算法所选择的作业的集合 J 不是最优解，则一定 有相容的作业子集 I，其产生更大的效益值。并假定 I 是具有最大效 益值的相容作业子集中使得 I ∩ J最大者。这两个作业集之间没有包 含关系。这是因为算法 GreedyJob 的特性和假定 I 产生的效益值比 J 的效益值更大。 假设 a 是 J\I 中具有最大效益的作业，于是， J 中比 a 具有更多效益的作业都应该在 I 中。对于任何元素 b∈I\J，我们有 p a ≥p b 。否则，由 p a <p b 可推出 b∈J，因为按照算法 GreedyJob， b 将先 于 a 被考虑是否该加入 J 中。而 J 中那些效益比 a 效益大的作业也允 许将 b 加入 J，因为它们在 I 中是相容的。 如果用 S I 和 S J 分别记对应于 I 和 J 的调度表，并且 i∈I ∩ J， i 项 作业在 S J 和 S I 中分别属于时间段 [t, t+1]和 [t’, t’+1]。若 t<t’，则在 S J 中将 i 项作业与 S J 在时间段 [t’, t’+1]内排序的作业（如果有的化）交 换，这样得到的调度表 S J ’还是相容的。同样讨论 t>t’情形。由此，我 们可以假设 I ∩ J 中作业在 S I 和 S J 中有相同的排序时间表。现在假设 排序时间表 S J 中，作业 a 被安排在时间片 [t a , t a +1]中。则排序时间表 S I 一定有某个作业 b∈I\J 被安排在时间片 [t a , t a +1]中。不然，在排序表 S I 中，时间片 [t a , t a +1]空闲，将作业 a 安排在这个时间片调度，将会 得到效益值更大的相容作业子集，这与 I 的假设矛盾。现在，将 S I 中的时间片 [t a , t a +1]换成调度作业 a，则得到新的相容作业集合 I’=(I\{b})∪{a}。显然 I’的效益值不低于 I 的效益值，但 I’ ∩ J 比 I ∩ J 的元素至少少一个，与前面的假设矛盾。 证毕 在上述算法中，每次新的作业 i 填入之前，都要做一次判断，实 际上是检查在 [0,1],[1,2], ?????， [f i -1,f i ]中是否还有空闲的时间片？若有， 则选择其中之一安排作业 i；否则，作业 i 将被搁置。实现的方法有 两种。 第一种方法是基于问题的这样一个特点， 即每项作业都是在单位 时间内完成的，因此，只要关注截止期限的不增序列是否可以插入其 它的作业期限即可。 假设已经安排的作业的期限已经按递增的顺序排 好： )()()( 21 k jDjDjD ≤≤≤L，则下一个具有期限 )(iD 的作业可 以插入 )()( 1+ ≤ qq jDjD 如果下述两个条件满足： a). )(}1),(max{ iDqjD q ≤+ ； b). klqforljDjDiD lq ≤<>< + )(),()( 1 。 按这个准则，得到算法 GreedyInsertJob： 带限期作业的贪心插入算法 GreedyInsertJob(D, J, n, k) // D(1), … , D(n)是期限值。作业已按效 //益值 p i 的不增顺序排列。 J[i]是最优解中第 i 个作业，终止时 //被选中的作业按期限值的不减次序排列 D[J[i]]≤ D[J[i+1]]， //1≤ i<k. integer D[0:n], J[0:n], i, k, n, r ; D[0]=J[0]=0; //初始化 k=1; J[1]=1; //初始记入作业 for i from 2 to n do r=k; while D[J[r]]>D[i] && D[J[r]]≠r do r=r-1; endwhile if D[J[r]]≤D[i] && D[i]>r then //把作业 i 插入 J for i from k by –1 to r+1 do J[i+1]=J[i]; endfor J[r+1]=I; k=k+1; endif endfor end GreedyInsertJob 不难算出该算法的时间复杂度为 O(n 2 ). 值得主要的是，这里大 部分的时间都浪费在插入作业时移动已经被选作业的位置上。 为了回 避这个问题，我们可以在逃选作业时就做“适当的安排” ：使被考虑 的作业尽量地向后安排，这引导出第二种处理方法。 第二种方法：如果 J 是作业的可行子集（已经被选定的作业） ， 那么可以使用下述规则来确定这些作业中的每一个作业的处理时间： 若还没有给作业 i 分配处理时间，则分配给它时间片 ],1[ αα ? ，其中 α应尽量取大且使得时间片 ],1[ αα ? 是空的。为实现这种算法，我们 引入集合的不相交并运算 Union(i,j)和寻找元素 i 所属集合的程序 Find(i). 这里采用集合的树表示，根 k 代表它所在的集合。 Union(i,j) 是将以 i 为根的树所代表的集合与以 j 为根的树所代表的集合合并成 一个新的集合，新集合的树根是 i 或 j 依它们所在的集合的元素多少 而定（在此，我们取多者） 。为此，对每个集合都有一个统计该集合 元素个数的计数器， 一般是采取减的办法， 空集的初始计数器值为 0。 每添加一个元素该集合的计数器值减 1。 设有 n 个带期限的作业需要安排， ]}}[],...,1[max{,min{ nDDnb = ， 我们只需考虑时间片 [1,2], [2,3], … , [b-1, b]。为叙述方便，再加进时 间片 [0, 1]。考虑集合 U＝ {[0, 1] ,[1,2], [2,3], … , [b-1, b]}子集。为简 便，用 k 来代表时间片 [k, k+1]。初始被考虑的子集有 b+1 个，它们 分别是这 b+1 个元素构成的单元素子集 {k}，代表它的树的根为 F(k)=k,元素个数计数器值为 P(k)=-1。 带期限作业的快速安排算法 GreedyTreeJob(D, n, b, J, k) //找最优解 J={J[1], J[2], … , J[k]},假 //定 p 1 ≥ p 2 ≥ ?????? ≥ p n ， ]}}[],...,1[max{,min{ nDDnb = integer b, D[n], J[n], F[0:b], P[0,b]; for i from 0 to n do F[i]=I; P[i[=-1; // 将树初始化 endfor k=0; // 初始化 J for i=1 to n do //开始使用贪心准则 j=Find(min{n,D[i]}); if F[j]≠0 then k=k+1; J[k]=I; //选择作业 i s＝ Find(F[j]-1); F[j]=F[s]; t=Union(s, j); P[t]=P[s]+P[j]; endif endfor end GreeduTreeJob 例子 设 n=7, (p 1 , p 2 ,… , p n )=(35,30,25,20,15,10,5), (d 1 , d 2 ,… , d n )=(4,2,4,3,4,8,3), 算法 GreedyTreeJob 的执行过程见文档“快速作业 调度” 。 null 多机调度问题 设有 n 项独立的作业 {1,2,…, n},由 m 台相同的机器加工处理。 作 业 i 所需要的处理时间为 t i 。约定：任何一项作业可作任何一台机器 上处理， 但未完工前不准中断处理； 任何作业不能拆分更小的子作业。 多机调度问题要求给出一种调度方案， 使所给的 n 个作业在尽可 能短的时间内由 m 台机器处理完 。 这是一个 NP 完全问题，到目前为止还没有一个有效的解法。利 用贪心策略，有时可以设计出较好的 近似解。可以采用谈心准则： 最 长处理时间作业优先处理， 给出贪心算法（课后练习） 。 例子 设有 7 项独立的作业 {1,2,3,4,5,6,7},要由三台机器 M 1 , M 2 , M 3 处理。各个作业所需要的处理时间分别为 {2,14,4,16,6,5,3}.将作业 按需时间的长短排列： [4, 2, 5, 6, 3, 7,1].首先将作业 4 安排给机器 M 1 处理，此时，机器 M 1 机器被占用的时间是 16，而机器 M 2 , M 3 被占 用的时间都是零，所以，应将作业 2 安排给机器 M 2 来处理，作业 5 应安排给机器 M 3 来处理，至此，作业 M 1 , M 2 , M 3 被占用的时间分 别是 16、 14、 6。接下去应安排作业 6，因为机器 M 3 能空闲下来的时 间最早，所以作业 6 应安排给机器 M 3 。此时，机器 M 1 , M 2 , M 3 能够 空闲下来的时刻分别是 16、 14、 11。所以下面将要安排的作业 3 应 安排给机器 M 3 。此时，机器 M 1 , M 2 , M 3 能够空闲下来的时刻分别是 16、 14、 15。 即将安排的作业 7 应安排给机器 M 2 ， 此时， 机器 M 1 , M 2 , M 3 能够空闲下来的时刻分别是 16、 17、 15。即将安排的作业 1 应安 排给机器 M 3 。如此全部作业均已安排完毕，所需要的时间是 17。这 里采用的调度方案是： 将需要时间最长的未被安排作业首先安排给能 够最早空闲下来的机器处理 。 M 1 16 M 2 14+3 M 3 6+5+4+2 §3 最小生成树 考虑无向图 G=(V, E)，不妨假定该图代表城市间的交通情况，顶 点代表城市，边代表连接两个城市的可能的交通线路。现在将每条边 赋予一个权值，这些权可以代表建造该条线路的成本、交通线的长度 或其它信息。这样得到一个赋权图。在实际问题中，人们往往希望在 结构上选择一组交通线， 它们 连接所有的城市并且具有最小的建造总 成本 。这个问题相当于求取连通赋权图的具有最小权值的生成树。我 们称之为最优生成树。贪心方法可以很好地解决此类问题。在此介绍 两种算法： Prim 算法和 Kruskal 算法。 Prim 算法的基本思想是： 1). 选择图 G 的一条权值最小的边 e 1 ； 作业 4 作业 2 作业 5 作业 6 3 7 1 2). 假设 G 的一棵子树 T 已经确定； 3). 选择 G 的不在 T 中的具有最小权值的边 e，使得 T∪{e}仍是 G 的一棵子树。 10 （ 1， 2） 1 Prim 30 45 50 （ 2， 6） 40 35 算 2 5 （ 6， 3） 25 法 20 4 55 3 （ 6， 4） 15 （ 3， 5） 10 （ 1， 2） 1 Kruskal 30 45 50 （ 6， 3） 40 35 算 4 5 （ 6， 4） 25 法 20 3 55 2 （ 6， 2） 15 （ 5， 3） Kruskal 算法的基本思想是： 1). 选择图 G 的一条权值最小的边 e 1 ； 2). 假设已经选好 G 的一组边 L={e 1 ,e 2 ,…,e k }; 3). 选择 G 的不在 L 中的具有最小权值的边 e k+1 ，使得 T∪{e}诱 导出的 G 的子图不含 G 的圈。 Prim最小生成树算法伪代码 PrimTree(E,COST,a,T,mincost) //E是图G的边集， 1 2 4 5 6 3 4 5 6 3 1 2 //COST(n,n)是G 的带权邻接矩阵。计算一棵最小生成树T //并把它作为一个集合存放到数组T[1:n-1,2]中，这棵树 //的权值赋给mincost 1 real COST[n,n],mincost; 2 integer NEAR[n],n,I,j,k,s,T[1：n-1,2]; 3 (k,s)=具有最小权值的边； 4 mincost＝COST(k,s); 5 for i from 1 to n do 6 if COST(I,s)<COST(I,k) then 7 NEAR(i)=s; 8 else NEAR(i)=k; 9 endif 10 endfor 11 NEAR(k)=NEAR(s)=0; 12 for i from 2 to n-1 do 13 设j是使得NEAR(j) ≠0且COST(j,NEAR(j))为最小的下标 14 (T[i,1],T[i,2])=(j,NEAR(j)); // 加入边 （j， NEAR(j)） 15 mincost=mincost+COST(j,NEAR(j)); 16 NEAR(j)=0; 17 for k from 1 to n do 18 if NEAR(k)≠0 && COST(k,NEAR(k))>COST(k,j) then 19 NEAR(k)=j; 20 endif 21 endfor 22 endfor 23 if mincost≥∞ then 24 print(‘no spanning tree’); 25 endif 26 end PrimTree 这里，树T的元素为(T[i,1],T[i,2]),其中1，2代表第i条边的两 个端点。NEAR(j)表示顶点j 的以最小权的边邻接的一个顶点。 PrimTree 算法的时间复杂度分析：语句 3 需要 O(|E|)的时间； 语句 17 至 21 的循环体需要时间 O(n)，因而从语句 12 到 22 的循环 体共需要时间O(n 2 )。所以,PrimTree算法的时间复杂度为O(n 2 ). 为叙述 Kruskal 算法，我们引进数据结构 min-堆：它是一个完 全二叉树，其中每个顶点都有一个权值，而且该二叉树满足：每个顶 点的权值都不大于其儿子的权值。min-堆的根具有最小的权值。 10 1 30 45 50 一个赋权图 40 35 和 4 5 它的边 min-堆 25 15 20 3 55 2 (1,2) (6,4) (6,3) (2,5) (3,5) (4,1) (6,2) (2,3)(6,5)(5,1) 4 5 6 3 1 2 Kruskal最优生成树算法伪代码 KruskalTree(E,COST,n,T,mincost)//说明同算法PrimTree 1 real mincost, COST[1:n,1:n]; 2 integer Parent[1:n],T[1:n-1],n; 3 以带权的边为元素构造一个min-堆； 4 Parent=-1;//每个顶点都在不同的集合中 5 i=mincost=0; 6 While i<n-1 && min-堆非空 do 7 从堆中删去最小权边（u，v）并重新构造min-堆； 8 j=Find(u); k=Find(v); 9 if j≠k then 10 i=i+1; T(i,1)=u; T(i,2)=v; 11 mincost=mincost+COST(u,v); 12 Union(j,k); 13 endif 14 endwhile 15 if i≠n-1 then 16 print(‘no spanning tree’) 17 endif 18 return 19 end KruskalTree 定理3 Kruskal 算法对于每一个无向连通图产生一棵最优树。 证明：设 T 是用Kruskal 算法产生的 G 的一棵生成树，而T’是 G的一棵最优生成树且使得|E(T’) ∩E(T)|最大。用E(T)表示树 T 的 边集，w(e)表示边 e 的权值，而边集 E 的权值之和用 w(E)表示。以 下证明w(E(T))=w(E(T’)).不妨设E(T) ≠E(T’),而e是E(T)\E(T’) 中权值最小的边。将 e 添加到 T’中即得到 T’的一个圈：e， e 1 ,e 2 ,…,e k 。因为T 是树，诸e i 中至少有一个不属于 E(T)。不妨设 e i 不属于E(T),则必然有w(e) ≤w(e i )。否则，w(e)>w(e i )和E(T)中比 e 权值小的边都在 T’中， e i 同这些边一起不含有圈，因而，按 Kruskal 算法，e i 将被选到 E(T)中。矛盾。在 T’中去掉边 e i ，换上 边e，得到G的一棵新的生成树T”,这棵树有两个特点：a).T”权值 不大于 T’的权值，因而与 T’有相等的权值；b).|E(T”) ∩E(T)|> |E(T’) ∩E(T)|.a)说明T”也是一棵最优树， 而b)说明与T’取法相 悖。因此w(E(T))=w(E(T’))，T 是最优生成树。证毕 §4 单点源最短路径问题 问题： 已知一个赋权有向图 G=(V,E，w),求由G中某个指定的顶 点v 0 其它各个顶点的最短的路径 。 45 50 10 路径 长度 (1) v0v2 10 10 35 (2) v0v2v3 25 20 15 20 30 (3) v0v2v3v1 45 15 3 (4) v0v4 45 一个加权有向图 从v 0 到其它各个顶点的最短路径 V 0 V 2 V 1 V 4 V 5 V 3 对于一般的单点源最短路径问题， 我们采用逐条构造最短路径的 办法， 用迄今已生成的所有路径长度之和为最小作为贪心准则， 为此， 每一条单独的路径都必须具有最小长度。 假定已经构造了k条最短路 径，则下面要构造的路径应该是下一条最短的最小长度路径。现在这 这k条最短路径的终点之集记为S，为陈述方便，也将 v 0 放于S 中。 如果V\S不是空集， 则从v 0 到V\S中顶点的最短路径中应该有一条最 短的，比如是v 0 到v k+1 的最短路径P： P=v 0 u 1 …u s-1 u s v k+1 (5.7) 显然，P 1 =v 0 u 1 …u s-1 u s 应是 v 0 到u s 最短路径，因而由 S 的定义和我们 贪心准则，u s 应属于S，同理，路径 P上其它顶点u i 也都在S 中。所 以，新的最短路径一定是某个已有的最短路径向前延伸一步。如果用 Dist(v i )记从v 0 到 S 中顶点 v i 的最短路径的长度，而图 G中的顶点w 依其属于 S与否分别记之为 S(w)=1或S(w)=0，则从v 0 出发，新的最 短路径的长度应该是 D(S)= )},()({min 0)(,1)( wuCOSTuDist wSuS + == (5.8) 满足(5.8)式的顶点w被选择加入S， 新的最短路径就是从v 0 出发到 w 的最短路径,而此时的Dist(w)=D(S)， S被被更新为S’=S ∪{w},后者 可以由更新w的集合特征值来实现：S(w)=1(原来S(w)=0).上述算法 思想是Dijkstra提出的。 Dijkstra最短路径算法伪代码 DijkstraPaths(v,COST,Dist,n)//G是具有n个顶点{1,2,…,n} //的有向图， v 是G 中取定的顶点，COST 是G 的邻接矩阵 boolean S[1:n]; real COST[1:n,1:n],Dist[1:n]; integer u,v,n,num,i,w; 1 for i from 1 to n do 2 S(i)=0; Dist(i)=COST(v,i); 3 endfor 4 S(v)=1; Dist(v)=0; 5 for num from 2 to n do 6 选取顶点w使得 )}({min)( 0)( uDistwDist uS = = 7 S(w)=1; 8 while S(u)=0 do 9 Dist(u)=min{Dist(u),Dist(w)+COST(w,u)}; 10 endwhile 11 endfor 12 end DijkstraPath 这里，我们需要注意语句 6 和 9。根据(5.8)式，被选择的新的最短 路径的长度应该等于语句 6 中的 )}({min 0)( uDist uS = ，这可由语句 9 中的 Dist值更新语句看出。因为当S变成 S’=S ∪{w}后，Dist(u)(u不属 于S’)值如果改变， 则必然是由于从v到u的最短路径上含有顶点w， 又由于从 v 到 S’中其它顶点的最短路径不含有顶点 w，所以 w 是从 v 到 u 的最短路径上最后一个内部顶点，故 Dist(u)=min{Dist(u),Dist(w)+COST(w,u)}。 算法DijstraPath的正 确性由此可以保证。