1、2022-12-24第四章第四章 贪心方法贪心方法2022-12-24本章教学要求及重点难点本章教学要求及重点难点n理解贪心方法的基本思想理解贪心方法的基本思想n掌握背包问题的求解方法掌握背包问题的求解方法n掌握带有限期的作业排序的基本方法掌握带有限期的作业排序的基本方法n掌握用贪心方法求解单源点最短路径的基本方掌握用贪心方法求解单源点最短路径的基本方法。法。n重点：用贪心方法求背包问题及带有限期作业重点：用贪心方法求背包问题及带有限期作业排序；排序；n难点：用贪心方法求单源点最短路径。难点：用贪心方法求单源点最短路径。2022-12-244.1 一般方法一般方法1.问题的一般特征问题的一般特
2、征 问题有问题有n个输入，问题的解是由这个输入，问题的解是由这n个输入的某个个输入的某个子集子集组成，这个子组成，这个子集必须满足某些事先给定的条件。集必须满足某些事先给定的条件。n 约束条件约束条件：子集必须满足的条件；：子集必须满足的条件；n 可行解可行解：满足约束条件的子集；可行解可能不唯一；：满足约束条件的子集；可行解可能不唯一；n 目标函数目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；：用来衡量可行解优劣的标准，一般以函数的形式给出；n 最优解最优解：能够使目标函数取极值（极大或极小）的可行解。：能够使目标函数取极值（极大或极小）的可行解。分类分类：根据描述问题约束条件和
3、目标函数的：根据描述问题约束条件和目标函数的数学模型数学模型的特性和问题的的特性和问题的求解方法求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。划等。最优化问题求解最优化问题求解 贪心方法贪心方法：一种改进的：一种改进的分级分级的处理方法，可对满足上述特征的某些问的处理方法，可对满足上述特征的某些问题方便地求解。题方便地求解。2022-12-24例例找零钱找零钱 一个小孩买了价值少于一个小孩买了价值少于1元的糖，并将元的糖，并将1元的钱元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假交给售货员。售货员希望用数目最
4、少的硬币找给小孩。假设提供数目不限的面值为设提供数目不限的面值为25分、分、10分、分、5分及分及1分的硬币。分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。所需的数目。假设需要找给小孩假设需要找给小孩67分，首先入选的是两枚分，
5、首先入选的是两枚25分的硬币，分的硬币，第三枚入选的不能是第三枚入选的不能是25分的硬币，否则将不可行（零钱总分的硬币，否则将不可行（零钱总数超过数超过67分），第三枚应选择分），第三枚应选择10分的硬币，然后是分的硬币，然后是5分的，分的，最后加入两个最后加入两个1分的硬币。分的硬币。贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）应使找出的硬币数目最少（至少是接近最少的数目）2022-12-242.贪心方法的一般策略贪心方法的一般策略 问题的一般特征：问题的解是由问题的一般特征：问题的解是由n个输
6、入的、满足某些事先给定个输入的、满足某些事先给定的条件的子集组成。的条件的子集组成。1）一般方法）一般方法 根据题意，选取一种根据题意，选取一种度量标准度量标准。然后按照这种度量标准对。然后按照这种度量标准对n个输个输入入排序排序，并按序一次输入一个量。，并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的如果这个输入和当前已构成在这种量度意义下的部分最优解部分最优解加在加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的当前输入合并到部分解中从而得到包含当前输入的新
7、的部分解新的部分解。2）贪心方法）贪心方法 这种能够得到某种量度意义下的最优解的这种能够得到某种量度意义下的最优解的分级处理分级处理方法称为方法称为贪心贪心方法方法注：注：贪心解贪心解 最优解最优解 直接将目标函数作为直接将目标函数作为量度标准量度标准也不一定能够得到问题的最优解也不一定能够得到问题的最优解 3）使用贪心策略求解的关键）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。选取能够得到问题最优解的量度标准。？2022-12-243.贪心方法的抽象化控制描述贪心方法的抽象化控制描述 procedure GREEDY(A,n)/A(1:n)包含包含n个输入个输入/solutio
8、n /将解向量将解向量solution初始化为空初始化为空/for i1 to n do xSELECT(A)/按照度量标准，从按照度量标准，从A中选择一个输入，其值赋予中选择一个输入，其值赋予x 并将之从并将之从A中删除中删除/if FEASIBLE(solution,x)then /判定判定x是否可以包含在解向量中，是否可以包含在解向量中，即是否能共同构成可行解即是否能共同构成可行解/solutionUNION(solution,x)/将将x和当前的解向量合并成新的解和当前的解向量合并成新的解 向量，并修改目标函数向量，并修改目标函数/endif repeat return(solutio
9、n)end GREEDY 2022-12-244.2 背包问题背包问题1.问题的描述问题的描述 已知已知n种物品具有重量种物品具有重量(w1,w2,wn)和效益值和效益值(p1,p2,pn)，及一个，及一个可容纳可容纳M重量的背包；设当物品重量的背包；设当物品i全部或一部分全部或一部分xi放入背包将得到放入背包将得到pi xi的的效益，这里，效益，这里，0 xi 1,p 1,pi 0 0。问题问题：采用怎样的装包方法才能使装入背包的物品的：采用怎样的装包方法才能使装入背包的物品的总效益最大总效益最大？分析分析：装入背包的总重量装入背包的总重量不能超过不能超过M M 如果所有物品的如果所有物品的
10、总重量总重量不超过不超过M M，即，即 MM，则把，则把所有所有的物的物品都装入背包中将获得最大可能的效益值品都装入背包中将获得最大可能的效益值 如果物品的总重量如果物品的总重量超过了超过了M M，则将有物品不能（全部）装，则将有物品不能（全部）装 入背包中。由于入背包中。由于0 xi1xi1，所以可以把物品的一部分装入背包，所以最，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为终背包中可刚好装入重量为M M的若干物品（整个或一部分）的若干物品（整个或一部分）目标目标：使装入背包的物品的：使装入背包的物品的总效益总效益达到达到最大最大。niiixw12022-12-24问题的形
11、式描述问题的形式描述 目标函数目标函数：约束条件约束条件：可可 行行 解解：满足上述约束条件的：满足上述约束条件的任一集合任一集合(x1,x2,xn)都是问题都是问题 的一个可行解的一个可行解可行解可能为多个。可行解可能为多个。(x1,x2,xn)称为问题的一个称为问题的一个解向量解向量 最最 优优 解解：能够使目标函数取：能够使目标函数取最大值最大值的可行解是问题的的可行解是问题的 最优解最优解最优解也可能为多个。最优解也可能为多个。niiixp1niwpxMxwiiiniii1,0,0,1012022-12-24例例4.1 背包问题的实例背包问题的实例 设，设，n=3，M=20，(p1,p
12、2,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.5iixpiixw2022-12-242.贪心策略求解贪心策略求解 度量标准的选择：三种不同的选择度量标准的选择：三种不同的选择1）以）以目标函数目标函数作为度量标准作为度量标准 即，每装入一件物品，就使背包背包获得即，每装入一件物品，就使背包背包获得最大最大可能的效益增可能的效益增量。量。该
13、度量标准下的该度量标准下的 处理规则：处理规则：按效益值的非增次序将物品一件件地放入到背包；按效益值的非增次序将物品一件件地放入到背包；如果正在考虑的物品放不进去，则只取其一部分装满背包：如如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下剩下的物的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。如：若如：若M=2M=2,背包外还剩两件物品背包外还剩两件物品i,ji,j，且有，且有(pi 4，wi4
14、)和和(pj 3，wj2)，则下一步应选择，则下一步应选择j而非而非i放入背包：放入背包：pi/2=2 pj 32022-12-24实例分析（例实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)p1p2 p3 首先将首先将物品物品1 1放入背包，此时放入背包，此时x11，背包获得，背包获得p125的效益增量，同时背包容的效益增量，同时背包容量减少量减少w118个单位，剩余空间个单位，剩余空间M=2M=2。其次考虑其次考虑物品物品2 2和和3 3。就。就M=2M=2而言有，只能选择物品而言有，只能选择物品2 2或或3 3的的一部分一部分装入
15、背包。装入背包。物品物品2 2：若若 x22/15，则则 p2 x216/53.1 物品物品3 3：若若 x32/10，则则 p3 x33 为使背包的效益有最大的增量，应选择为使背包的效益有最大的增量，应选择物品物品2的的2/15装包，即装包，即 x22/15 最后，背包装满，最后，背包装满，M=0M=0，故，故物品物品3 3将不能装入背包，将不能装入背包，x30 。背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 28.2 (次优解次优解,非问题的最优解非问题的最优解)2022-12-242）以）以容量容量作为度量标准作为度量标准 以以目标函数目标函数作为度量标
16、准所存在的问题：尽管背包的效作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入了，从而不能装入“更多更多”的物品。的物品。改进：让背包改进：让背包容量容量尽可能慢地消耗，从而可以尽量装入尽可能慢地消耗，从而可以尽量装入“更多更多”的物品。的物品。即，新的标准是：以即，新的标准是：以容量容量作为度量标准作为度量标准 该度量标准下的处理规则：该度量标准下的处理规则：按物品按物品重量的非降次序重量的非降次序将物品装入到背包；将物品装入到背包；如果正在考虑的物品放不进去，则只取其一部分装如果正在
17、考虑的物品放不进去，则只取其一部分装满背包；满背包；2022-12-24实例分析（例实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)w3w2 w1 首先将首先将物品物品3 3放入背包，此时放入背包，此时x31，背包容量减少，背包容量减少w310个单个单位，还剩余空间位，还剩余空间M=10M=10。同时，。同时，背包获得背包获得p315的效益增量的效益增量。其次考虑其次考虑物品物品1 1和和2 2。就。就M=10M=10而言有，也只能选择物品而言有，也只能选择物品1 1或或2 2的的一一部分部分装入背包。装入背包。为使背包的按照为使背包的
18、按照“统一统一”的规则，下一步将放入的规则，下一步将放入物品物品2的的10/15装包，即装包，即 x210/152/3 最后，背包装满最后，背包装满M=0M=0，故，故物品物品1 1将不能装入背包，将不能装入背包，x10 。背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 31 (次优解次优解,非问题的最优解非问题的最优解)存在的问题：效益值没有得到存在的问题：效益值没有得到“最大最大”的增加的增加2022-12-243）最优的度量标准）最优的度量标准 影响背包效益值得因素：影响背包效益值得因素：n 背包的背包的容量容量Mn 放入背包中的物品的重量及其可能带来的效
19、益值放入背包中的物品的重量及其可能带来的效益值 可能的策略可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间是：在背包效益值的增长速率和背包容量消耗速率之间取得取得平衡平衡，即每次装入的物品应使它所占用的每一，即每次装入的物品应使它所占用的每一单位容量单位容量能获得当前能获得当前最大的单位效益。最大的单位效益。在这种策略下的在这种策略下的量度量度是：已装入的物品的累计效益值与所用容量之是：已装入的物品的累计效益值与所用容量之比。比。故，新的故，新的量度标准量度标准是：每次装入要使累计效益值与所用容量的比值是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其
20、后的装入）。有最多的增加（首次装入）和最小的减小（其后的装入）。此时，将按照物品的单位效益值：此时，将按照物品的单位效益值：pi/wi 比值（密度）的非增次序考比值（密度）的非增次序考虑。虑。2022-12-24实例分析（例实例分析（例4.1)(p1,p2,p3)=(25,24,15)，(w1,w2,w3)=(18,15,10)p1/w1p3/w3 p2/w2 首先将首先将物品物品2 2放入背包，此时放入背包，此时x21，背包容量减少，背包容量减少w215个单个单位，还剩余空间位，还剩余空间M=5M=5。同时，。同时，背包获得背包获得p224的效益增量的效益增量。其次考虑其次考虑物品物品1 1
21、和和3 3。此时，应选择物品。此时，应选择物品3,3,且就且就M=5M=5而言有，也而言有，也只能放入物品只能放入物品3 3的的一部分一部分到背包中到背包中 。即即 x35/101/2 最后，背包装满最后，背包装满M=0M=0，故，故物品物品1 1将不能装入背包，将不能装入背包，x10 。背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 31.5 (最优解最优解)2022-12-243.背包问题的贪心求解算法背包问题的贪心求解算法算法算法4.2 背包问题的贪心算法背包问题的贪心算法 procedure GREEDYKNAPSACK(P,W,M,X,n)/p(1:n
22、)和和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 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-KNA
23、PSACK2022-12-244.最优解的证明最优解的证明 即证明：由第三种策略所得到的贪心解是问题的即证明：由第三种策略所得到的贪心解是问题的最优解最优解。最优解最优解的含义：在满足约束条件的情况下，可使目标函数取极的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。目标函数取得极值。证明的证明的基本思想基本思想：将此贪心解与（假设中的）任一最优解：将此贪心解与（假设中的）任一最优解相比较相比较。如果这两个解相同，则显然贪心解就是最优解。否则，如果这两个解相同
24、，则显然贪心解就是最优解。否则，这两个解不同，就去找开始这两个解不同，就去找开始不同不同的第一个分量位置的第一个分量位置i，然后设，然后设法用贪心解的这个法用贪心解的这个xi去去替换替换最优解的那个最优解的那个xi，并证明最优解在分量代，并证明最优解在分量代换前后总的效益值没有任何变化。换前后总的效益值没有任何变化。可反复进行代换，直到新产生的最优解与贪心解完全一样。这一可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的代换过程中，最优解的效益值没有任何损失效益值没有任何损失，从而证明贪心解的效益，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优
25、解一样可取值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大得目标函数的最大/最小值。最小值。从而得证：该从而得证：该贪心解贪心解也即问题的也即问题的最优解最优解。2022-12-24 定理定理4.1 如果如果p1/w1 p2/w2 pn/wn,则算法则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。对于给定的背包问题实例生成一个最优解。证明证明：设设X=(x1,x2,xn)是是GRDDDY-KNAPSACK所生成的所生成的贪心解贪心解。如果所有的如果所有的xi都等于都等于1,则显然则显然X就是问题的就是问题的最优解最优解。否则，。否则，设设j
26、是使是使xi1的最小下标。由算法可知，的最小下标。由算法可知，l xi=1 1ij,l 0 xj 1l xi=0 jin 若若X不是问题的最优解，则必定存在一个可行解不是问题的最优解，则必定存在一个可行解 Y=(y1,y2,yn),使得：使得：且应有：且应有：iiiixpyp Mywii2022-12-24 设设k是使得是使得yk xk的最小下标，则有的最小下标，则有yk xk:a)若若k0,当且仅当作业当且仅当作业i在其截至期限以前被在其截至期限以前被完成时，则获得完成时，则获得pi0的效益。的效益。问题问题：求这：求这n个作业的一个子集个作业的一个子集J，其中的所有作业都可在其截至期，其中
27、的所有作业都可在其截至期限内完成。限内完成。J是问题的一个可行解。是问题的一个可行解。可行解可行解J中的中的 所有作业的效益之和是所有作业的效益之和是 ，具有，具有最大效益值的最大效益值的可可行解是该问题的最优解。行解是该问题的最优解。如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可决策应该执行哪些作业，以获得最大可能的效益值。能的效益值。目标函数：目标函数：约束条件：约束条件：所有的作业都应在其期限之前完成所有的作业都应在其期限之前完成
28、JiipJiip2022-12-24例例4.2 n=4，(p1，p2，p3，p4)(100,10,15,20)和和(d1，d2，d3，d4)(2,1,2,1)。可行解如下表所示：。可行解如下表所示：问题的最优解是问题的最优解是。所允许的处理次序是：先处理作业。所允许的处理次序是：先处理作业4 4再处理作业再处理作业1 1。可行解可行解（1）（2）（3）（4）（1,2）（1,3）（1,4）（2,3）（3,4）处理顺序处理顺序12342,11,3或或3,14,12,34,3效益值效益值10010152011011512025352022-12-241.带有限期的作业排序算法带有限期的作业排序算法1
29、)度量标准的选择度量标准的选择 以目标函数以目标函数 作为量度。作为量度。量度标准：下一个要计入的作业将是使得在满足所量度标准：下一个要计入的作业将是使得在满足所 产生的产生的J是一个可行解的限制条件下让是一个可行解的限制条件下让 得到最大增加的作业。得到最大增加的作业。处理规则：按处理规则：按pi的非增次序来考虑这些作业。的非增次序来考虑这些作业。JiipJiip2022-12-24例：例例：例4.2求解求解(p1，p2，p3，p4)(100,10,15,20)(d1，d2，d3，d4)(2,1,2,1)首先令首先令J=,作业作业1具有当前的最大效益值，且具有当前的最大效益值，且1是可行解，
30、是可行解，所以作业所以作业1计入计入J；在剩下的作业中，作业在剩下的作业中，作业4具有最大效益值，且具有最大效益值，且1,4也是可行解，故作业也是可行解，故作业4计入计入J，即，即J=1,4；考虑考虑1,3,4和和1,2,4均不能构成新的可行解，均不能构成新的可行解，作业作业3和和2将被舍弃。将被舍弃。故最后的故最后的J=1,4，最终效益值，最终效益值120（问题的（问题的最最优解优解）0Jiip2022-12-242)作业排序算法的概略描述作业排序算法的概略描述 算法算法4.3 procedure GREEDY-JOB(D,J,n)/作业按作业按p1p2pn的次序输入，它们的期限值的次序输入
31、，它们的期限值D(i)1,1in,n1。J是在它们的截止期限完成的作业的集合是在它们的截止期限完成的作业的集合/J1 for i2 to n do if Ji的所有作业能在它们的截止期限前完成的所有作业能在它们的截止期限前完成 then JJi endif repeat end GREEDY-JOB2022-12-242.最优解证明最优解证明 定理定理4.2 算法算法4.3对于作业排序问题总是得到问题的一个对于作业排序问题总是得到问题的一个最优解最优解证明证明：设设J是由算法所得的是由算法所得的贪心解贪心解作业集合，作业集合，I是一个是一个最优解最优解的的作业集合。作业集合。若若I=J，则，则
32、J就是最优解；否则就是最优解；否则 ，即至少存在两个作业，即至少存在两个作业a和和b，使得，使得aJ且且 ,bI且且 。并设并设a是这样的一个具有是这样的一个具有最高效益值最高效益值的作业，且由算法的作业，且由算法的处理规则可得：对于在的处理规则可得：对于在I中而不在中而不在J中的作业所有中的作业所有b，有：，有：papbIaJbIJJI 且2022-12-24 设设SJ和和SI分别是分别是J和和I的可行的的可行的调度表调度表。因为。因为J和和I都是可行解，都是可行解，故这样的调度表一定存在；故这样的调度表一定存在；设设i是既属于是既属于J又属于又属于I的一个作业，并的一个作业，并i设在调度表
33、设在调度表SJ中的调度中的调度时刻是时刻是t，t+1，而在而在SI中的调度时刻是中的调度时刻是t，t+1。在在SJ和和SI中作如下调整：中作如下调整：若若tt，则将则将SJ中在中在t，t+1时刻调度的那个作业（如时刻调度的那个作业（如果有的话）与果有的话）与i相交换。如果相交换。如果J中在中在t，t+1时刻没有作业调度，时刻没有作业调度，则直接将则直接将i移到移到t，t+1调度。调度。新的调度表也是可行的。反之，新的调度表也是可行的。反之，若若tt，则在，则在SI中作类似的调换，即将中作类似的调换，即将SI中在中在t，t+1时时刻调度的那个作业（如果有的话）与刻调度的那个作业（如果有的话）与i
34、相交换。如果相交换。如果I中在中在t，t+1时刻没有作业调度，则直接将时刻没有作业调度，则直接将i移到移到t，t+1调度。调度。同样，新同样，新的调度表也是可行的。的调度表也是可行的。对对J和和I中共有的所有作业作上述的调整。设调整后得到的调中共有的所有作业作上述的调整。设调整后得到的调度表为度表为SJ和和SI，则在，则在SJ和和SI中中J和和I中中共有共有的所有作业将在相同的的所有作业将在相同的时间被调度。时间被调度。2022-12-24 设设a在在SJ中的调度时刻是中的调度时刻是ta,ta+1，b是是SI中该时刻调中该时刻调度的作业。根据以上的讨论有：度的作业。根据以上的讨论有：papb。
35、在在SI中，去掉作业中，去掉作业b，而去调度作业，而去调度作业a，得到的是作业集，得到的是作业集合合I=I-b a的的 一个可行的调度表，且一个可行的调度表，且I的效益值不小于的效益值不小于I的效益值。而的效益值。而I中比中比I少了一个与少了一个与J不同的作业。不同的作业。重复上述的转换，可使重复上述的转换，可使I在在不减不减效益值的情况下转换成效益值的情况下转换成J。从而从而J至少有和至少有和I一样的效益值。所以一样的效益值。所以J也是最优解。也是最优解。证毕。证毕。2022-12-243.如何判断如何判断J的可行性的可行性方法一方法一：检验：检验J中作业所有可能的排列，对于任一种次序排列的
36、作中作业所有可能的排列，对于任一种次序排列的作 业排列，判断这些作业是否能够在其期限前完成业排列，判断这些作业是否能够在其期限前完成若若J 中有中有k个作业，则将要检查个作业，则将要检查k!个序列个序列方法二方法二：检查：检查J中作业的一个中作业的一个特定序列特定序列就可判断就可判断J的可行性：的可行性：对于所给出的一个排列对于所给出的一个排列i i1 1i i2 2iik k,由于作业由于作业i ij j完成的完成的 最早时间是最早时间是j j，因此只要判断出，因此只要判断出排列中的每个作业排列中的每个作业 d dijijjj，就可得知，就可得知是一个允许的调度序列，从而是一个允许的调度序列
37、，从而J J是一个是一个 可行解。反之，如果可行解。反之，如果排列中有一个排列中有一个d dijijj,j,则则将是一个将是一个 行不通的调度序列，因为至少作业行不通的调度序列，因为至少作业i ij j不能在其期限之前完不能在其期限之前完 成。成。这一检查过程可以只通过检验这一检查过程可以只通过检验J J中作业的一种特殊的排列：按照中作业的一种特殊的排列：按照作业作业期限的非降次序期限的非降次序排列的作业序列即可完成。排列的作业序列即可完成。2022-12-24 定理定理4.3 设设J是是k个作业的集合，个作业的集合，i1i2ik是是J中作业的一种排列，它中作业的一种排列，它使得使得di1di
38、2dik。J是一个可行解，是一个可行解，当且仅当当且仅当J中的作业可以按照中的作业可以按照的次的次序而又不违反任何一个期限的情况来处理。序而又不违反任何一个期限的情况来处理。证明：证明：如果如果J中的作业可以按照中的作业可以按照的次序而又不违反任何一个期限的情况的次序而又不违反任何一个期限的情况来处理，则来处理，则J是一个可行解是一个可行解 若若J是一个可行解，则必存在序列是一个可行解，则必存在序列r1r2rk，使得，使得drjj,1jk。若若，则，则即是可行解。否则，即是可行解。否则，令，令a是使得是使得raia的最小下标，并设的最小下标，并设rb=ia。则有：。则有：ba 且且 dradr
39、b (为什么为什么?)在在中调换中调换ra与与rb，所得的新序列，所得的新序列 s1s2sk的处理次序不违反任的处理次序不违反任何一个期限。何一个期限。重复上述过程，则可将重复上述过程，则可将转换成转换成且不违反任何一个期限。故且不违反任何一个期限。故是一个是一个可行可行的调度序列的调度序列 故定理得证故定理得证。2022-12-24 i1 i2 ia ic ikr1 r2 ra rb rk ab dradrb2022-12-245.带有限期的作业排序算法的实现带有限期的作业排序算法的实现 对当前正在考虑的作业对当前正在考虑的作业j，按限期大小采用一种，按限期大小采用一种“插入排序插入排序”的
40、方式，尝试将其的方式，尝试将其“插入插入”到一个按限期从小到大顺序构造的作到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解业调度序列中，以此判断是否能够合并到当前部分解J中。如果可中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。具体如下：具体如下：假设假设n个作业已经按照效益值从大到小的次序，即个作业已经按照效益值从大到小的次序，即p1p2pn的顺序排列好，每个作业可以在的顺序排列好，每个作业可以在单位时间单位时间内完成，并内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业具
41、有相应的时间期限；且至少有一个单位时间可以执行作业 首先，将作业首先，将作业1存入部分解存入部分解J中，此时中，此时J是可行的；是可行的；然后，依次考虑作业然后，依次考虑作业2到到n。假设已经处理了。假设已经处理了i-1个作业，其中个作业，其中有有k个作业计入了部分解个作业计入了部分解J中：中：J(1),J(2),J(k)，且有，且有 D(J(1)D(J(2)D(J(k)2022-12-24 对当前正在考虑的作业对当前正在考虑的作业i,i,将将D(i)D(i)依次和依次和D(J(k),D(J(k-D(J(k),D(J(k-1),1),，D(J(1)D(J(1)相比较，直到找到位置相比较，直到找
42、到位置q q：使得：使得 D(i)D(i)D(J(D(J(l l)，q ql lkk，且，且 D(J(q)D(i)D(J(q)D(i)此时，若此时，若D(J(D(J(l l)l l,q,ql lk,k,即说明即说明q q位置之后的所有作业位置之后的所有作业均可均可推迟推迟一个单位时间执行，而又不违反各自的执行期限。一个单位时间执行，而又不违反各自的执行期限。最后，将最后，将q q位置之后的所有作业后移一位，将作业位置之后的所有作业后移一位，将作业i i插入插入到位到位置置q q1 1处，从而得到一个包含处，从而得到一个包含k+1k+1个作业的新的可行解。个作业的新的可行解。若找不到这样的若找不
43、到这样的q q，作业，作业i i将被舍弃。将被舍弃。对对i i之后的其它作业重复上述过程直到之后的其它作业重复上述过程直到n n个作业处理完毕。最个作业处理完毕。最后后J J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。中所包含的作业集合是此时算法的贪心解，也是问题的最优解。2022-12-24算法算法4.4 带有限期和效益的单位时间的作业排序贪心算法带有限期和效益的单位时间的作业排序贪心算法 procedure JS(D,J,n,k)/D(1),D(n)是期限值。是期限值。n1。作业已按。作业已按p1p2pn的顺序排序。的顺序排序。J(i)是最优解中的第是最优解中的第i个作个作 业
44、，业，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)/将插入点的作业后移一位将插入
45、点的作业后移一位/repeat J(r+1)i;kk+1 endif repeat end JS2022-12-24计算时间分析计算时间分析 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设
46、设s是最终计入是最终计入J中的作业数，则算法中的作业数，则算法JS所需要的总时间是所需要的总时间是O(sn)。snn，故，故最坏情况最坏情况：T TJSJS=(n=(n2 2)，特例情况：，特例情况：p pi i=d=di i=n-i+1,1in=n-i+1,1in最好情况最好情况：T TJSJS=(n)=(n)，特例情况：，特例情况：d di i=i,1in=i,1in2022-12-246.一种一种“更快更快”的作业排序问题的作业排序问题 使用不相交集合的使用不相交集合的 UNION和和FIND算法算法（见（见1.4.3节），可以将节），可以将JS的计算时间降低到数的计算时间降低到数量级接
47、近量级接近(n)。（略）（略）2022-12-24例4.3 设n=5,(p1,p5)=(20,15,10,5,1),(d1,d5)=(2,2,1,3,3)。J011,21,21,2,4已分配时间片已分配时间片无无1,20,1,1,20,1,1,20,1,1,2,2,3正被考正被考虑作业虑作业12345动作动作分配分配1,2分配分配0,1不适合，舍弃不适合，舍弃分配分配2,3舍弃舍弃最优解是J1,2,42022-12-244.4 最优归并模式最优归并模式1.问题的描述问题的描述1）两个文件的归并问题）两个文件的归并问题 两个已知文件的一次归并所需的计算时间两个已知文件的一次归并所需的计算时间O(
48、两个文件的元素总数两个文件的元素总数)例：例：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 2022-12-24 二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归二路归并模式：每次仅作两个文件的归并；当有
49、多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。并的模式，最终得到一个完整的记录文件。二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。之为二元归并树。如如 归并树的构造归并树的构造 外结点：外结点：n个原始文件个原始文件 内结点：一次归并后得到的文件内结点：一次归并后得到的文件 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件示的文件归并成其本身所代表的文件6050302010
50、X1Z1XX3X22022-12-24不同的归并顺序带来的计算时间是不同的。不同的归并顺序带来的计算时间是不同的。例例4.5 已知已知X1,X2,X3是分别为是分别为30、20、10个记录长度的已分类文件。个记录长度的已分类文件。将这将这3个文件归并成长度为个文件归并成长度为60的文件。可能的归并过程和相应的记录移的文件。可能的归并过程和相应的记录移动次数如下：动次数如下：问题：采用怎样的归并顺序才能使归并过程中元素的移问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）动次数最小（或执行的速度最快）XX3X2X1移动50次移动60次XX1X2X3移动30次移动60次
