第4章贪心方法.ppt

《第4章贪心方法.ppt》由会员分享，可在线阅读，更多相关《第4章贪心方法.ppt（82页珍藏版）》请在三一文库上搜索。

1、第四章 贪心方法 Date 本章教学要求及重点难点 n理解贪心方法的基本思想 n掌握背包问题的求解方法 n掌握带有限期的作业排序的基本方法 n掌握用贪心方法求解单源点最短路径的基本方 法。 n重点：用贪心方法求背包问题及带有限期作业 排序； n难点：用贪心方法求单源点最短路径。 Date 4.1 一般方法 1. 问题的一般特征 问题有n个输入，问题的解是由这n个输入的某个子集组成，这个子 集必须满足某些事先给定的条件。 n 约束条件：子集必须满足的条件； n 可行解：满足约束条件的子集；可行解可能不唯一； n 目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出； n 最优解：能够使目标函

2、数取极值（极大或极小）的可行解。 分类：根据描述问题约束条件和目标函数的数学模型的特性和问题的 求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规 划等。 最优化问题求解 贪心方法：一种改进的分级的处理方法，可对满足上述特征的某些问 题方便地求解。 Date 例找零钱 一个小孩买了价值少于1元的糖，并将1元的钱 交给售货员。售货员希望用数目最少的硬币找给小孩。假设 提供数目不限的面值为25分、10分、5分及1分的硬币。售货 员分步骤组成要找的零钱数，每次加入一个硬币。 选择硬币时所采用的贪心算法如下：每一次选择应使零钱 数尽量增大。为确保解法的可行性（即：所给的零钱等于要 找的零钱

3、数），所选择的硬币不应使零钱总数超过最终所需 的数目。 假设需要找给小孩67分，首先入选的是两枚25分的硬币， 第三枚入选的不能是25分的硬币，否则将不可行（零钱总数 超过67分），第三枚应选择10分的硬币，然后是5分的，最 后加入两个1分的硬币。 贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应 使找出的硬币数目最少（至少是接近最少的数目） Date 2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定 的条件的子集组成。 1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输 入排序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度

4、意义下的部分最优解加在 一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将 当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2）贪心方法 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心 方法 注： 贪心解 最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优 解 3）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。 Date 3. 贪心方法的抽象化控制描述 procedure GREEDY(A,n) /A(1:n)包含n个输入/ solution /将解向量solution初始化为为空/ for i1 to n do xSELECT(A) /按照

5、度量标标准，从A中选择选择 一个输输入，其值赋值赋 予x 并将之从A中删删除/ if FEASIBLE(solution,x) then /判定x是否可以包含在解向量中， 即是否能共同构成可行解/ solutionUNION(solution,x) /将x和当前的解向量合并成新的解 向量，并修改目标标函数/ endif repeat return(solution) end GREEDY Date 4.2 背包问题 1.问题的描述 已知n种物品具有重量(w1,w2,wn)和效益值(p1,p2,pn) ，及一个 可容纳M重量的背包；设当物品i全部或一部分xi放入背包将得到pi xi的效 益，这里

6、，0 xi 1, pi 0。 问题：采用怎样的装包方法才能使装入背包的物品的总效益最大？ 分析： 装入背包的总重量不能超过M 如果所有物品的总重量不超过M，即 M，则把所有的物 品都装入背包中将获得最大可能的效益值 如果物品的总重量超过了M，则将有物品不能（全部）装 入背包中。由于0xi1，所以可以把物品的一部分装入背包，所以最 终背包中可刚好装入重量为M的若干物品（整个或一部分） 目标：使装入背包的物品的总效益达到最大。 Date 问题的形式描述 目标函数： 约束条件： 可 行 解：满足上述约束条件的任一集合(x1,x2,xn) 都是问题 的一个可行解可行解可能为多个。 (x1,x2,xn)

7、称为问题的一个解向量 最 优 解：能够使目标函数取最大值的可行解是问题的 最优解最优解也可能为多个。 Date 例4.1 背包问题的实例 设，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下： (x1,x2,x3) (1/2,1/3,1/4) 16.5 24.25 /没有放满背包/ (1, 2/15, 0 ) 20 28.2 (0, 2/3, 1) 20 31 (0, 1, 1/2) 20 31.5 Date 2. 贪心策略求解 度量标准的选择：三种不同的选择 1）以目标函数作为度量标准 即，每装入一件物品

8、，就使背包背包获得最大可能的效益增 量。 该度量标准下的 处理规则： 按效益值的非增次序将物品一件件地放入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果 该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品 种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。 如：若M=2,背包外还剩两件物品i,j，且有(pi 4，wi4) 和(pj 3，wj2)，则下一步应选择j而非i放入背包： pi/2 = 2 pj 3 Date 实例分析（例4.1) (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1p2 p3

9、首先将物品1放入背包，此时x11，背包获得p125的效益增量，同时背包容 量减少w118个单位，剩余空间M=2。 其次考虑物品2和3。就M=2而言有，只能选择物品2或3的一部分装入背包。 物品2： 若 x22/15， 则 p2 x216/53.1 物品3： 若 x32/10， 则 p3 x33 为使背包的效益有最大的增量，应选择物品2的2/15装包，即 x22/15 最后，背包装满， M=0，故物品3将不能装入背包，x30 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 28.2 (次优解,非问题的最优解) Date 2）以容量作为度量标准 以目标函数作为度量标准所存在的问题：尽

10、管背包的效 益值每次得到了最大的增加，但背包容量也过快地被消耗掉 了，从而不能装入“更多”的物品。 改进：让背包容量尽可能慢地消耗，从而可以尽量装入 “更多”的物品。 即，新的标准是：以容量作为度量标准 该度量标准下的处理规则： 按物品重量的非降次序将物品装入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满 背包； Date 实例分析（例4.1) (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) w3w2 w1 首先将物品3放入背包，此时x31，背包容量减少w310个单位 ，还剩余空间M=10。同时，背包获得p315的效益增量。 其次考虑

11、物品1和2。就M=10而言有，也只能选择物品1或2的一 部分装入背包。为使背包的按照“统一”的规则，下一步将放入物品2 的10/15装包，即 x210/152/3 最后，背包装满M=0，故物品1将不能装入背包，x10 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 31 (次优解,非问题的最优解) 存在的问题：效益值没有得到“最大”的增加 Date 3）最优的度量标准 影响背包效益值得因素： n 背包的容量M n 放入背包中的物品的重量及其可能带来的效益值 可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间 取得平衡，即每次装入的物品应使它所占用的每一单位容量能获得当前

12、最大的单位效益。 在这种策略下的量度是：已装入的物品的累计效益值与所用容量之 比。 故，新的量度标准是：每次装入要使累计效益值与所用容量的比值 有最多的增加（首次装入）和最小的减小（其后的装入）。 此时，将按照物品的单位效益值：pi/wi 比值（密度）的非增次序考 虑。 Date 实例分析（例4.1) (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1/w1p3/w3 p2/w2 首先将物品2放入背包，此时x21，背包容量减少w215个单 位，还剩余空间M=5。同时，背包获得p224的效益增量。 其次考虑物品1和3。此时，应选择物品3,且就M

13、=5而言有，也 只能放入物品3的一部分到背包中 。即 x35/101/2 最后，背包装满M=0，故物品1将不能装入背包，x10 。 背包最终可以获得效益值 x1 p1 x2 p2x3 p3 31.5 (最优解) Date 3. 背包问题的贪心求解算法 算法4.2 背包问题的贪心算法 procedure GREEDYKNAPSACK(P,W,M,X,n) /p(1:n)和w(1:n)分别含有按P(i)/W(i)P(i1)/W(i1)排序的n 件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解 向量/ real P(1:n),W(1:n),X(1:n),M,cu; integer I,n

14、 X0 /将解向量初始化为空/ cuM /cu是背包的剩余容量/ for i1 to n do if W(i) cu then exit endif X(i) 1 cu cu-W(i) repeat if in then X(i) cu/W(i) endif end GREEDY-KNAPSACK Date 4. 最优解的证明 即证明：由第三种策略所得到的贪心解是问题的最优解。 最优解的含义：在满足约束条件的情况下，可使目标函数取极（ 大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目 标函数取得极值。 证明的基本思想：将此贪心解与（假设中的）任一最优解相比较 。 如果这两个解相同，

15、则显然贪心解就是最优解。否则， 这两个解不同，就去找开始不同的第一个分量位置i，然后设法 用贪心解的这个xi去替换最优解的那个xi ，并证明最优解在分量代换 前后总的效益值没有任何变化。 可反复进行代换，直到新产生的最优解与贪心解完全一样。这一 代换过程中，最优解的效益值没有任何损失，从而证明贪心解的效益 值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取 得目标函数的最大/最小值。 从而得证：该贪心解也即问题的最优解。 Date 定理4.1 如果p1/w1 p2/w2 pn/wn,则算法GREEDY- KNAPSACK对于给定的背包问题实例生成一个最优解。 证明： 设X=(x1,

16、x2, , xn)是GRDDDY-KNAPSACK所生成的贪心解。 如果所有的xi都等于1,则显然X就是问题的最优解。否则， 设j是使xi1的最小下标。由算法可知， l xi=1 1ij, l 0xj 1 l xi=0 jin 若X不是问题的最优解，则必定存在一个可行解 Y=(y1, y2, , yn),使得： 且应有： Date 设k是使得yk xk的最小下标，则有yk xk: a) 若k0,当且仅当作业i在其截至期限以前被 完成时，则获得pi0的效益。 问题：求这n个作业的一个子集J，其中的所有作业都可在其截至期限 内完成。J是问题的一个可行解。 可行解J中的 所有作业的效益之和是 ，具有

17、最大效益值的可行 解是该问题的最优解。 如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益 值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可 能的效益值。 目标函数： 约束条件：所有的作业都应在其期限之前完成 Date 例4.2 n=4，(p1，p2，p3，p4)(100,10,15,20)和(d1，d2， d3，d4)(2,1,2,1)。可行解如下表所示： 问题的最优解是。所允许的处理次序是：先处理作业4 再处理作业1。 可行解处理顺序效益值 （1）1100 （2）210 （3）315 （4）420 （1,2）2,1110 （1,3）1,3或3,1115 （1,4）4,

18、1120 （2,3）2,325 （3,4）4,335 Date 1. 带有限期的作业排序算法 1) 度量标准的选择 以目标函数 作为量度。 量度标准：下一个要计入的作业将是使得在满足所 产生的J是一个可行解的限制条件下让 得到最大增加的作业。 处理规则：按pi的非增次序来考虑这些作业。 Date 例：例4.2求解 (p1，p2，p3，p4)(100,10,15,20) (d1，d2，d3，d4)(2,1,2,1) 首先令J=, 作业业1具有当前的最大效益值值，且1是可行解 ，所以作业业1计计入J； 在剩下的作业业中，作业业4具有最大效益值值，且 1,4也是可行解，故作业业4计计入J，即J=1,

19、4； 考虑虑1,3,4和1,2,4均不能构成新的可行解， 作业业3和2将被舍弃。 故最后的J=1,4，最终终效益值值120（问题问题 的最 优优解） Date 2)作业排序算法的概略描述 算法4.3 procedure GREEDY-JOB(D,J,n) /作业按p1p2pn的次序输入，它们的期限值D(i)1, 1in,n1。J是在它们的截止期限完成的作业的集合/ J1 for i2 to n do if Ji的所有作业能在它们的截止期限前完成 then JJi endif repeat end GREEDY-JOB Date 2. 最优解证明 定理4.2 算法4.3对于作业排序问题总是得到问

20、题的一个 最优解 证明： 设J是由算法所得的贪心解作业集合，I是一个最优解的作 业集合。 若I=J，则J就是最优解；否则 ，即至少存在两个作业a和b，使得aJ且 ,bI且 。 并设a是这样的一个具有最高效益值的作业，且由算法的 处理规则可得：对于在I中而不在J中的作业所有b，有： papb Date 设SJ和SI分别是J和I的可行的调度表。因为J和I都是可行解， 故这样的调度表一定存在； 设i是既属于J又属于I的一个作业，并i设在调度表SJ中的调度 时刻是t，t+1，而在SI中的调度时刻是t，t+1。 在SJ和SI中作如下调整： 若tt，则将SJ中在t，t+1时刻调度的那个作业（如果 有的话）

21、与i相交换。如果J中在t，t+1时刻没有作业调度，则 直接将i移到t，t+1调度。新的调度表也是可行的。反之， 若tt，则在SI中作类似的调换，即将SI中在t，t+1时 刻调度的那个作业（如果有的话）与i相交换。如果I中在t，t+1 时刻没有作业调度，则直接将i移到t，t+1调度。同样，新的 调度表也是可行的。 对J和I中共有的所有作业作上述的调整。设调整后得到的调 度表为SJ和SI，则在SJ和SI中J和I中共有的所有作业将在相同的 时间被调度。 Date 设a在SJ中的调度时刻是ta, ta+1， b是SI中该时刻调 度的作业。根据以上的讨论有：papb。 在SI中，去掉作业b，而去调度作业

22、a，得到的是作业集 合I=I-b a的 一个可行的调度表，且I的效益值不小于I 的效益值。而I中比I少了一个与J不同的作业。 重复上述的转换，可使I在不减效益值的情况下转换成J 。从而J至少有和I一样的效益值。所以J也是最优解。 证毕。 Date 3. 如何判断J的可行性 方法一：检验J中作业所有可能的排列，对于任一种次序排列的作 业排列，判断这些作业是否能够在其期限前完成若J 中有k个作业，则将要检查k!个序列 方法二：检查J中作业的一个特定序列就可判断J的可行性： 对于所给出的一个排列i1i2ik,由于作业ij完成的 最早时间是j，因此只要判断出排列中的每个作业 dijj，就可得知是一个允

23、许的调度序列，从而J是一个 可行解。反之，如果排列中有一个dijj,则将是一个 行不通的调度序列，因为至少作业ij不能在其期限之前完 成。 这一检查过程可以只通过检验J中作业的一种特殊的排列：按照 作业期限的非降次序排列的作业序列即可完成。 Date 定理4.3 设J是k个作业的集合，i1i2ik是J中作业的一种排列，它 使得di1di2dik。J是一个可行解，当且仅当J中的作业可以按照的次 序而又不违反任何一个期限的情况来处理。 证明： 如果J中的作业可以按照的次序而又不违反任何一个期限的情况来 处理，则J是一个可行解 若J是一个可行解，则必存在序列r1r2rk，使得drjj, 1jk。 若

24、，则即是可行解。否则， ，令a是使得raia的最小下标，并设rb=ia。则有： ba 且 dradrb (为什么?) 在中调换ra与rb，所得的新序列 s1s2sk的处理次序不违反任何 一个期限。 重复上述过程，则可将转换成且不违反任何一个期限。故是一个 可行的调度序列 故定理得证。 Date i1 i2 ia ic ik r1 r2 ra rb rk ab dradrb Date 5. 带有限期的作业排序算法的实现 对当前正在考虑的作业j，按限期大小采用一种“插入排序”的 方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调 度序列中，以此判断是否能够合并到当前部分解J中。如果可以，

25、则插入到序列中，形成新的可行解序列。否则，舍弃该作业。 具体如下： 假设n个作业已经按照效益值从大到小的次序，即 p1p2pn的顺序排列好，每个作业可以在单位时间内完成，并 具有相应的时间期限；且至少有一个单位时间可以执行作业 首先，将作业1存入部分解J中，此时J是可行的； 然后，依次考虑作业2到n。假设已经处理了i-1个作业，其中 有k个作业计入了部分解J中：J(1),J(2),J(k)，且有 D(J(1)D(J(2)D(J(k) Date 对当前正在考虑的作业i,将D(i)依次和D(J(k), D(J(k- 1),，D(J(1)相比较，直到找到位置q：使得 D(i) D(J(l)，qlk，

26、且 D(J(q) D(i) 此时，若D(J(l)l, qlk,即说明q位置之后的所有作业 均可推迟一个单位时间执行，而又不违反各自的执行期限。 最后，将q位置之后的所有作业后移一位，将作业i插入到位 置q1处，从而得到一个包含k+1个作业的新的可行解。 若找不到这样的q，作业i将被舍弃。 对i之后的其它作业重复上述过程直到n个作业处理完毕。最 后J中所包含的作业集合是此时算法的贪心解，也是问题的最优解 。 Date 算法4.4 带有限期和效益的单位时间的作业排序贪心算法 procedure JS(D,J,n,k) /D(1),D(n)是期限值。n1。作业已按p1p2pn的顺序排序。J(i)是最

27、优解中的第i个作 业，1ik。终止时， D(J(i)D(J(i1)， 1ik/ integer D(0:n),J(0:n),i,k,n,r D(0)J(0)0 /初始化/ k1;J(1)1 /计入作业1/ for i2 to n do /按p的非增次序考虑作业。找i的位置并检查插入的可行性/ rk while D(J(r)D(i) and D(J(r) r do rr-1 repeat If D(J(r)D(i) and D(i)r then /把i插入到J中/ for ik to r+1 by -1 do J(i+1) J(i) /将插入点的作业后移一位/ repeat J(r+1) i;k

28、k+1 endif repeat end JS Date 计算时间分析 for i2 to n do 将循环n-1次 rk while D(J(r)D(i) and D(J(r) r do 至多循环k次， k是当前计入J中的作业数 rr-1 repeat If D(J(r)D(i) and D(i)r then for ik to r+1 by -1 do 循环k-r次，r是插入点的位置 J(i+1) J(i) repeat J(r+1) I;kk+1 endif repeat 设s是最终计入J中的作业数，则算法JS所需要的总时间是O(sn)。sn，故 最坏情况：TJS = (n2)，特例情况

29、：pi=di=n-i+1,1in 最好情况：TJS = (n)，特例情况：di=i,1in Date 6. 一种“更快”的作业排序问题 使用不相交集合的 UNION和FIND算法（见 1.4.3节），可以将JS的计算时间降低到数量级 接近(n)。 （略） Date 例4.3 设n=5,(p1,p5)=(20,15,10,5,1),(d1,d5)=(2,2,1,3,3)。 J已分配时间 片 正被考 虑作业 动作 0无1分配1,2 11,22分配0,1 1,20,1,1,23不适合，舍 弃 1,20,1,1,24分配2,3 1,2,4 0,1,1,2,2,3 5舍弃 最优解是J1,2,4 Date

30、 4.4 最优归并模式 1. 问题的描述 1）两个文件的归并问题 两个已知文件的一次归并所需的计算时间O(两个文件的元素总数) 例： n个记录的文件 (n+m) 个记录的文件 m个记录的文件 (n+m) 2）多个文件的归并 已知n个文件，将之归并成一个单一的文件 例：假定文件X1，X2， X3， X4，采用两两归并的方式，可能的归并模 式有： X1+X2=Y1+X3= Y2+X4= Y3 X1+X2 = Y1 + Y3 X3+X4=Y2 Date 二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并 的模式，最终得到一个完整的记录文件。 二元归并树：二路归并模式的归并过程可以用一

31、个二元树的形式描述，称之 为二元归并树。 如 归并树的构造 外结点：n个原始文件 内结点：一次归并后得到的文件 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示 的文件归并成其本身所代表的文件 60 50 30 20 10 X1 Z1 X X3 X2 Date 不同的归并顺序带来的计算时间是不同的。 例4.5 已知X1,X2,X3是分别为30、20、10个记录长度的已分类文件 。将这3个文件归并成长度为60的文件。可能的归并过程和相应的记录移 动次数如下： 问题：采用怎样的归并顺序才能使归并过程中元素的移 动次数最小（或执行的速度最快） X X3 X2 X1 移动50次 移动

32、60次 X X1 X2 X3 移动30次 移动60次 总移动次数：110次 总移动次数：90次 Date 2. 贪心求解 1) 度量标准的选择 任意两个文件的归并所需的元素移动次数与这两个文件的长度 之和成正比； 度量标准：每次选择需要移动次数最少的两个集合进行归并； 处理规则：每次选择长度最小的两个文件进行归并。 95 35 5 20 30 60 3015 10 F4F3 Z1 Z2 Z4 Z3 F1 F5F2 (F1,F2,F3,F4,F5) = (20,30,10,5,30) Date 2) 目标函数 目标：元素移动的次数最少 实例：为得到归并树根结点表示的归并文件，外部结点中每个 文件

33、记录需要移动的次数该外部结点到根的距离，即根到该外部 结点路径的长度。如， F4 ： 则F4中所有记录在整个归并过程中移动的总量|F4|*3 带权外部路径长度：记di是由根到代表文件Fi的外部结点的距 离，qi是Fi的长度，则这棵树的代表的归并过程的元素移动总量是 ： 最优的二路归并模式：与一棵具有最小外部带权路径长度的二 元树相对应。 F4Z1Z2Z4 Date 算法4.6 生成二元归并树的算法 procedure TREE(L,n) /L是n个单结点的二元树表/ for i1 to n-1 do call GETNODE(T) /构造一颗颗新树树T/ LCHILD(T) LEAST(L)

34、/从表L中选选当前根WEIGHT最小的树树， 并从中删删除/ RCHILD(T) LEAST(L) WEIGHT(T) WEIGHT(LCHILD(T)+WEIGHT(RCHILD(T) call INSERT(L,T) /将归归并的树树T加入到表L中/ repeat return (LEAST(L) /此时时，L中的树树即为归为归 并的结结果/ end TREE Date 例4.6 已知六个初始文件，长度分别为：2,3,5,7,9,13。 采用算法TREE，各阶段的工作状态如图所示： L迭代 2357913 0 23 57913 1 5 23 57913 2 5 10 Date 23 579

35、13 3 5 1016 23 579 13 4 5 1016 23 23 5 79 13 5 5 10 16 23 39 Date 时间分析 1) 循环体：n-1次 2) L以有序序列表示 LEAST(L): (1) INSERT(L,T): (n) 总时间总时间 ： (n2) 3) L以min-堆表示 LEAST(L): (logn) INSERT(L,T): (logn) 总时间总时间 ： (nlogn) Date 3. 最优解的证明 定理3.4 若L最初包含n1个单结点的树，这些树有WEIGHT值为 (q1,q2,qn)，则算法TREE对于具有这些长度的n个文件生成一棵最优 的二元归并树

36、。 证明：归纳法证明 当n=1时，返回一棵没有内部结点的树。定理得证。 假定算法对所有的(q1,q2,qn)，1mn,生成一棵最优二元归 并树。 对于n,假定q1q2qn,则q1和q2将是在for循环的第一次迭代中 首先选出的具有最小WEIGHT值的两棵树（的WEIGHT值）；如图所示 ，T是由这样的两棵树构成的子树： q1q2 q1+q2 T Date 设T是一棵对于(q1,q2,qn)的最优二元归并树。 设P是T中距离根最远的一个内部结点。 若P的两棵子树不是q1和q2，则用q1和q2代换P当前的子树而 不会增加T的带权外部路径长度。 故，T应是最优归并树中的子树。 则在T中用一个权值为q

37、1q2的外部结点代换T，得到的是一 棵关于(q1q2,qn)最优归并树T”。 而由归纳假设，在用权值为q1q2的外部结点代换了T之后， 过程TREE将针对(q1q2,qn)得到一棵最优归并树。将T带入该 树，根据以上讨论，将得到关于(q1,q2,qn)的最优归并树。 故，TREE生成一棵关于(q1,q2,qn)的最优归并树。 Date 5. k路归并模式 每次同时归并k个文件。 k元归并树：可能需要增加“虚”结点，以补充不足的外 部结点。 如果一棵树的所有内部结点的度都为k，则外部结点 数n满足 n mod (k-1) = 1 对于满足 n mod (k1) =1的整数n，存在一棵具有n 个外

38、部结点的k元树T，且T中所有结点的度为k。 至多需要增加k-2个外部结点。 k路最优归并模式得贪心规则：每一步选取k棵具有最 小长度的子树归并。 Date 4.5 最小生成树 1. 问题的描述 生成树：设G=(V,E)是一个无向连通图。如果G的生 成子图T=(V,E)是一棵树，则称T是G的一棵 生成树(spanning tree) 最小生成树: 2. 贪心策略 度量标准：选择能使迄今为止所计入的边的成本和有最小 增加的那条边。 Prim算法 Kruskal算法 Date 3. Prim算法 策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到A中 的下一条边(u,v)，应是E中一条当前不在

39、A中且使得A(u,v)也是一 棵树的最小成本边。 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 12 1 6 2 1 6 2 3 1 6 2 3 4 边 (1,2) (2,6) (3,6) (6,4) 成本 10 25 15 20 Date 1 4 6 2 5 3 10 20 25 15 35 边 (3,5) 成本 35 V(TP) = 1,2,3,4,5,6 E(TP) = (1,2),(2,6),(3,5),(4,6),(3,6) Date 算法4.7 Prim最小生成树算法 procedure PRIM(E,COST,n,T,mincost) /E是

40、G的边集。COST(n,n)是n结点图G的成本邻接矩阵，矩阵元素 COST(i,j)是一个正实数，如果不存在边(i,j)，则为。计算一棵最小生成树并 把它作为一个集合存放到数组T(1:n-1,2)中(T(i,1),T(i,2)是最小成本生成树的一 条边。最小成本生成树的总成本最后赋给mincost/ real COST(n,n), mincost integer NEAR(n), n, i, k, l, T(1:n-1,2) (k,l)具有最小成本的边边 mincostCOST(k,l) (T(l,1),T(l,2) (k,l) for i1 to n do /将NEAR置初值值/ if CO

41、ST(i,l) COST(i,k) then NEAR(i)l else NEAR(i) k endif repeat Date NEAR(k)NEAR(l)0 for i2 to n-1 do /找T的其余n-2条边边/ 设设j是NEAR(j)0 且COST(j,NEAR(j)最小的下标标 (T(i,1),T(i,2)(j,NEAR(j) mincostmincost+COST(j,NEAR(j) NEAR(j)0 for k1 to n do /修改NEAR/ if NEAR(k)0 and COST(k,NEAR(k)COST(k,j) then NEAR(k)j endif repea

42、t repeat if mincost then print(no spanning tree) endif end PRIM Date 计计算复杂杂性： 第3行花费(e)(e=|E|)时间，第4行花费(1)时间；第6 9行的循环花费(n)时间；第12行和第1620行的循环要求 (n)时间，因此第1121行循环要花费(n)时间。 所以PRIM算法具有 的时间复杂度 Date 另一种PRIM算法 n最小生成树中包含了与每个结点v相关的 一条最小成本边 证明略 n 方法：从一棵包含任何一个随意指定的 结点而没有边的树开始这一算法，然后再 逐条增加边。 Date 4. Kruskal算法 （连通）图

43、的边按成本的非降次序排列，下一条计入生成树T中的边 是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边 。 1 4 6 2 5 3 10 30 20 45 25 55 40 50 15 35 12 1 6 2 1 6 23 1 6 2 3 4 边 (1,2) (3,6) (4,6) (2,6) 成本 10 15 20 25 1 6 2 345 6345 345 4 5 5 Date 1 4 6 2 5 3 10 20 25 15 35 边 (1,4) (3,5) 成本 30 舍弃 35 V(TK) = 1,2,3,4,5,6 E(TK) = (1,2),(2,6),(3,5),(

44、4,6),(3,6) Date 算法4.9 Kruskal算法 procedure KRUSKAL(E,COST,N,T,mincost) /G有n个结点，E是G的边集。COST(u,v)是边(u,v)的成本。T是最小成本生成 树的边集，mincost是它的成本/ real mincost, COST(1:n,1:n); integer PARENT(1:n), T(1:n-1,2),n 以边成本为元素构造一个min堆 PARENT1/每个结结点都在不同的集合中/ imincost0 while in-1 and 堆非空 do 从堆中删删去最小成本边边(u,v)并重新构造堆 jFIND(u);

45、 kFIND(v) if(jk) then ii+1 T(i,1) u; T(i,2) v mincostmincost + COST(u,v) call UNION(j,k) endif repeat if in-1 then print(no spanning tree) endif return end KRUSKAL Date 注： 边集以min-堆的形式保存，一条当前最小成本边可以在 (loge)的时间时间 内找到； 当且仅仅当图图G是不连连通的，in-1；此时时算法具有最坏 的执执行时间时间 ； 算法的计计算时间时间 是(eloge) Date 4.6 单源点最短路径 1. 问题描

46、述 n 最短路径问题： 每对结点之间的路径问题 特定线路下的最短路径问题 单源最短路径问题等 n 单源最短路径问题 已知一个n结点有向图G=(V,E)和边的权函数c(e)， 求由G中某指定结点v0到其它各结点的最短路径。 假定边的权值为正。 Date n例4.10 如图所示。设v0是起始点，求v0到其它 各结点的最短路径。 路径 长度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v1 45 (4) v0v4 45 注：路径按照长度的非降次序给出 v0 v1 v4 v5v3v2 45 4510 15 20 10 153 35 2030 Date 2. 贪心策略求解 1) 度量标准 量度的选择：迄今已生成的所有路径长度之和为使之 达到最小，其中任意一条路径都应具有最小长度： 假定已经构造了i条最短路径，则下一条要构造的路径应是下 一条最短的路径。 处理规则：按照路径长度的非降次序依次生成从结点v0到 其它各结点的最短路径。 例： v0v2 v0v2v3 v0v2v3v1 v0v4 Date 2) 贪心算法 设S是已经对其生成了最短路径的结点集合（包括v0) 。