第4章贪心方法

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

1、第4章贪心方法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望本章教学要求及重点难点本章教学要求及重点难点n理解贪心方法的基本思想理解贪心方法的基本思想n掌握背包问题的求解方法掌握背包问题的求解方法n掌握带有限期的作业排序的基本方法掌握带有限期的作业排序的基本方法n掌握用贪心方法求解单源点最短路径的基本方掌握用贪心方法求解单源点最短路径的基本方法。法。 n重点：用贪心方法求背包问题及带有限期作业重点：用贪心方法求背包问题及带有限期作业排序；排序； n难点：用贪心

2、方法求单源点最短路径。难点：用贪心方法求单源点最短路径。 8/1/20244.1 一般方法一般方法1. 问题的一般特征问题的一般特征 问题有问题有n个输入，问题的解是由这个输入，问题的解是由这n个输入的某个个输入的某个子集子集组成，这个子组成，这个子集必须满足某些事先给定的条件。集必须满足某些事先给定的条件。n 约束条件约束条件：子集必须满足的条件；：子集必须满足的条件；n 可行解可行解：满足约束条件的子集；可行解可能不唯一；：满足约束条件的子集；可行解可能不唯一；n 目标函数目标函数：用来衡量可行解优劣的标准，一般以函数的形式给出；：用来衡量可行解优劣的标准，一般以函数的形式给出；n 最优解

3、最优解：能够使目标函数取极值（极大或极小）的可行解。：能够使目标函数取极值（极大或极小）的可行解。 分类分类：根据描述问题约束条件和目标函数的：根据描述问题约束条件和目标函数的数学模型数学模型的特性和问题的的特性和问题的求解方法求解方法的不同，可分为：线性规划、整数规划、非线性规划、动态规的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。划等。 最优化问题求解最优化问题求解 贪心方法贪心方法：一种改进的：一种改进的分级分级的处理方法，可对满足上述特征的某些问的处理方法，可对满足上述特征的某些问题方便地求解。题方便地求解。8/1/2024例例找零钱找零钱 一个小孩买了价值少于一个小孩买

4、了价值少于1元的糖，并将元的糖，并将1元的元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为假设提供数目不限的面值为25分、分、10分、分、5分及分及1分的硬分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。币。售货员分步骤组成要找的零钱数，每次加入一个硬币。 选择硬币时所采用的贪心算法如下：每一次选择应使零钱选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终要

5、找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。所需的数目。 假设需要找给小孩假设需要找给小孩67分，首先入选的是两枚分，首先入选的是两枚25分的硬币，分的硬币，第三枚入选的不能是第三枚入选的不能是25分的硬币，否则将不可行（零钱总分的硬币，否则将不可行（零钱总数超过数超过67分），第三枚应选择分），第三枚应选择10分的硬币，然后是分的硬币，然后是5分的，分的，最后加入两个最后加入两个1分的硬币。分的硬币。 贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）使找出的硬币数目最少（至少是接近

6、最少的数目）8/1/20242. 贪心方法的一般策略贪心方法的一般策略 问题的一般特征：问题的解是由问题的一般特征：问题的解是由n个输入的、满足某些事先给定个输入的、满足某些事先给定的条件的子集组成。的条件的子集组成。 1）一般方法）一般方法 根据题意，选取一种根据题意，选取一种度量标准度量标准。然后按照这种度量标准对。然后按照这种度量标准对n个输个输入入排序排序，并按序一次输入一个量。，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的如果这个输入和当前已构成在这种量度意义下的部分最优解部分最优解加在加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将一起不能产生

7、一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的当前输入合并到部分解中从而得到包含当前输入的新的部分解新的部分解。 2）贪心方法）贪心方法 这种能够得到某种量度意义下的最优解的这种能够得到某种量度意义下的最优解的分级处理分级处理方法称为方法称为贪心贪心方法方法注：注： 贪心解贪心解 最优解最优解 直接将目标函数作为直接将目标函数作为量度标准量度标准也不一定能够得到问题的最优解也不一定能够得到问题的最优解 3）使用贪心策略求解的关键）使用贪心策略求解的关键 选取能够得到问题最优解的量度标准。选取能够得到问题最优解的量度标准。8/1/20243. 贪心方

8、法的抽象化控制描述贪心方法的抽象化控制描述 procedure GREEDY(A,n) /A(1:n)包含包含n个输入个输入/ solution /将解向量将解向量solution初始化初始化为为空空/ for i1 to n do xSELECT(A) /按照度量按照度量标标准，从准，从A中中选择选择一个一个输输入，其入，其值赋值赋予予x 并将之从并将之从A中中删删除除/ if FEASIBLE(solution,x) then /判定判定x是否可以包含在解向量中，是否可以包含在解向量中， 即是否能共同构成可行解即是否能共同构成可行解/ solutionUNION(solution,x) /

9、将将x和当前的解向量合并成新的解和当前的解向量合并成新的解 向量，并修改目向量，并修改目标标函数函数/ endif repeat return(solution) end GREEDY 8/1/20244.2 背包问题背包问题1.问题的描述问题的描述 已知已知n种物品具有重量种物品具有重量(w1,w2,wn)和效益值和效益值(p1,p2,pn) ，及一，及一个可容纳个可容纳M重量的背包；设当物品重量的背包；设当物品i全部或一部分全部或一部分xi放入背包将得到放入背包将得到pi xi的的效益，这里，效益，这里，0 xi 1, p 1, pi 0 0。 问题问题：采用怎样的装包方法才能使装入背包的

10、物品的：采用怎样的装包方法才能使装入背包的物品的总效益最大总效益最大？ 分析分析： 装入背包的总重量装入背包的总重量不能超过不能超过M M 如果所有物品的如果所有物品的总重量总重量不超过不超过M M，即，即 M M，则把，则把所有所有的物的物品都装入背包中将获得最大可能的效益值品都装入背包中将获得最大可能的效益值 如果物品的总重量如果物品的总重量超过了超过了M M，则将有物品不能（全部）装，则将有物品不能（全部）装 入背包中。由于入背包中。由于0xi1xi1，所以可以把物品的一部分装入背包，所以最终，所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为背包中可刚好装入重量为M M的若

11、干物品（整个或一部分）的若干物品（整个或一部分） 目标目标：使装入背包的物品的：使装入背包的物品的总效益总效益达到达到最大最大。8/1/2024问题的形式描述问题的形式描述 目标函数目标函数： 约束条件约束条件： 可可 行行 解解：满足上述约束条件的：满足上述约束条件的任一集合任一集合(x1,x2,xn) 都是问题都是问题 的一个可行解的一个可行解可行解可能为多个。可行解可能为多个。 (x1,x2,xn)称为问题的一个称为问题的一个解向量解向量 最最 优优 解解：能够使目标函数取：能够使目标函数取最大值最大值的可行解是问题的的可行解是问题的 最优解最优解最优解也可能为多个。最优解也可能为多个。

12、8/1/2024例例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.58/1/20242. 贪心策略求解贪心策略求解 度量标准的选择：三种不同的选择度量标准的选择：三种不同的选择1）以）以目标函数目标函数作为度量标准作为度量标

13、准 即，每装入一件物品，就使背包背包获得即，每装入一件物品，就使背包背包获得最大最大可能的效益增可能的效益增量。量。 该度量标准下的该度量标准下的 处理规则：处理规则： 按效益值的非增次序将物品一件件地放入到背包；按效益值的非增次序将物品一件件地放入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在该物品的一部分不满足获得最大效益增量的度量标准，则在剩下剩下的物品的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。种选择可以获得最大效益增量的其它物品，将它

14、或其一部分装入背包。 如：若如：若M=2M=2, ,背包外还剩两件物品背包外还剩两件物品i,ji,j，且有，且有(pi 4，wi4) 和和(pj 3，wj2)，则下一步应选择，则下一步应选择j而非而非i放入背包：放入背包： pi/2 = 2 pj 38/1/2024实例分析（例实例分析（例4.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1p2 p3 首先将首先将物品物品1 1放入背包，此时放入背包，此时x11，背包获得，背包获得p125的效益增量，同时背包容的效益增量，同时背包容量减少量减少w118个单位，剩余空间个单位，剩余空间M=

15、2M=2。 其次考虑其次考虑物品物品2 2和和3 3。就。就M=2M=2而言有，只能选择物品而言有，只能选择物品2 2或或3 3的的一部分一部分装入背包。装入背包。 物品物品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 p2

16、x3 p3 28.2 (次优解次优解,非问题的最优解非问题的最优解)8/1/20242）以）以容量容量作为度量标准作为度量标准 以以目标函数目标函数作为度量标准所存在的问题：尽管背包的效作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入了，从而不能装入“更多更多”的物品。的物品。 改进：让背包改进：让背包容量容量尽可能慢地消耗，从而可以尽量装入尽可能慢地消耗，从而可以尽量装入“更多更多”的物品。的物品。 即，新的标准是：以即，新的标准是：以容量容量作为度量标准作为度量标准 该度量标准下的

17、处理规则：该度量标准下的处理规则： 按物品按物品重量的非降次序重量的非降次序将物品装入到背包；将物品装入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满如果正在考虑的物品放不进去，则只取其一部分装满背包；背包；8/1/2024实例分析（例实例分析（例4.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) w3w2 w1 首先将首先将物品物品3 3放入背包，此时放入背包，此时x31，背包容量减少，背包容量减少w310个单位，个单位，还剩余空间还剩余空间M=10M=10。同时，。同时，背包获得背包获得p315的效益增量的效益增量。 其次考虑

18、其次考虑物品物品1 1和和2 2。就。就M=10M=10而言有，也只能选择物品而言有，也只能选择物品1 1或或2 2的的一一部分部分装入背包。装入背包。为使背包的按照为使背包的按照“统一统一”的规则，下一步将放入的规则，下一步将放入物品物品2的的10/15装包，即装包，即 x210/152/3 最后，背包装满最后，背包装满M=0M=0，故，故物品物品1 1将不能装入背包，将不能装入背包，x10 。 背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 31 (次优解次优解,非问题的最优解非问题的最优解) 存在的问题：效益值没有得到存在的问题：效益值没有得到“最大最大”

19、的增加的增加8/1/20243）最优的度量标准）最优的度量标准 影响背包效益值得因素：影响背包效益值得因素：n 背包的背包的容量容量Mn 放入背包中的物品的重量及其可能带来的效益值放入背包中的物品的重量及其可能带来的效益值 可能的策略可能的策略是：在背包效益值的增长速率和背包容量消耗速率之间是：在背包效益值的增长速率和背包容量消耗速率之间取得取得平衡平衡，即每次装入的物品应使它所占用的每一，即每次装入的物品应使它所占用的每一单位容量单位容量能获得当前能获得当前最大的单位效益。最大的单位效益。 在这种策略下的在这种策略下的量度量度是：已装入的物品的累计效益值与所用容量之是：已装入的物品的累计效益

20、值与所用容量之比。比。 故，新的故，新的量度标准量度标准是：每次装入要使累计效益值与所用容量的比值是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。有最多的增加（首次装入）和最小的减小（其后的装入）。 此时，将按照物品的单位效益值：此时，将按照物品的单位效益值：pi/wi 比值（密度）的非增次序考比值（密度）的非增次序考虑。虑。8/1/2024实例分析（例实例分析（例4.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10) p1/ /w1p3/ /w3 p2/ /w2 首先将首先将物品物品2 2放入背包

21、，此时放入背包，此时x21，背包容量减少，背包容量减少w215个单个单位，还剩余空间位，还剩余空间M=5M=5。同时，。同时，背包获得背包获得p224的效益增量的效益增量。 其次考虑其次考虑物品物品1 1和和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 (最优解最优解

22、)8/1/20243. 背包问题的贪心求解算法背包问题的贪心求解算法算法算法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 X0 /将解向量初始化为空将解向量初始化为空/ cuM /cu是背包的剩余容量是背包的剩余容

23、量/ 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-KNAPSACK8/1/20244. 最优解的证明最优解的证明 即证明：由第三种策略所得到的贪心解是问题的即证明：由第三种策略所得到的贪心解是问题的最优解最优解。 最优解最优解的含义：在满足约束条件的情况下，可使目标函数取极的含义：在满足约束条件的情况下，可使目标函数取极（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使（大或小）值的可行解。贪心解是可行解，故只需证

24、明：贪心解可使目标函数取得极值。目标函数取得极值。 证明的证明的基本思想基本思想：将此贪心解与（假设中的）任一最优解：将此贪心解与（假设中的）任一最优解相比较相比较。 如果这两个解相同，则显然贪心解就是最优解。否则，如果这两个解相同，则显然贪心解就是最优解。否则， 这两个解不同，就去找开始这两个解不同，就去找开始不同不同的第一个分量位置的第一个分量位置i，然后设法，然后设法用贪心解的这个用贪心解的这个xi去去替换替换最优解的那个最优解的那个xi ，并证明最优解在分量代换，并证明最优解在分量代换前后总的效益值没有任何变化。前后总的效益值没有任何变化。 可反复进行代换，直到新产生的最优解与贪心解完

25、全一样。这一可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的代换过程中，最优解的效益值没有任何损失效益值没有任何损失，从而证明贪心解的效益，从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大得目标函数的最大/最小值。最小值。 从而得证：该从而得证：该贪心解贪心解也即问题的也即问题的最优解最优解。8/1/2024 定理定理4.1 如果如果p1/w1 p2/w2 pn/wn,则算法则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。对于给定的背

26、包问题实例生成一个最优解。证明证明： 设设X=(x1, x2, , xn)是是GRDDDY-KNAPSACK所生成的所生成的贪心解贪心解。 如果所有的如果所有的xi都等于都等于1,则显然则显然X就是问题的就是问题的最优解最优解。否则，。否则， 设设j是使是使xi1的最小下标。由算法可知，的最小下标。由算法可知，l xi=1 1ij,l 0xj 1l xi=0 jin 若若X不是问题的最优解，则必定存在一个可行解不是问题的最优解，则必定存在一个可行解 Y=(y1, y2, , yn),使得：使得： 且应有：且应有： 8/1/2024 设设k是使得是使得yk xk的最小下标，则有的最小下标，则有y

27、k xk: a) 若若k0,当且仅当作业当且仅当作业i在其截至期限以前被在其截至期限以前被完成时，则获得完成时，则获得pi0的效益。的效益。 问题问题：求这：求这n个作业的一个子集个作业的一个子集J，其中的所有作业都可在其截至期限，其中的所有作业都可在其截至期限内完成。内完成。J是问题的一个可行解。是问题的一个可行解。 可行解可行解J中的中的 所有作业的效益之和是所有作业的效益之和是 ，具有，具有最大效益值的最大效益值的可行可行解是该问题的最优解。解是该问题的最优解。 如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否

28、则，将有作业无法完成值；否则，将有作业无法完成决策应该执行哪些作业，以获得最大可决策应该执行哪些作业，以获得最大可能的效益值。能的效益值。 目标函数：目标函数： 约束条件：约束条件：所有的作业都应在其期限之前完成所有的作业都应在其期限之前完成8/1/2024例例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）1100（2）210（3）

29、315（4）420（1,2）2,1110（1,3）1,3或3,1115（1,4）4,1120（2,3）2,325（3,4）4,3358/1/20241. 带有限期的作业排序算法带有限期的作业排序算法1) 度量标准的选择度量标准的选择 以目标函数以目标函数 作为量度。作为量度。 量度标准：下一个要计入的作业将是使得在满足所量度标准：下一个要计入的作业将是使得在满足所 产生的产生的J是一个可行解的限制条件下让是一个可行解的限制条件下让 得到最大增加的作业。得到最大增加的作业。 处理规则：按处理规则：按pi的非增次序来考虑这些作业。的非增次序来考虑这些作业。8/1/2024例：例例：例4.2求解求解

30、 (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,4； 考考虑1,3,4和和1,2,4均不能构成新的可行解，均不能构成新的可行解，作作业3和和2将被舍弃。将被舍弃。 故最后的故最后的J=1,4，最，最终效益效益值120（问题的的最最优解解）8/1/20242)作业排序算法的概略描述作

31、业排序算法的概略描述 算法算法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-JOB8/1/20242. 最优解证明最优解证明 定理定理4.2 算法算法4.3对于作业排序问题总是得到问题的一个对于作业排序问题总是得到问题的一个

32、最优解最优解证明证明： 设设J是由算法所得的是由算法所得的贪心解贪心解作业集合，作业集合，I是一个是一个最优解最优解的作的作业集合。业集合。 若若I=J，则，则J就是最优解；否则就是最优解；否则 ，即至少存在两个作业，即至少存在两个作业a和和b，使得，使得aJ且且 ,bI且且 。 并设并设a是这样的一个具有是这样的一个具有最高效益值最高效益值的作业，且由算法的的作业，且由算法的处理规则可得：对于在处理规则可得：对于在I中而不在中而不在J中的作业所有中的作业所有b，有：，有： papb8/1/2024 设设SJ和和SI分别是分别是J和和I的可行的的可行的调度表调度表。因为。因为J和和I都是可行解

33、，都是可行解，故这样的调度表一定存在；故这样的调度表一定存在； 设设i是既属于是既属于J又属于又属于I的一个作业，并的一个作业，并i设在调度表设在调度表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

34、，则在，则在SI中作类似的调换，即将中作类似的调换，即将SI中在中在t，t+1时时刻调度的那个作业（如果有的话）与刻调度的那个作业（如果有的话）与i相交换。如果相交换。如果I中在中在t，t+1时刻没有作业调度，则直接将时刻没有作业调度，则直接将i移到移到t，t+1调度。调度。同样，新同样，新的调度表也是可行的。的调度表也是可行的。 对对J和和I中共有的所有作业作上述的调整。设调整后得到的调中共有的所有作业作上述的调整。设调整后得到的调度表为度表为SJ和和SI，则在，则在SJ和和SI中中J和和I中中共有共有的所有作业将在相同的的所有作业将在相同的时间被调度。时间被调度。8/1/2024 设设a在

35、在SJ中的调度时刻是中的调度时刻是ta, ta+1， b是是SI中该时刻调中该时刻调度的作业。根据以上的讨论有：度的作业。根据以上的讨论有：papb。 在在SI中，去掉作业中，去掉作业b，而去调度作业，而去调度作业a，得到的是作业集，得到的是作业集合合I=I-b a的的 一个可行的调度表，且一个可行的调度表，且I的效益值不小于的效益值不小于I的效益值。而的效益值。而I中比中比I少了一个与少了一个与J不同的作业。不同的作业。 重复上述的转换，可使重复上述的转换，可使I在在不减不减效益值的情况下转换成效益值的情况下转换成J。从而从而J至少有和至少有和I一样的效益值。所以一样的效益值。所以J也是最优

36、解。也是最优解。证毕。证毕。8/1/20243. 如何判断如何判断J的可行性的可行性方法一方法一：检验：检验J中作业所有可能的排列，对于任一种次序排列的作中作业所有可能的排列，对于任一种次序排列的作 业排列，判断这些作业是否能够在其期限前完成业排列，判断这些作业是否能够在其期限前完成若若J 中有中有k个作业，则将要检查个作业，则将要检查k!个序列个序列方法二方法二：检查：检查J中作业的一个中作业的一个特定序列特定序列就可判断就可判断J的可行性：的可行性： 对于所给出的一个排列对于所给出的一个排列i i1 1i i2 2iik k, ,由于作业由于作业i ij j完成的完成的 最早时间是最早时间

37、是j j，因此只要判断出，因此只要判断出排列中的每个作业排列中的每个作业 d dijijjj，就可得知，就可得知是一个允许的调度序列，从而是一个允许的调度序列，从而J J是一个是一个 可行解。反之，如果可行解。反之，如果排列中有一个排列中有一个d dijijj,j,则则将是一个将是一个 行不通的调度序列，因为至少作业行不通的调度序列，因为至少作业i ij j不能在其期限之前完不能在其期限之前完 成。成。 这一检查过程可以只通过检验这一检查过程可以只通过检验J J中作业的一种特殊的排列：按照中作业的一种特殊的排列：按照作业作业期限的非降次序期限的非降次序排列的作业序列即可完成。排列的作业序列即可

38、完成。8/1/2024 定理定理4.3 设设J是是k个作业的集合，个作业的集合，i1i2ik是是J中作业的一种排列，它中作业的一种排列，它使得使得di1di2dik。J是一个可行解，是一个可行解，当且仅当当且仅当J中的作业可以按照中的作业可以按照的次的次序而又不违反任何一个期限的情况来处理。序而又不违反任何一个期限的情况来处理。证明：证明： 如果如果J中的作业可以按照中的作业可以按照的次序而又不违反任何一个期限的情况来的次序而又不违反任何一个期限的情况来处理，则处理，则J是一个可行解是一个可行解 若若J是一个可行解，则必存在序列是一个可行解，则必存在序列r1r2rk，使得，使得drjj, 1j

39、k。 若若，则，则即是可行解。否则，即是可行解。否则， ，令，令a是使得是使得raia的最小下标，并设的最小下标，并设rb=ia。则有：。则有： ba 且且 dradrb (为什么为什么?) 在在中调换中调换ra与与rb，所得的新序列，所得的新序列 s1s2sk的处理次序不违反任何的处理次序不违反任何一个期限。一个期限。 重复上述过程，则可将重复上述过程，则可将转换成转换成且不违反任何一个期限。故且不违反任何一个期限。故是一个是一个可行可行的调度序列的调度序列 故定理得证故定理得证。8/1/2024 i1 i2 ia ic ikr1 r2 ra rb rk ab dradrb8/1/20245

40、. 带有限期的作业排序算法的实现带有限期的作业排序算法的实现 对当前正在考虑的作业对当前正在考虑的作业j，按限期大小采用一种，按限期大小采用一种“插入排序插入排序”的方式，尝试将其的方式，尝试将其“插入插入”到一个按限期从小到大顺序构造的作到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解业调度序列中，以此判断是否能够合并到当前部分解J中。如果可中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。具体如下：具体如下： 假设假设n个作业已经按照效益值从大到小的次序，即个作业已经按照效益值从大到小

41、的次序，即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)8/1/2024 对当前正在考虑的作业对当前正在考虑的作

42、业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)相比较，直到找到位置相比较，直到找到位置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位置之后的所有作业后移一位，

43、将作业位置之后的所有作业后移一位，将作业i i插入插入到位到位置置q q1 1处，从而得到一个包含处，从而得到一个包含k+1k+1个作业的新的可行解。个作业的新的可行解。 若找不到这样的若找不到这样的q q，作业，作业i i将被舍弃。将被舍弃。 对对i i之后的其它作业重复上述过程直到之后的其它作业重复上述过程直到n n个作业处理完毕。最个作业处理完毕。最后后J J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。中所包含的作业集合是此时算法的贪心解，也是问题的最优解。8/1/2024算法算法4.4 带有限期和效益的单位时间的作业排序贪心算法带有限期和效益的单位时间的作业排序贪心算法 p

44、rocedure JS(D,J,n,k) /D(1),D(n)是期限值。是期限值。n1。作业已按。作业已按p1p2pn的顺序排序。的顺序排序。J(i)是最优解中的第是最优解中的第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

45、) 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;kk+1 endif repeat end JS8/1/2024计算时间分析计算时间分析 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

46、(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)。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

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

48、8/1/20244.4 最优归并模式最优归并模式1. 问题的描述问题的描述1）两个文件的归并问题）两个文件的归并问题 两个已知文件的一次归并所需的计算时间两个已知文件的一次归并所需的计算时间O(两个文件的元素总数两个文件的元素总数) 例：例： n个记录的文件个记录的文件 (n+m) 个记录的文件个记录的文件 m个记录的文件个记录的文件 (n+m) 2）多个文件的归并）多个文件的归并 已知已知n个文件，将之归并成一个单一的文件个文件，将之归并成一个单一的文件 例：假定文件例：假定文件X1，X2， X3， X4，采用两两归并的方式，可能的归并模，采用两两归并的方式，可能的归并模式有：式有： X1+

49、X2=Y1+X3= Y2+X4= Y3 X1+X2 = Y1 + Y3 X3+X4=Y2 8/1/2024 二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。的模式，最终得到一个完整的记录文件。 二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，称之为二元归并树。为二元归并树。如如 归并树的构造归并树的构造 外结点：外结点：n个原始文件个原始文件 内结点：一次归并后得到的文件内结点：一次归并后得到的文

50、件 在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件的文件归并成其本身所代表的文件6050302010X1Z1XX3X28/1/2024不同的归并顺序带来的计算时间是不同的。不同的归并顺序带来的计算时间是不同的。 例例4.5 已知已知X1,X2,X3是分别为是分别为30、20、10个记录长度的已分类文件。个记录长度的已分类文件。将这将这3个文件归并成长度为个文件归并成长度为60的文件。可能的归并过程和相应的记录移动的文件。可能的归并过程和相应的记录移动次数如下：次数如下： 问题：采

51、用怎样的归并顺序才能使归并过程中元素的移问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）动次数最小（或执行的速度最快）XX3X2X1移动50次移动60次XX1X2X3移动30次移动60次总移动次数：110次总移动次数：90次8/1/20242. 贪心求解贪心求解1) 度量标准的选择度量标准的选择 任意两个文件的归并所需的任意两个文件的归并所需的元素移动次数元素移动次数与这两个文件的与这两个文件的长度长度之和之和成成正比；正比； 度量标准度量标准：每次选择需要移动次数最少的两个集合进行归并；：每次选择需要移动次数最少的两个集合进行归并； 处理规则处理规则：每次选择长

52、度最小的两个文件进行归并。：每次选择长度最小的两个文件进行归并。95355203060301510F4F3Z1Z2Z4Z3F1F5F2(F1,F2,F3,F4,F5) = (20,30,10,5,30)8/1/20242) 目标函数目标函数 目标目标：元素移动的次数最少：元素移动的次数最少 实例：为得到归并树根结点表示的归并文件，外部结点中每个实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数该外部结点到根的距离，即根到该外部文件记录需要移动的次数该外部结点到根的距离，即根到该外部结点路径的长度。如，结点路径的长度。如， F4 ： 则则F4中所有记录在整个归并过程中移

53、动的总量中所有记录在整个归并过程中移动的总量|F4|*3 带权外部路径长度带权外部路径长度：记：记di是由根到代表文件是由根到代表文件Fi的外部结点的距的外部结点的距离，离，qi是是Fi的长度，则这棵树的代表的归并过程的元素移动总量是：的长度，则这棵树的代表的归并过程的元素移动总量是： 最优的二路归并模式最优的二路归并模式：与一棵具有：与一棵具有最小外部带权路径长度最小外部带权路径长度的二的二元树相对应。元树相对应。F4Z1Z2Z48/1/2024算法算法4.6 生成二元归并树的算法生成二元归并树的算法 procedure TREE(L,n) /L是是n个单结点的二元树表个单结点的二元树表/

54、for i1 to n-1 do call GETNODE(T) /构造一构造一颗新新树T/ LCHILD(T) LEAST(L) /从表从表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 TREE8/1/2024例例4.6 已知六个初始文件，长度分别为：已知六个初

55、始文件，长度分别为：2,3,5,7,9,13。 采用算法采用算法TREE，各阶段的工作状态如图所示：，各阶段的工作状态如图所示：L迭代23579130235791315235791325108/1/20242357913351016235791345101623235791355101623398/1/2024时间分析时间分析 1) 循环体：循环体：n-1次次 2) L以有序序列表示以有序序列表示 LEAST(L): (1) INSERT(L,T): (n) 总时间： (n2) 3) L以以min-堆表示堆表示 LEAST(L): (logn) INSERT(L,T): (logn) 总时间：

56、 (nlogn)8/1/20243. 最优解的证明最优解的证明 定理定理3.4 若若L最初包含最初包含n1个单结点的树，这些树有个单结点的树，这些树有WEIGHT值为值为(q1,q2,qn)，则算法，则算法TREE对于具有这些长度的对于具有这些长度的n个文件生成一棵最优个文件生成一棵最优的二元归并树。的二元归并树。证明：证明：归纳法归纳法证明证明 当当n=1时，返回一棵没有内部结点的树。定理得证。时，返回一棵没有内部结点的树。定理得证。 假定算法对所有的假定算法对所有的(q1,q2,qn)，1mn,生成一棵最优二元归生成一棵最优二元归并树。并树。 对于对于n,假定假定q1q2qn,则则q1和和

57、q2将是在将是在for循环的第一次迭代循环的第一次迭代中首先选出的具有最小中首先选出的具有最小WEIGHT值的两棵树（的值的两棵树（的WEIGHT值）；如图所值）；如图所示，示，T是由这样的两棵树构成的子树：是由这样的两棵树构成的子树：q1q2q1+q2T8/1/2024 设设T是一棵对于是一棵对于(q1,q2,qn)的最优二元归并树。的最优二元归并树。 设设P是是T中距离根中距离根最远最远的一个的一个内部结点内部结点。 若若P的两棵子树不是的两棵子树不是q1和和q2，则用，则用q1和和q2代换代换P当前的子树而当前的子树而不会增加不会增加T的带权外部路径长度。的带权外部路径长度。 故，故，T

58、应是最优归并树中的子树。应是最优归并树中的子树。 则在则在T中用一个权值为中用一个权值为q1q2的外部结点代换的外部结点代换T，得到的是一，得到的是一棵关于棵关于(q1q2,qn)最优归并树最优归并树T”。 而由归纳假设，在用权值为而由归纳假设，在用权值为q1q2的外部结点代换了的外部结点代换了T之后，之后，过程过程TREE将针对将针对(q1q2,qn)得到一棵最优归并树。将得到一棵最优归并树。将T带入带入该树，根据以上讨论，将得到关于该树，根据以上讨论，将得到关于(q1,q2,qn)的最优归并树。的最优归并树。 故，故，TREE生成一棵关于生成一棵关于(q1,q2,qn)的的最优归并树最优归

59、并树。8/1/20245. k路归并模式路归并模式 每次每次同时同时归并归并k个文件。个文件。 k元归并树：可能需要增加元归并树：可能需要增加“虚虚”结点，以补充不足的结点，以补充不足的外部结点。外部结点。 如果一棵树的所有内部结点的度都为如果一棵树的所有内部结点的度都为k，则外部结点，则外部结点数数n满足满足 n mod (k-1) = 1 对于满足对于满足 n mod (k1) =1的整数的整数n，存在一棵具有，存在一棵具有n个外部结点的个外部结点的k元树元树T，且，且T中所有结点的度为中所有结点的度为k。 至多需要增加至多需要增加k-2个外部结点。个外部结点。 k路最优归并模式得贪心规则

60、：每一步选取路最优归并模式得贪心规则：每一步选取k棵具有最小棵具有最小长度的子树归并。长度的子树归并。8/1/20244.5 最小生成树最小生成树1. 问题的描述问题的描述 生成树生成树：设：设G=(V,E)是一个无向连通图。如果是一个无向连通图。如果G的生的生 成子图成子图T=(V,E)是一棵树，则称是一棵树，则称T是是G的一棵的一棵 生成树生成树(spanning tree) 最小生成树最小生成树:2. 贪心策略贪心策略 度量标准：选择能使迄今为止所计入的边的度量标准：选择能使迄今为止所计入的边的成本和成本和有有最小最小 增加增加的那条边。的那条边。 Prim算法算法 Kruskal算法算

61、法 8/1/20243. Prim算法算法 策略：使得迄今所选择的边的集合策略：使得迄今所选择的边的集合A构成一棵树；对将要计入到构成一棵树；对将要计入到A中中的下一条边的下一条边(u,v)，应是，应是E中一条当前不在中一条当前不在A中且使得中且使得A(u,v)(u,v)也是一棵也是一棵树的最小成本边。树的最小成本边。1462531030204525 554050153512162162316234边(1,2)(2,6)(3,6)(6,4)成本102515208/1/20241462531020251535边(3,5)成本35V(TP) = 1,2,3,4,5,6E(TP) = (1,2),(

62、2,6),(3,5),(4,6),(3,6) 8/1/2024算法算法4.7 Prim最小生成树算法最小生成树算法 procedure PRIM(E,COST,n,T,mincost) /E是是G的边集。的边集。COST(n,n)是是n结点图结点图G的成本邻接矩阵，矩阵元素的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边是一个正实数，如果不存在边(i,j)，则为，则为。计算一棵最小生成。计算一棵最小生成树并把它作为一个集合存放到数组树并把它作为一个集合存放到数组T(1:n-1,2)中中(T(i,1),T(i,2)是最小成本是最小成本生成树的一条边。最小成本生成树的总成本最后

63、赋给生成树的一条边。最小成本生成树的总成本最后赋给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 COST(i,l) COST(i,k) then NEAR(i)l else NEAR(i) k endif repeat8/1/2024 NEAR(k)NEAR(l)0 for i2 to n-1 do /找找T的其余的

64、其余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 repeat repeat if mincost then print(no spanning tree) endif end PRIM8/1/2024计算复算复杂性：性： 第第3行花费行花费(e)(e

65、=|E|)时间，第时间，第4行花费行花费(1)时间；第时间；第69行的循环花费行的循环花费(n)时间；第时间；第12行和第行和第1620行的循行的循环要求环要求(n)时间，因此第时间，因此第1121行循环要花费行循环要花费(n)时间。时间。 所以所以PRIM算法具有算法具有 的时间复杂度的时间复杂度8/1/2024另一种另一种PRIM算法算法n最小生成树中包含了与每个结点最小生成树中包含了与每个结点v相关的相关的一条最小成本边一条最小成本边 证明略证明略n 方法：从一棵包含任何一个随意指定的方法：从一棵包含任何一个随意指定的结点而没有边的树开始这一算法，然后再结点而没有边的树开始这一算法，然后

66、再逐条增加边。逐条增加边。8/1/20244. Kruskal算法算法 （连通）图的边按成本的非降次序排列，下一条计入生成树（连通）图的边按成本的非降次序排列，下一条计入生成树T中的边中的边是还没有计入的边中具有最小成本、且和是还没有计入的边中具有最小成本、且和T中现有的边不会构成环路的边。中现有的边不会构成环路的边。1462531030204525 554050153512162162316234边(1,2)(3,6)(4,6)(2,6)成本1015202516234563453454558/1/20241462531020251535边(1,4)(3,5)成本30 舍弃35V(TK) =

67、1,2,3,4,5,6E(TK) = (1,2),(2,6),(3,5),(4,6),(3,6) 8/1/2024算法算法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堆堆

68、 PARENT1/每个每个结点都在不同的集合中点都在不同的集合中/ imincost0 while in-1 and 堆非空堆非空 do 从堆中从堆中删去最小成本去最小成本边(u,v)并重新构造堆并重新构造堆 jFIND(u); 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 KRUSKAL8/1/2024注：注： 边集以边集以min-

69、堆的形式保存，一条当前最小成本边可以在堆的形式保存，一条当前最小成本边可以在(loge)的的时间时间内找到；内找到； 当且当且仅仅当当图图G是不是不连连通的，通的，in-1n-1；此；此时算法具有最坏的算法具有最坏的执行行时间； 算法的算法的计算算时间是是(eloge)8/1/20244.6 单源点最短路径单源点最短路径1. 问题描述问题描述n 最短路径问题：最短路径问题： 每对结点之间的路径问题每对结点之间的路径问题 特定线路下的最短路径问题特定线路下的最短路径问题 单源最短路径问题等单源最短路径问题等n 单源最短路径问题单源最短路径问题 已知一个已知一个n结点有向图结点有向图G=(V,E)

70、和边的权函数和边的权函数c(e)，求由求由G中某指定结点中某指定结点v0到其它各结点的最短路径。到其它各结点的最短路径。 假定边的权值为正。假定边的权值为正。8/1/2024n例例4.10 如图所示。设如图所示。设v0是起始点，求是起始点，求v0到其它到其它各结点的最短路径。各结点的最短路径。 路径路径 长度长度(1) v0v2 10(2) v0v2v3 25(3) v0v2v3v1 45(4) v0v4 45注：路径按照长度的注：路径按照长度的非降次序非降次序给出给出v0v1v4v5v3v24545101520101533520308/1/20242. 贪心策略求解贪心策略求解1) 度量标准

71、度量标准 量度的选择：迄今已生成的量度的选择：迄今已生成的所有路径长度之和所有路径长度之和为使之为使之达到最小，其中任意一条路径都应具有最小长度：达到最小，其中任意一条路径都应具有最小长度： 假定已经构造了假定已经构造了i条最短路径，则下一条要构造的路径应是下条最短路径，则下一条要构造的路径应是下一条最短的路径。一条最短的路径。 处理规则：按照处理规则：按照路径长度路径长度的的非降次序非降次序依次生成从结点依次生成从结点v0到到其它各结点的最短路径。其它各结点的最短路径。 例：例： v0v2 v0v2v3 v0v2v3v1 v0v4 8/1/20242) 贪心算法贪心算法 设设S是已经对其生成

72、了最短路径的是已经对其生成了最短路径的结点集合结点集合（包括（包括v0)。 对于当前不在对于当前不在S中的结点中的结点w，记，记DIST(w)是从是从v0开始，开始，只经过只经过S中的结点而在中的结点而在w结束的那条最短路径的长度。结束的那条最短路径的长度。则有，则有，SW8/1/2024 如果下一条最短路径是到结点如果下一条最短路径是到结点u u，则这条路径是从结点，则这条路径是从结点v0v0出发在出发在u u处终止，且处终止，且只经过只经过那些在那些在S S中的结点中的结点, ,即由即由v0v0至至u u的这条最短路径上的的这条最短路径上的所有所有中间结点中间结点都是都是S S中的结点中的

73、结点: : 设设w w是这条路径上的任意中间结点，则从是这条路径上的任意中间结点，则从v0v0到到u u的路径也包含了一的路径也包含了一条从条从v0v0到到w w的路径，且其长度小于从的路径，且其长度小于从v0v0到到u u的路径长度。的路径长度。 v0,s1,s2, v0,s1,s2,w w,sm-1,u,sm-1,u 均在均在S S中中 根据根据生成规则：生成规则：最短路径是按照路径长度的非降次序生成的，最短路径是按照路径长度的非降次序生成的，因此从因此从v0v0到到w w的最短路径应该已经生成。从而的最短路径应该已经生成。从而w w也应该在也应该在S S中。中。 故故, ,不存在不存在不

74、在不在S S中的中间结点。中的中间结点。 所生成的下一条路径的终点所生成的下一条路径的终点u u必定是所有不在必定是所有不在S S内的结点中且具内的结点中且具有最小距离有最小距离DIST(u)DIST(u)的结点。的结点。8/1/2024如果选出了这样结点如果选出了这样结点u u并生成了从并生成了从v0v0到到u u的最短路径之后，结点的最短路径之后，结点u u将成为将成为S S中的一个成员。此时，那些从中的一个成员。此时，那些从v0v0出发，出发，只经过只经过S S中的结点并且在中的结点并且在S S外的结外的结点点w w处结束的最短路径可能会处结束的最短路径可能会减少减少DIST(w)DIS

75、T(w)的值变小：的值变小： 如果这样的路径的长度发生了改变，则这些路径必定是一条从如果这样的路径的长度发生了改变，则这些路径必定是一条从v0v0开开始，经过始，经过u u然后到然后到w w的的更短更短的路所致。的路所致。 根据根据DIST(w)DIST(w)的定义，它所表示的的定义，它所表示的v0v0至至w w的最短路径上的所有中间的最短路径上的所有中间结点都在结点都在S S中；中； 只考虑只考虑EE和和 的情况的情况 u u是从是从v0v0至至w w的最短路径上所经过的结点。的最短路径上所经过的结点。 则有：则有：DIST(w) = DIST(u) + c(u,w)DIST(w) = DI

76、ST(u) + c(u,w)SWuv08/1/2024算法算法4.10 生成最短路径的贪心算法生成最短路径的贪心算法 procedure SHORTEST-PATHS(v,COST,DIST,n) /G是一个是一个n结点有向图，它由其成本邻接矩阵结点有向图，它由其成本邻接矩阵COST(n,n)表示表示DIST(j)被置被置 以结点以结点v到结点到结点j的最短路径长度，这里的最短路径长度，这里1jn。DIST(v)被置成零被置成零/ boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,I,w for i1 to n do /

77、将集合将集合S初始化初始化为空空/ S(i) 0;DIST(i) COST(v,i) repeat S(v) 1;DIST(v) 0 /结点点v计入入S/ for num2 to n-1 do /确定由确定由结点点v出出发的的n-1条路条路/ 选取取结点点u,它使得它使得DIST(u)= S(u) 1 /结点点u计入入S/ for 所有所有S(w)0的的结点点w do /修改修改DIST(w)/ DIST(w) = min(DIST(w), DIST(u) + COST(u,w) repeat repeat end SHORTEST-PATHS8/1/20243) 计算时间计算时间 算法算法3

78、.103.10的的计计算算时间时间是：是：(n2) for i1 to n do S(i) 0;DIST(i) COST(v,i) repeat for num2 to n-1 do 选取取结点点u,它使得它使得DIST(u)= S(u) 1 for 所有所有S(w)0的的结点点w do DIST(w) = min(DIST(w), DIST(u) + COST(u,w) repeat repeat最短路径算法的最短路径算法的时间时间复复杂杂度度 由于任何一条由于任何一条边都有可能都有可能是最短路径中的是最短路径中的边，所以求任何最，所以求任何最短路径的算法都必短路径的算法都必须至少至少检查图

79、中的每条中的每条边一次，所以一次，所以这样的算的算法的最小法的最小时间是是(e)。 邻接矩接矩阵表示的表示的图： (n2) 8/1/2024例例4.11 求下图中从求下图中从v1出发到其余各结点的最短路径出发到其余各结点的最短路径v1v2v4v3v5v6v7205025705070105055403025图的成本邻接矩阵：图的成本邻接矩阵： 0 20 50 30 + + + 0 25 + + 70 + + 0 40 25 50 + + + 0 55 + + + + + 0 10 70+ + + + + 0 50+ + + + + + 08/1/2024算法的执行轨迹描述算法的执行轨迹描述迭代选

80、取的结点S DIST (1) (2) (3) (4) (5) (6) (7)置初值123452435611,21,2,41,2,4,31,2,4,3,51,2,4,3,5,6 0 20 50 30 + + + 0 20 45 30 + 90 + 0 20 45 30 85 90 + 0 20 45 30 70 90 + 0 20 45 30 70 90 140 0 20 45 30 70 90 130算法的执行在有算法的执行在有n-1个结点加入到个结点加入到S中后终止中后终止8/1/20243. 最短路径生成树最短路径生成树 对于无向连通图对于无向连通图G，由结点，由结点v到其余各结点的最短路

81、径的边构到其余各结点的最短路径的边构成成G的一棵的一棵生成树生成树，称为，称为最短路径生成树最短路径生成树。 注：不同起点注：不同起点v的生成树可能不同。的生成树可能不同。21356748555254035151050204530213567485254015102030213567485552515104530 原始图原始图 由结点由结点1出发的最短路径生成树出发的最短路径生成树 最小成本生成树最小成本生成树 8/1/2024思考题思考题1在在Dijkstra算法中，事先约定了所有边的权算法中，事先约定了所有边的权值为正数。如果边的权可以为负数，那么值为正数。如果边的权可以为负数，那么Dij

82、kstra算法是否仍然成立？算法是否仍然成立？2 假定对于一个图假定对于一个图G，已经生成了一棵由节点，已经生成了一棵由节点v出发的最短路径生成树出发的最短路径生成树p。如果图。如果图G中所有边中所有边的权值由的权值由ai变成变成ai2，ai0，这时，这时，p是否依然是否依然是图是图G的最短路径生成树？的最短路径生成树？8/1/2024习题一习题一n6.链接表表示队列时的插入和删除元素的算法链接表表示队列时的插入和删除元素的算法ADDQ和和DELETEQ。8/1/202418.计算计算F1（1），），F1（2），），F1（3），），F1（4）的轨）的轨迹，将其计算时间与过程迹，将其计算时间与过

83、程F（n）比较。）比较。procedure F1(n) /返回第返回第n个斐波那契数个斐波那契数/ integer n if n 2 then return(1) else return(F2(2,n,1,1) endifend F1procedure F2(i,n,x,y) if i n then call F2(i+1,n,y,x+y) endif return(y)end F28/1/202419.在数据集在数据集n=5,A(1:5)=10,20,12,18,16上上模拟过程模拟过程MAX1procedure MAX1(i) / 查找数组查找数组A中最大值元素，并返回该元素的最大下标。中

84、最大值元素，并返回该元素的最大下标。/ global integer n,A(1:n),j,k integer i if i A(j) then ki else kj endif else kn endif return(k) /递归调用的返回用的返回/ end MAX1 8/1/202423.BINOM(n,m)= BINOM(n-1,m)+ BINOM(n-1,m-1) BINOM(n,0)= BINOM(n,n)=0写一个递归程序。写一个递归程序。8/1/2024习题二习题二2.递归表达式递归表达式T(n)= g(n) n足够小足够小 2T(n/2)+f(n) 否则否则求求g(n)=O(

85、1) g(n)=O(1) 和和 f(n)=O(n) f(n)=O(n) g(n)=O(1) g(n)=O(1) 和和 f(n)=O(1) f(n)=O(1)8/1/20245.作一个三分检索算法，并分析此作一个三分检索算法，并分析此算法在各种情况下的计算复杂度。算法在各种情况下的计算复杂度。8/1/20249.找最大最小元素找最大最小元素8/1/202415.模拟执行模拟执行QUICKSORT算法算法 （1，1，1，1，1） （5，5，8，3，4，3，2）procedure PARTITION(m,p) integer m,p,i; global A(m:p-1) vA(m);im /A(m)

86、是划分元素是划分元素/ loop loop ii+1 until A(i)v repeat loop pp-1 until A(p)v repeat if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m)A(p)； A(p)vend PARTITION procedure QUICKSORT(p,q) integer p,q;global n,A(1:n) if pq then jq+1 call PARTITION(p,j) call QUICKSORT(p,j-1) call QUICKSORT(j+1,q) en

87、dif end QUICKSORT 8/1/2024n超难题超难题 n五个海盗抢到了五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们颗宝石，每一颗都一样大小和价值连城。他们决定这么分：决定这么分： 抽签决定自己的号码（抽签决定自己的号码（1、2、3、4、5） 首先，由首先，由1号提出分配方案，然后大家表决，当且仅当超过半号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼鱼 如果如果1号死后，再由号死后，再由2号提出分配方案，然后剩下的号提出分配方案，然后剩下的4人进行人进行表

88、决，当且仅当超过半数的人同意时，按照他的方案进行分配，表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼否则将被扔入大海喂鲨鱼 依此类推依此类推 条件：每个海盗都是很聪明的人，都能很理智地做出判断，条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。从而做出选择。 问题：第一个海盗提出怎样的分配方案才能使自己的收益最问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？大化？ 8/1/2024n设设5个人分别是个人分别是 假设前面的都扔海里了，由假设前面的都扔海里了，由来分，无论他怎么分（包括全来分，无论他怎么分（包括全给给），都面临被否决扔海里的

89、危险。），都面临被否决扔海里的危险。 所以，当所以，当来分时，来分时，一个不给，全由一个不给，全由独吞，独吞，为了避为了避免被扔海里的危险，也要同意，免被扔海里的危险，也要同意，的方案成立。的方案成立。 那么，在那么，在分时，分时，是肯定要反对的，要赢得是肯定要反对的，要赢得的同意，的同意，必须多给一个，否则有可能否决（对必须多给一个，否则有可能否决（对来说，反正来说，反正来分时还来分时还是是0,你不多给一个你不多给一个 就否决），所以就否决），所以的分配方案一定是：的分配方案一定是：98011 回到回到来的分配，由于来的分配，由于肯定反对，为了赢得肯定反对，为了赢得的同意，的同意，必须在必须在分配方案的基础上给他们加一个，由于只需再争取两票，分配方案的基础上给他们加一个，由于只需再争取两票，中可以中可以 排除争取一个，从收益来说，排除排除争取一个，从收益来说，排除中的一个即可，那么中的一个即可，那么的分配方案为：的分配方案为：981(或或)1 其它都不给！其它都不给！ 8/1/2024