5第五章贪心方法

1、1第五章第五章贪心方法贪心方法25.1 一般方法一般方法5.2 背包问题背包问题5.3 带有限期的作业排序带有限期的作业排序5.4 最优归并模式最优归并模式5.5 最小生成树最小生成树(略略)5.6 单源点最短路径单源点最短路径(略略)目录目录35.1 一般方法一般方法p方法适用的问题特点方法适用的问题特点p方法的基础知识方法的基础知识p方法的求解步骤及核心问题方法的求解步骤及核心问题p方法的抽象化控制方法的抽象化控制p方法的缺点和优点方法的缺点和优点4p如果有一个机会可以帮助你梦想成真，那么你希如果有一个机会可以帮助你梦想成真，那么你希望哪两个梦想成真：望哪两个梦想成真：n1 去巴西看足球世

2、界杯；去巴西看足球世界杯；n2 心仪已久的大学学习；心仪已久的大学学习；n3 环球旅行；环球旅行；n4 参观参观2014青岛世博会现场。青岛世博会现场。一个现实世界里的例子一个现实世界里的例子1、2 1、3 1、42、3 2、43、45梦梦想想成成真真的的例例子子贪心方法适用的问题特点贪心方法适用的问题特点p有这样一类问题：它有有这样一类问题：它有n个输入，而它的解就是个输入，而它的解就是这这n个输入的某个子集，个输入的某个子集，这些子集必须满足某些这些子集必须满足某些事先给定的条件。事先给定的条件。约束条件约束条件可行解可行解最优解最优解目标目标函数函数1、2 1、3 1、42、3 2、43

3、、4两个活动两个活动个人喜好个人喜好？6基本概念：基本概念：约束条件、可行解、目标函数、最优解约束条件、可行解、目标函数、最优解A(1)A(2)A(n 1)A(n)B1(1)B1(2)B1(m1)Bk(1) Bk(2)Bk(mk)最优解最优解 问题有问题有n个输入，它的解就是这个输入，它的解就是这n个输入的某个子集，这个子个输入的某个子集，这个子集必须满足某些事先给定的条件即集必须满足某些事先给定的条件即约束条件约束条件，满足约束条件的，满足约束条件的子集称为该问题的子集称为该问题的可行解可行解。一般来说可行解不是唯一的，为衡。一般来说可行解不是唯一的，为衡量可行解的优劣，以函数的形式给出一定

4、的标准，这些函数称量可行解的优劣，以函数的形式给出一定的标准，这些函数称为为目标函数目标函数，使目标函数取极值，使目标函数取极值(极大或极小极大或极小)的可行解就称为的可行解就称为最最优解优解。B1是该问题的是该问题的一个可行解一个可行解B1满足一定满足一定的约束条件的约束条件B2(1)B2(2)B2(m2)一类问题有一类问题有n个输入个输入:Bi是是A的一个子集的一个子集该问题有该问题有k个可行解个可行解该可行解可使该可行解可使 目目标函数取极值标函数取极值7基础知识基础知识p贪心方法是指在对问题求解时，总是做出贪心方法是指在对问题求解时，总是做出在当前看来是最好的选择。在当前看来是最好的选

5、择。p贪心方法的思想可以追溯到贪心方法的思想可以追溯到1823年年J.C.Warnsdorff 解决马踏棋盘问题时给解决马踏棋盘问题时给出的一个著名的算法。出的一个著名的算法。p贪心方法应用的典型问题有背包问题、带贪心方法应用的典型问题有背包问题、带有期限的作业排序、最小生成树、单源点有期限的作业排序、最小生成树、单源点最短路径等问题。最短路径等问题。8贪心方法的求解步骤贪心方法的求解步骤 p贪心方法是根据具体的问题：贪心方法是根据具体的问题：n选取一种量度标准；选取一种量度标准；n按此标准对按此标准对n个输入进行排序；个输入进行排序； n按该顺序一次输入一个量；按该顺序一次输入一个量；n如果

6、这个输入量和当前如果这个输入量和当前该量度意义下该量度意义下的部分最的部分最优解加在一起不能产生一个可行解优解加在一起不能产生一个可行解，则不把此则不把此输入加入到这个部分解中。输入加入到这个部分解中。p这种能够得到某种量度意义下的最优解的这种能够得到某种量度意义下的最优解的分级处理方法就是分级处理方法就是贪心方法贪心方法。9贪心方法设计求解的核心问题贪心方法设计求解的核心问题p贪心方法设计求解的核心问题是选择能产生问题贪心方法设计求解的核心问题是选择能产生问题最优解的最优量度标准。最优解的最优量度标准。p值得一提的是，把目标函数作为度量标准所得到值得一提的是，把目标函数作为度量标准所得到的解

7、也不一定是问题的最优解。的解也不一定是问题的最优解。A(1)A(2)A(n)次优解次优解次优解次优解最优解最优解A1(n)A1(1)量度标准量度标准1A2(n)A2(1)量度标准量度标准2Ak(n)Ak(1)量度标准量度标准k10按某种最优量度标准从按某种最优量度标准从A中中选择一个输入，把它赋值给选择一个输入，把它赋值给x，并从并从A中消去它。中消去它。Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution, x) then solutionUNION(solution, x) endif r

8、epeat return (solution)End GREEDY算法算法5.1 贪心方法的抽象化控制贪心方法的抽象化控制判断判断x是否可以包是否可以包含在解向量中含在解向量中将将x与解向量结合与解向量结合并修改目标函数并修改目标函数11方法的缺点和优点方法的缺点和优点p缺点：缺点：n不是对所有问题都能得到整体最优解。不是对所有问题都能得到整体最优解。n需要证明后才能真正运用到题目的算法中。需要证明后才能真正运用到题目的算法中。p优点：优点：n一旦经过证明成立后，它就是一种高效的算法。一旦经过证明成立后，它就是一种高效的算法。n策略的构造简单易行。策略的构造简单易行。n对范围相当广泛的许多问题

9、他能产生整体最优对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。解或者是整体最优解的近似解。125.2 背包问题背包问题p问题描述问题描述p背包问题实例背包问题实例p背包问题的贪心算法背包问题的贪心算法p定理定理5.113 极极 大大 化化 pixi 0 xi 1, pi 0 约束条件约束条件 wixi M wi 0, 1 i nn 已知有已知有n种物品和一个可容纳种物品和一个可容纳M重量的背包，每种重量的背包，每种物品物品i(1 i n)的重量为的重量为wi，假定将物品，假定将物品i的某一部分的某一部分xi放入背包就会得到放入背包就会得到pixi的效益的效益(0 xi 1

10、,1,pi 0) ) ，采用怎，采用怎样的装包方法会使装入背包物品的总效益为最大？样的装包方法会使装入背包物品的总效益为最大？n 问题的形式化描述：问题的形式化描述：问题描述问题描述14(x1, x2, x3) wi xi pixi(1, 2/15, 0) 2028.2(1, 0, 1/5)2028(0, 2/3, 1)2031(0, 1, 1/2)2031.5其中的其中的4个可行解是：个可行解是：有有3个物品个物品n 3，背包能容纳的最大重量，背包能容纳的最大重量M 20，物品的价值和，物品的价值和重量：重量： (p1, p2, p3) (25,24,15)，(w1,w2,w3) (18,1

11、5,10)背包问题实例背包问题实例考虑下列情况下的背包问题：考虑下列情况下的背包问题：效益值的非增次序效益值的非增次序物品重量的非降次序物品重量的非降次序pi wi比值的非增次序比值的非增次序15p即以目标函数为量度标准即以目标函数为量度标准n该标准使得背包每装入一件物品就获得最该标准使得背包每装入一件物品就获得最大可能的效益值增量。大可能的效益值增量。n结果是一个次优解，原因是背包容量消耗结果是一个次优解，原因是背包容量消耗过快过快。(x1,x2,x3) wixi pixi(1,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5(1)按效益值的非增次按效益值的

12、非增次序把物品放到包里。序把物品放到包里。(p1, p2, p3) (25,24,15)；(w1, w2, w3) (18,15,10)。(2)按物品重量的非降按物品重量的非降次序把物品放到包里。次序把物品放到包里。p以容量为量度标准以容量为量度标准n该标准使得背包每装入一件物品就获得最该标准使得背包每装入一件物品就获得最小可能的容量增量。小可能的容量增量。n结果仍是一个次优结果仍是一个次优解，原因是容量在慢慢解，原因是容量在慢慢消耗的过程中，效益值却没有消耗的过程中，效益值却没有迅速的增加。迅速的增加。背包问题的量度标准选择背包问题的量度标准选择16p选效益值和容量之比为量度标准选效益值和容

13、量之比为量度标准n每一次装入的物品使它占用的每一单位每一次装入的物品使它占用的每一单位 容量获得当前最大的单位效益容量获得当前最大的单位效益n结果是一个最优解，因为每一单位容量结果是一个最优解，因为每一单位容量 的增加将获得最大的单位效益值。的增加将获得最大的单位效益值。(3)按按pi wi比值比值的非增的非增次序把物品放到包里。次序把物品放到包里。(p2 w2, p3 w3, p1 w1) (24 15, 15 10, 25 18)(x1,x2,x3) wixi pixi(1,2/15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5(p1, p2, p3)=(25,

14、24,15)；(w1, w2, w3)=(18,15,10)。背包问题的量度标准选择背包问题的量度标准选择17算法算法5.2 背包问题的贪心算法背包问题的贪心算法procedure GREEDY-KNAPSACK(P,W,M,X,n)float P(1:n), W(1:n), X(1:n), M, cu; int i, n;X 0; cu M;for i 1 to n do if (W(i) cu) then exit; endif； X(i) 1; cu cu W(i);repeatif (i n) then X(i) cu W(i);endifend GREEDY-KNAPSACK将解向量

15、将解向量X初始化为初始化为0，cu为背包的剩余重量为背包的剩余重量放入物品放入物品i 的一部分的一部分若物品若物品i的重量大于背包的的重量大于背包的剩余重量，则退出循环剩余重量，则退出循环若物品若物品i的重量小于等于背包的剩余的重量小于等于背包的剩余容量，则物品容量，则物品i可放入背包内可放入背包内先将物品按先将物品按pi wi比值的非增次序排序比值的非增次序排序(降序降序)18p如果物品事先按照效益值的非增次序或物品重量的非降如果物品事先按照效益值的非增次序或物品重量的非降次序。那么利用算法次序。那么利用算法5.2即可分别即可分别得到量度标准为最优得到量度标准为最优（使每次效益增量最大或容量

16、消耗最慢）的解。（使每次效益增量最大或容量消耗最慢）的解。(p1,p2,p3) (25,24,15), (w1,w2,w3) (18,15,10)(p2 w2 , p3 w3 , p1 w1 ) (24 15, 15 10, 25 18)输入参数输入参数 P (24,15,25)；W (15, 10,18)；M 20；n 3。 初始：初始：X (0, 0, 0)；cu 20。for 循环部分循环部分：(1) 15 cu，then x(1) 1，cu cu w(1) 5； (2) 10 cu，then 跳出循环；跳出循环；结尾：结尾：x(2) cu w(2) 0.5。输入参数输入参数 X (1,

17、 0.5, 0)。运行过运行过程如下程如下19把这个贪心解把这个贪心解X与任一最优解与任一最优解Y相比较，相比较，如果这两个解不同，就去找开始不同的第一个如果这两个解不同，就去找开始不同的第一个xi，然后设法用贪心解的这个然后设法用贪心解的这个xi去去代换代换最优解的那个最优解的那个yi ，并，并证明最优解在分量代换前后的总效益值无任何变化。证明最优解在分量代换前后的总效益值无任何变化。反复进行这种代换，直到新产生的最优解与贪心解反复进行这种代换，直到新产生的最优解与贪心解完全完全一样一样，从而证明了贪心解就是最优解。，从而证明了贪心解就是最优解。最优解证明的基本思想最优解证明的基本思想20定

18、理定理5.1p如果如果p1 w1 p2 w2 pn wn，则算法，则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个对于给定的背包问题实例生成一个最优解。最优解。证明证明: 设设X (x1, , xn )是算法所生成的解。是算法所生成的解。1. 如果所有的如果所有的xi 等于等于1，显然这个解就是最优解。，显然这个解就是最优解。2. 否则，设否则，设j是使是使xj 1的最小下标，由算法可知：的最小下标，由算法可知： 对于对于 1 i j，xi 1； 对于对于 j i n，xi 0； 对于对于 i j，0 xj1。21 3. 若若X不是最优解，则必存在一个最优解不是最优解，则必存

19、在一个最优解 Y (y1, , yn)，使得使得 piyi pixi 。 假定假定 wiyiM，设，设k是使得是使得 yk xk的最小下标，的最小下标， 则可以推出则可以推出yk xk成立。成立。4. 现在，假定把现在，假定把 yk 增加到增加到 xk ，那么必须从，那么必须从(yk 1,yn) 中减去同样多的量，使得所用的总容量仍为中减去同样多的量，使得所用的总容量仍为M。这。这导致一个新的解导致一个新的解Z (z1, zn)，其中，其中 zi xi，1 i k，并且并且 wi ( yi zi ) wk ( zk yk) k i n三种可能发生的情况：三种可能发生的情况：(1)k j；(2)

20、k j；(3)k j225. 因此，对于因此，对于Z有有 pizi piyi (zk yk)pk (yi zi)pi piyi (zk yk)wk pk wk (yi zi)wipi wi piyi (zk yk)wk (yi zi)wipk wk piyi 1 i n所以所以 pizi piyi 成立成立6. 若若 pizi piyi，则，则Y不可能是最优解。不可能是最优解。 所以所以 pi zi piyi ， 如果如果Z X，则，则X就是最优解；就是最优解； 否则否则Z X，则重复上面的讨论，每次，则重复上面的讨论，每次Y中少一个和中少一个和 X不同的值，最终把不同的值，最终把Y转换成转换

21、成X，从而证明了，从而证明了X也是最优解，也是最优解， 证毕。证毕。元素按元素按pi wi非非增次序排列。增次序排列。1 i nk 1 i n1 i n1 i n1 i nk 1 i nk 1 i n23定理定理5.1证明总结证明总结p分析贪心解的形式分析贪心解的形式p假设最优解假设最优解p比较贪心解和最优解比较贪心解和最优解p重新构造最优解重新构造最优解p证明重新构造的最优解与贪心解相同证明重新构造的最优解与贪心解相同245.3 带有限期的作业排序带有限期的作业排序n问题描述问题描述n带限期的作业排序算法带限期的作业排序算法n定理定理5.2n定理定理5.3n算法算法5.4n算法算法5.525

22、问题描述问题描述p假定只能在一台机器上处理假定只能在一台机器上处理n个作业，个作业， 每个作业均每个作业均可在单位时间内完成；又假定每个作业可在单位时间内完成；又假定每个作业i都有一个都有一个截止期限截止期限di 0(di是整数是整数)，当且仅当作业，当且仅当作业i在它的期在它的期限截止之前被完成时获得限截止之前被完成时获得pi 0的效益。的效益。p该问题的一个可行解是这该问题的一个可行解是这n个作业的一个子集合个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，中的每个作业都能在各自的截止期限之前完成，可行解的效益值是可行解的效益值是J中这些作业的效益之和中这些作业的效益之和

23、pj 。具有最大效益值的可行解就是最优解具有最大效益值的可行解就是最优解。限制条件限制条件目标函数目标函数26形式化描述形式化描述目标函数：目标函数： 约束条件：作业约束条件：作业 j 的处理时间的处理时间 tj dj，dj 0，pj 0， 1 j n Jjjp27有有4个作业个作业n 4；(p1, p2, p3, p4) (100, 10, 15, 20)；(d1, d2, d3, d4) (2, 1, 2, 1)；可行解可行解J处理顺序处理顺序效益值效益值 pj （1）1100（2）210（3）315（4）420 （1，3） 1, 3 或或 3, 1 115 （1，2） 2，1 110 （

24、1，4） 4，1 120 （2，3） 2，3 25 （3，4） 4，3 35例例5.228带限期的作业排序算法的实现思想带限期的作业排序算法的实现思想p为得到最优解，贪心策略应制定一个量度标准，为得到最优解，贪心策略应制定一个量度标准，使得所选择的下一个作业在这种量度下达到最优。使得所选择的下一个作业在这种量度下达到最优。p选择目标函数选择目标函数 pj作为量度标准作为量度标准，使下一个要计入，使下一个要计入的作业是满足的作业是满足J是一个可行解是一个可行解的限制条件下使的限制条件下使 pj得到最大增加的作业，只需将各作业按效益得到最大增加的作业，只需将各作业按效益pi降序降序排列即可，即：排

25、列即可，即：p1 p2 pn .J中的每个作业中的每个作业都能在各自的截都能在各自的截止期限之前完成。止期限之前完成。29算法算法5.3 带限期的作业排序算法描述带限期的作业排序算法描述procedure GREEDY_JOB(D, J, n)/ 作业按作业按p1 p2 pn的次序输入；它们的期限值的次序输入；它们的期限值D(i) 1，1 i n，n 1。J是在它们的截止期限前完成是在它们的截止期限前完成的作业的集合。的作业的集合。/ J1 for i 2 to n do if (J i的所有作业都能在它们的截止期限前完成的所有作业都能在它们的截止期限前完成 ) then J J i endi

26、frepeatend GREEDY_JOB算法中最关键的一步算法中最关键的一步30两个问题两个问题p算法算法5.3所描述的贪心方法是否能提供一个所描述的贪心方法是否能提供一个最优解？最优解？p对于给定的作业集合对于给定的作业集合J，如何确定它是否是，如何确定它是否是可行解？可行解？31定理定理5.2p对于作业排序问题用算法对于作业排序问题用算法5.3所描述的贪心方法总是所描述的贪心方法总是得到一个最优解。得到一个最优解。p证明思路：证明思路：nJ是贪心方法求出的作业集合，是贪心方法求出的作业集合，I是一个最优解的作业集合。是一个最优解的作业集合。可以证明可以证明J和和I具有相同的效益值，从而具

27、有相同的效益值，从而J也是最优解。也是最优解。n证明证明I J。IJaba是使得是使得a J且且a I的的一个最高效益值的作业一个最高效益值的作业由贪心方法可知，对于在由贪心方法可知，对于在I中中又不在又不在J中的所有作业中的所有作业b，都有，都有pa pb。这是因为，若。这是因为，若pb pa,则则贪心方法会先于贪心方法会先于a考虑考虑b，并把，并把b计入到计入到J中去。中去。32n设设SJ和和SI分别是分别是J和和I的可行调度表。令调度表中相同作的可行调度表。令调度表中相同作业在相同的时间片执行。具体方法如下：业在相同的时间片执行。具体方法如下： SJ: .i.k.SI: i. t t S

28、J: .ki.SI: i. t t SJ: .i.SI: .i.k. t t SJ: .i.SI: .k.i. t t n用用J中作业中作业a替换掉替换掉I中同时间片调用的作业中同时间片调用的作业b，得到作业集，得到作业集合合I I b a的一个可行调度表。显然，的一个可行调度表。显然，I的效益值不的效益值不小于小于I的效益值，并且的效益值，并且I比比I少一个与少一个与J不同的作业。不同的作业。n重复应用上述转换，使重复应用上述转换，使I在不减效益值得情况下转换成在不减效益值得情况下转换成J，因此因此J也必定是最优解，证毕。也必定是最优解，证毕。33确定作业集合确定作业集合J是否是可行解是否是

29、可行解p假定假定J中有中有k个作业，检验个作业，检验J的所有可能的排列的所有可能的排列ni1, i2, , ik是是J中作业的一种排列中作业的一种排列;n完成作业完成作业ij的最早时间是的最早时间是j，1 j n；n若排列中每个作业的若排列中每个作业的dij j，则，则 是一个允许的调是一个允许的调度序列，度序列，J是一个可行解；否则，检验其他排列是一个可行解；否则，检验其他排列形式。形式。检验一种特殊的排列：检验一种特殊的排列：按期限的非降次序。按期限的非降次序。34一个例子一个例子 (p1, p2 , p3, p4) (100, 10, 15, 20)， (d1, d2, d3, d4)

30、(2, 1, 2, 1) ：d2 d4 d1 d3J 1, 4 处理次序：处理次序：4, 1 , J是一个可行解是一个可行解J 2, 3 处理次序：处理次序：2, 3 , J是一个可行解是一个可行解J 2, 4 处理次序：处理次序： 2, 4 , 但是作业但是作业4违反它的期限，违反它的期限，所以所以J不是一个可行解不是一个可行解35定理定理5.3p设设J是是k个作业的集合，个作业的集合，i1,i2,ik是是J中作中作业的一种排列，它使得业的一种排列，它使得di1 di2dik。J是是一个可行解，当且仅当一个可行解，当且仅当J中的作业可以按中的作业可以按照照 的次序而又不违反任何一个期限的情的

31、次序而又不违反任何一个期限的情况来处理。况来处理。36证明思想证明思想p如果如果J中的作业可以按照中的作业可以按照 的次序而又不违反任的次序而又不违反任何一个期限，则何一个期限，则J是一个可行解。是一个可行解。p若若J是可行解，则必存在是可行解，则必存在 r1,r2,rk，使得，使得drj j， 1 j k。n假设假设 ，令，令a是使得是使得ra ia的最小下标。的最小下标。n设设rb ia，显然，显然b a。n在在 中交换中交换ra与与rb的位置，产生新的可行排列的位置，产生新的可行排列 ”。p连续使用这种方法，就将连续使用这种方法，就将 转换成转换成 且不违反且不违反任何一个期限。任何一个

32、期限。 : ra. : ia .rb. ” : rb. : ia .ra.ra延后执行延后执行是否可行？是否可行？drb dia dra37p首先将作业按首先将作业按p1 p2 pn排序，将作业排序，将作业1存入数组存入数组J中，然后处理作业中，然后处理作业2到作业到作业n。p假设已处理了假设已处理了i 1个作业，其中有个作业，其中有k个作业已存入个作业已存入J(1), J(2),J(k)中，且中，且DJ(1) DJ(2) DJ(k)。p现在处理作业现在处理作业i，判断，判断J i是否可行，即，是否能找到是否可行，即，是否能找到一个适当的位置一个适当的位置r，满足如下条件：，满足如下条件：nD

33、l l， r 1 l k；nDJ(r) Di；nDi r；p若找到，则进行如下处理：若找到，则进行如下处理：n位置位置r 1k共共k r个作业依次后移一个位置，即延迟一个单位个作业依次后移一个位置，即延迟一个单位时间再处理；时间再处理；n作业作业i插入到插入到r 1位置，即，在位置，即，在r时间片处理；时间片处理；类似于直接插入类似于直接插入法对期限值进行法对期限值进行非降次序排列。非降次序排列。根据定理根据定理5.3，带有限期的作业排序问题可如下处理：带有限期的作业排序问题可如下处理：38J0 J1 J2 J3 J4 J50312J0 J1 J2 J3 J4 J501012345p20151

34、051d0231442实例：实例：n 5，(p1, p2, p3, p4, p5) (10, 1, 15, 20, 5) (d1, d2, d3, d4, d5) ( 1, 4, 3, 2, 4)J0 J1 J2 J3 J4 J50122134Dl l, r 1 l k；DJ(r) Di；Di r；39procedure JS(D, J, n, k) integer D(0:n), J(0:n), i, k, n, r; D(0) J(0) 0; k1; J(1) 1; for i2 to n do r k; while ( D(J(r) D(i) and D(J(r) r ) do rr 1

35、 repeat if ( D(J(r) D(i) and D(i) r ) then for lk to r 1 by 1 do J(l 1)J(l); repeat J(r 1) i ; kk 1； endif repeatend JS从从D(J(k)到到 D(J(1)依依次与次与D(i)比较来寻找比较来寻找插入位置插入位置r的过程的过程 满足条件表满足条件表示找到插入示找到插入位置位置r实现作业实现作业r 1到到作业作业k依次往后依次往后移动一个位置移动一个位置 将作业将作业i插入到插入到r 1位置位置算法算法5.4 带有限期的作业排序的贪心算法带有限期的作业排序的贪心算法40D(0) J

36、(0) 0; k 1; J(1) 1; for循环循环(i 2时时) r k 1; while (D(J(r) D(i)andD(J(r) r) 条件不满足，不执行循环条件不满足，不执行循环 if ( D(J(r) D(i) and D(i) r ) then for i 1 to r 1 2 by 1 do 不执行循环不执行循环 J(2) i 2 ; k k 1 2; J(0) J(1) J(2) J(3) J(4) J(5)01012345p20151051d0231442实例：实例：n 5, (p1, p2, p3, p4, p5) (10, 1, 15, 20, 5) (d1, d2,

37、 d3, d4, d5) ( 1, 4, 3, 2, 4)41k 2; for循环循环(i 3时时) r k 2; while (DJr Di and DJr r) 执行两次循环后执行两次循环后 r 0 if ( DJr Di and Di r ) then for i 2 to r 1 1 by 1 do 执行执行2次次 J3 J2; J2 J1; J1 i 3 ; k k 1 3; J0 J1 J2 J3 J4 J5012213k 3; for循环循环(i 4时时) r k 3; while (DJr Di and DJr r) 条件不满足，不执行循环条件不满足，不执行循环 if ( DJ

38、r Di and Di r ) then for i 3 to r 1 4 by 1 do 不执行循环不执行循环 J4 i 4 ; k k 1 4; 4012345p20151051d02314442k 4; for循环循环( i 5时时) r k 4; while (DJr DiandDJr r) 条件不满足，不执行循环条件不满足，不执行循环 if ( DJr Di and Di r )条件不满足条件不满足作业作业5不能插入不能插入 J0 J1 J2 J3 J4 J503124012345p20151051d02314443算法算法5.4的时间复杂度的时间复杂度p算法算法JS有两个赖以测量其

39、时间复杂度的参数：有两个赖以测量其时间复杂度的参数：作作业数业数 n 和包含在解和包含在解J中的作业数中的作业数 s p内层的内层的while循环至多循环循环至多循环k次，插入作业次，插入作业 i 要执行要执行时间为时间为 (k r)p外层外层for循环共执行循环共执行(n 1)次次p如果如果s是是k的终值，即的终值，即s是最后所得解的作业数，则是最后所得解的作业数，则JS算法所需要的总时间为算法所需要的总时间为 (sn)p由于由于s n，所以，所以JS算法的时间复杂度为算法的时间复杂度为 (n2)44一种更快的作业排序算法一种更快的作业排序算法p算法思想算法思想n对作业对作业i分配时间时，分

40、给它一个时间片，在这个时间片分配时间时，分给它一个时间片，在这个时间片里作业里作业i能完成。时间片是一个时间范围，在考虑已经分能完成。时间片是一个时间范围，在考虑已经分配的时间片的基础上，时间上界应尽可能的取大配的时间片的基础上，时间上界应尽可能的取大(可能的可能的话尽量将作业向后排话尽量将作业向后排)。p算法的非形式化描述算法的非形式化描述n如果如果J是作业的可行子集，可使用下述规则来确定是作业的可行子集，可使用下述规则来确定J中每个中每个作业的处理时间：若还没给作业作业的处理时间：若还没给作业i分配处理时间，则分给分配处理时间，则分给它时间片它时间片 1, ，其中其中 应尽量取大，且该时间

41、片是空应尽量取大，且该时间片是空的。若正在被考虑的作业的。若正在被考虑的作业i不存在这样的不存在这样的 ，则这个作业就则这个作业就不能计入不能计入J中。中。可以把可以把JS的计算时间由的计算时间由 (n2)降低到数量级接近于于降低到数量级接近于于 (n)。45i12345pi20151051di22133可行解可行解J已分配的时间片已分配的时间片考虑的作业考虑的作业分配动作分配动作无无1分配分配1, 211, 22分配分配0, 11, 20, 1 1, 23舍弃舍弃1, 20, 1 1, 24分配分配2, 31, 2, 40, 1 1, 2 2, 35舍弃舍弃如何得到如何得到 ？快速作业排序实

42、例快速作业排序实例461.存在存在n个作业，每个作业花费一个单位时间，因此只需考虑个作业，每个作业花费一个单位时间，因此只需考虑时间片时间片i 1,i，1 i b，b minn, maxdi 例如：例如：10个作业，作业的截止期中最大值是个作业，作业的截止期中最大值是5，只需考虑时间段，只需考虑时间段0,5 5个作业，作业的截止期中最大值是个作业，作业的截止期中最大值是10，同样只需考虑时间段，同样只需考虑时间段0,52.对于任一期限对于任一期限i，设，设ni是满足是满足ni i且且ni 1,ni为空的最大整数为空的最大整数 3.引进一个虚构的期限值引进一个虚构的期限值0和时间片和时间片 1,

43、0 若期限值若期限值i j，但，但ni nj，设，设i j表明时间表明时间i 1, j是满的，所以期限值为是满的，所以期限值为i 1, i 2, , j的作业都有可能分到的作业都有可能分到ni 1, ni时间片时间片4.对于每个期限值对于每个期限值i，用，用F(i)表示当前最接近的空时间片，即表示当前最接近的空时间片，即 F(i) ni . 开始时，时间片都为空，开始时，时间片都为空，F(i) i.思想：将期限值表示成集合，使得确定思想：将期限值表示成集合，使得确定 的时间减小的时间减小算法算法5.5设计思想设计思想476.期限值按可以分配到的时间片被分成不同集合，期限值按可以分配到的时间片被

44、分成不同集合，初始有初始有b 1个集合。个集合。7.使用集合的树表示法，把每个集合表示成一棵树，使用集合的树表示法，把每个集合表示成一棵树，根结点就认为是这个集合。根结点就认为是这个集合。P(i)把期限值把期限值i链接到它链接到它的集合树。开始时的集合树。开始时P(i) 1，0 i b.8.判断作业判断作业i的可用空时间片，即找的可用空时间片，即找minn,di的根的根j，若若F(j) 0，说明有时间片可以分配，则，说明有时间片可以分配，则 F(j)是最接是最接近的时间片。近的时间片。9.标识标识F(j)被占用：以被占用：以j为根的集合树与包含期限为根的集合树与包含期限F(j) 1的集合树合并

45、，的集合树合并，F(j)更新。更新。算法算法5.5设计思想设计思想48pF(i)：期限：期限i能分配到的时间片，初始化为能分配到的时间片，初始化为ipP(i)： 期限期限i的父结点，初始化为的父结点，初始化为 1p对于当前考虑的作业对于当前考虑的作业i 作业作业i的期限的期限D(i)所在的集合所在的集合 FIND(D(i)j j是否已被分配是否已被分配 F(j)是否为是否为0 若若F(j)不为不为0，则，则给作业给作业i分配时间片分配时间片F(j)并并做标记做标记集合的变化集合的变化：j所在的集合和前面的集合所在的集合和前面的集合l合并合并线性表的变化线性表的变化： 对对F(j)重新赋值为重新

46、赋值为F(l)的值的值算法算法5.5设计思想设计思想49p初始初始np1 p2 pnnb minn,maxdjnF(i) inP(i) 1p依次检验每个作业依次检验每个作业wn寻找寻找D(w)所在树的根节点所在树的根节点jn如果如果F(j) 0， F(j)时间片可以分配给作业时间片可以分配给作业w ，因此，将，因此，将w并入到解集合并入到解集合J中，中，n寻找寻找F(j) 1所在树的根节点所在树的根节点l，将，将l和和j所在的两个树合并所在的两个树合并到一起。到一起。nF(j) F(l)算法算法5.5设计思想设计思想jFIND(min(n, D(w)kk 1;J(k)w;lFIND(F(j)

47、1);call UNION(l,j);50Procedure FJS(D,n,b,k.J)/作业已按作业已按p1 p2 pn被排序，被排序，b minn,maxD(i)./找最优解找最优解J=J(1),J(k) integer b,D(0:n),J(0:n),F(0:b),P(0:b)for i 0 TO b DO F(i)i ; P(i) 1 ;repeatk0for i1 TO n DO jFIND(min(n,D(i) ; if F(j) 0 then kk 1; J(k) i ; lFIND(F(j) 1) UNION(l, j); F(j)F(l) endifrepeatend FJ

48、S 作业作业i的期限值所的期限值所在的集合的根在的集合的根可以给作业可以给作业i分配时间片分配时间片标识标识F(j)被占用被占用算法算法5.5 作业排序的一个更快算法作业排序的一个更快算法51考虑考虑作业作业树树J无无 0 1 2 3 4 5 6 7-10-11-12-13-14-15-16-170 1 2 3 3 5 6 7-10-11-12-2334-15-16-1710 1 1 3 3 5 6 7-10-2112-2334-15-16-171,2F(0)(1) (2) (3) (4) (5) (6) (7)例：设例：设n=7，(p1, ,p7) (35,30,25,20,15,10,5)

49、 (d1,d7) (4,2,4,3,4,8,3) 1252考虑考虑作业作业树树J0 1 1 1 3 5 6 7-10-4112-15-16-1713341,2,3 0 0 1 1 3 5 6 710-5112-15-16-1713341,2,3,4F(0)(1) (2) (3) (4) (5) (6) (7)(p1, ,p7) (35,30,25,20,15,10,5) (d1,d7) (4,2,4,3,4,8,3)3453考虑考虑作业作业树树J10-5112-15-16-1713140 0 1 1 3 5 6 71,2,3,40 0 1 1 3 5 6 610-5112-15-2667133

50、41,2,3,4,60 0 1 1 3 5 6 6 同上同上F(0)(1) (2) (3) (4) (5) (6) (7)最优解最优解J 1,2,3,4,6，处理次序，处理次序4,2,3,1,6，效益值，效益值120(舍弃舍弃)567(舍弃舍弃)(p1, ,p7) (35,30,25,20,15,10,5) (d1,d7) (4,2,4,3,4,8,3)545.4 最优归并模式最优归并模式将两个分别包含将两个分别包含n个和个和m个记录的个记录的已排序已排序文件文件归并归并成成一个包含一个包含(n m)个记录的排序文件个记录的排序文件, 时间为时间为 (n m)1460357901345679文

51、件文件1：n 3文件文件2：m 5若待归并的文件数大于若待归并的文件数大于2，如何处理呢？，如何处理呢？55例例: 将将4个文件个文件X1,X2,X3,X4进行归并进行归并, 有不同的归并方式：有不同的归并方式：X1X2X3X4Y1Y2Y3X1X2X3X4Y1Y2Y35.4 最优归并模式最优归并模式n个文件归并个文件归并, 有多种归并方式，需要的时间也不同。有多种归并方式，需要的时间也不同。56归并的计算时间归并的计算时间,即记录比较和移动的时间。即记录比较和移动的时间。问题问题: 如何确定一个把如何确定一个把n个个已排序已排序文件归并在一起的最文件归并在一起的最优方法，即需要时间最少的方法。

52、优方法，即需要时间最少的方法。n 3，长度分别为，长度分别为30,20,10Y1Y35060记录移动的总次数记录移动的总次数: 50 60 110X1X2X330 20 10Y1Y2X130X2X3 20 103060记录移动的总次数记录移动的总次数: 30 60 90最优最优5.4 最优归并模式最优归并模式57量度标准：量度标准：每一步都归并尺寸比较小的两个文件每一步都归并尺寸比较小的两个文件例例: 有五个文件长度分别是有五个文件长度分别是(F1,F5) (20, 30,10, 5, 30)5F410F315Z120F130F230F560Z335Z295Z4这种模式称这种模式称二路归并模式

53、二路归并模式 用用二元归并树二元归并树来表示来表示叶结点称叶结点称外部结点外部结点表示已知的文件表示已知的文件内部结点内部结点, 每个内部结点每个内部结点有两个儿子有两个儿子, 表示它是由表示它是由两个文件归并而得到的两个文件归并而得到的5.4 最优归并模式最优归并模式585F410F315Z120F130F230F560Z335Z295Z4带权外部路径长度带权外部路径长度 如果如果di表示从根到代表文件表示从根到代表文件Fi的外部结点的距离，的外部结点的距离， qi表示文件表示文件Fi的长度的长度(即记录数即记录数)，则这棵二元归并树，则这棵二元归并树 的记录移动总量是：的记录移动总量是：

54、diqi ( i 1,2,n) 一个最优二路归并模式一个最优二路归并模式 与一棵具有最小外部路径与一棵具有最小外部路径 的二元树相对应的二元树相对应计算实例中的记录移动总量计算实例中的记录移动总量 diqi 5 3 10 3 20 2 30 2 30 2 2055.4 最优归并模式最优归并模式59生成二元归并树算法生成二元归并树算法 算法把算法把n个树的表个树的表L作为输入作为输入, 树中的每一个结点有树中的每一个结点有三个信息段三个信息段( LCHILD,RCHILD,WEIGHT ) 起初起初L中的每一棵树正好是一个结点中的每一棵树正好是一个结点, 即外部结点即外部结点, 结点的结点的LC

55、HILD和和RCHILD信息段都为信息段都为0, 而而WEIGHT信息段的值就是已知文件的长度。信息段的值就是已知文件的长度。 算法运行时算法运行时, 对于对于L中的任何一棵具有根结点中的任何一棵具有根结点T的树的树, WEIGHT(T)表示要归并的文件的长度。表示要归并的文件的长度。 WEIGHT(T) 树树T中外部结点的长度和中外部结点的长度和5.4 最优归并模式最优归并模式60procedure TREE(L, n)for I 1 to n 1 do call GETNODE(T); LCHILD(T)LEAST(L); RCHILD(T)LEAST(L); WEIGHT(T)WEIGH

56、T(LCHILD(T) WEIGHT(RCHILD(T) call INSERT(L,T);repeatreturn (LEAST(L);end TREE构造一个新结点构造一个新结点 作作为当前树的根结点为当前树的根结点找出找出L中一棵中一棵WEIGHT最小的树，把它作为新最小的树，把它作为新结点的左子树，然后在结点的左子树，然后在L中将这棵树删除中将这棵树删除把根为把根为T的树插的树插入到表入到表L中中新结点的新结点的WEIGHT信息信息段的值等于左、右子树段的值等于左、右子树的的WEIGHT之和之和最后留在表最后留在表L中的树就是归并中的树就是归并树，将它作为结果返回树，将它作为结果返回5

57、.4 最优归并模式最优归并模式61例例: 有有6个文件个文件, 长度分别为长度分别为: 2 , 3 , 5 , 7 , 9 , 13, 算法算法TREE如何工作？如何工作？23初始初始, 表表L中有中有6棵树棵树,每棵树只有一个结点每棵树只有一个结点,分别代表分别代表6个文件个文件i 1, 先产生一个新结点先产生一个新结点(内结点内结点), 从从L的的6棵树中找出棵树中找出WEIGHT值值最小的树最小的树,作为新结点的左子树作为新结点的左子树, 再从剩余再从剩余5棵树中找出棵树中找出WEIGHT最小的树最小的树,作为新结点的右子树作为新结点的右子树, 新结点的新结点的WEIGHT的值等于左、的

58、值等于左、右子树右子树WEIGHT值之和值之和, 表表L中还有中还有5棵树棵树2351379表表L:i 1，表，表L：5137955.4 最优归并模式最优归并模式62i 2，先产生一个新结点，从，先产生一个新结点，从L的棵树中找出的棵树中找出WEIGHT值为值为5的的树，作为新结点的左子树，再在剩余树，作为新结点的左子树，再在剩余4棵树找出棵树找出WEIGHT值为值为5的树，作为新结点的右子树，新结点的的树，作为新结点的右子树，新结点的WEIGHT的值等于左、的值等于左、右子树右子树WEIGHT值之和，表值之和，表L中还有中还有4棵树棵树235i 2，表，表L：51379i 3，先产生一个新结

59、点，从，先产生一个新结点，从L的棵树中找出的棵树中找出WEIGHT值为值为7的的树，作为新结点的左子树，再在剩余树，作为新结点的左子树，再在剩余4棵树找出棵树找出WEIGHT值为值为9的树，作为新结点的右子树，新结点的的树，作为新结点的右子树，新结点的WEIGHT的值等于左、的值等于左、右子树右子树WEIGHT值之和，表值之和，表L中还有中还有3棵树棵树102355101379165.4 最优归并模式最优归并模式i 3，表，表L：632355101379167916232355101323395.4 最优归并模式最优归并模式i 4，表，表L：i 5，表，表L：64二元归并树算法的计算时间二元归

60、并树算法的计算时间 主循环执行主循环执行n 1次次 如果如果L中中WEIGHT的值按升序排列的值按升序排列, 则则LEAST(L)只需要只需要 (1)的时间的时间 INSERT(L,T)在在 (n)时间内被执行时间内被执行 因此因此二元归并树二元归并树算法的计算是总量为算法的计算是总量为: (n2) 若若L表示成一个表示成一个min-堆的情况，堆的情况， INSERT(L,T) 和和LEAST(L) 可在可在log(n)时间内完成，算法的时间为时间内完成，算法的时间为 (nlogn)v定理定理3.4: 若若L最初包含最初包含n 1个单各结点的树，这些个单各结点的树，这些树有树有WEIGHT值为