第六章贪心法优秀课件.ppt

第六章贪心法第1页，本讲稿共48页第六章第六章 贪心法贪心法贪心法的学习提纲n一般方法一般方法n适合求解的问题适合求解的问题 n基本思想基本思想(求解问题的过程求解问题的过程)n算法控制流程算法控制流程n算法的正确性证明算法的正确性证明n应用举例应用举例n背包问题背包问题n带时限的作业排序问题带时限的作业排序问题第2页，本讲稿共48页 贪心算法的直观含义贪心算法的直观含义 例例1.1.如：找硬币如：找硬币0.150.15元，要求硬币数最少。找硬币方法就是一种元，要求硬币数最少。找硬币方法就是一种贪心算法贪心算法.（1 1）面值；）面值；5 5分、分、2 2分、分、1 1分：分：（2 2）面值：）面值：1111分、分、5 5分、分、1 1分：分：从此例可以看出：从此例可以看出：1 1，贪心法，贪心法未必未必总能求得问题的最优解；总能求得问题的最优解；2 2，贪心算法总是作出在当前看来是最好的选择，贪心算法总是作出在当前看来是最好的选择.也就是说贪心算法不从整体最优上加也就是说贪心算法不从整体最优上加以考虑以考虑,它所作出的选择只是在某种意义上的局部最优选择。它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题，最小生成树问题等。都能产生最优解。如单源最短路径问题，最小生成树问题等。而且而且,在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解！好的近似解！3个个5分分 (最优)1个个11分分4个个1分分 (次优)第3页，本讲稿共48页6.1 6.1 一般方法一般方法l贪心方法适合的问题是贪心方法适合的问题是最优化问题最优化问题。最优化问题：最优化问题：有有n n个输入，而它的解就由这个输入，而它的解就由这n n个输入的满足某些事先给定的个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值函数，称为目标函数，使目标函数取极值(极大或极小极大或极小)的可行解，称为最优解。的可行解，称为最优解。目标函数：目标函数：约束条件（函数）：约束条件（函数）：其中：其中：可行解：可行解：如找硬币问题可描述如下：如找硬币问题可描述如下：最优化问题的解可表示成最优化问题的解可表示成一个一个n n元组元组X=（x1,x2xn），），其中每个分量取自某个值集其中每个分量取自某个值集S，所有允许的所有允许的n-元组组成一个元组组成一个侯选解集。侯选解集。第4页，本讲稿共48页6.1 6.1 一般方法一般方法l贪心方法适合的问题是贪心方法适合的问题是最优化问题最优化问题。最优化问题：最优化问题：有有n n个输入，而它的解就由这个输入，而它的解就由这n n个输入的满足某些事先给定的个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值某个值函数，称为目标函数，使目标函数取极值(极大或极小极大或极小)的可行解，的可行解，称为最优解。称为最优解。最优化问题的解是一个最优化问题的解是一个n n元组元组n贪心法是通过贪心法是通过分步决策分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策，产生决策，产生n-n-元组的一个分量，贪心法要求根据题意，选定一种最优量度标准，作为选元组的一个分量，贪心法要求根据题意，选定一种最优量度标准，作为选择当前分量的依据，这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标择当前分量的依据，这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准（贪心准则，也称贪心选择性质）。准（贪心准则，也称贪心选择性质）。第5页，本讲稿共48页6.1 6.1 一般方法一般方法l贪心法的基本思想贪心法的基本思想:是依据题意选取一种量度标准，然后按照这种量度标准对这是依据题意选取一种量度标准，然后按照这种量度标准对这n n个输入进行排个输入进行排序，并按序一次输入一个量，作为序，并按序一次输入一个量，作为n-n-元组的一个分量，如果这个输入量的加入元组的一个分量，如果这个输入量的加入不满足约束条件不满足约束条件,则不把此输入加入到部分解向量中则不把此输入加入到部分解向量中.n贪心法求解问题的过程贪心法求解问题的过程:q选取最优量度标准选取最优量度标准q依最优量度标准对依最优量度标准对n n个输入排序个输入排序q初始状态下初始状态下,解向量解向量solution=solution=中中;q按序一次取一个输入量，作为按序一次取一个输入量，作为n-n-元组的一个分量，若加入该分量满足给定的约束条件，则元组的一个分量，若加入该分量满足给定的约束条件，则加入，否则，不加入，继续检测下一个分量加入，否则，不加入，继续检测下一个分量.第6页，本讲稿共48页贪心方法的抽象化控制贪心方法的抽象化控制算法算法6.1 贪心法的控制流程SolutionType Greedy(SType a，int n)SolutionType solutions=/将解向量将解向量solutionsolution初始化为空初始化为空 for(int i=0;i0.0.如果这些物品重量的和大于如果这些物品重量的和大于M,M,要求所有选中要要求所有选中要装入背包的物品总重量不得超过装入背包的物品总重量不得超过M,M,而装入背包物品获得的总效而装入背包物品获得的总效益最大益最大.即即 0 xil，pi0，wi0，0in-1 满足约束条件的任一集合满足约束条件的任一集合(x0，xn-1)是一个是一个可行解可行解(即能装下即能装下)，使，使目标函数取最大值目标函数取最大值的可行解是的可行解是最优解最优解。n背包问题描述：背包问题描述：约束条件：约束条件：第12页，本讲稿共48页 例例6.1 n3，M=20，P(25，24，15)，W=(18，15，10)假设物品可分，故有可行解无数个，其中的四个可行解是：假设物品可分，故有可行解无数个，其中的四个可行解是：(x0，x1，x2)wixi pixi (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 在这四个可行解中，第在这四个可行解中，第个解的效益值最大。但这个解是否是背包问题的最优解，尚个解的效益值最大。但这个解是否是背包问题的最优解，尚无法确定，但有一点是可以肯定的，即对于一般背包问题，其最优解显然必须装满背包。无法确定，但有一点是可以肯定的，即对于一般背包问题，其最优解显然必须装满背包。6.3 6.3 背包问题背包问题第13页，本讲稿共48页n贪心法求解背包问题贪心法求解背包问题q选择量度标准选择量度标准q计算在此量度标准下的计算在此量度标准下的”最优解最优解”n(1)选选目标函数目标函数作为量度标准作为量度标准,即即”效益效益”优先优先,使每装入一件使每装入一件物品就使背包获得最大可能的效益值增量物品就使背包获得最大可能的效益值增量.按物品收益从大到小排序按物品收益从大到小排序0,1,2 解为解为:(x0,x1,x2)=(1,2/15,0)收益收益:25+24*2/15=28.2 6.3 6.3 背包问题背包问题非最优解非最优解原因原因原因原因:只考虑当前收益最大只考虑当前收益最大只考虑当前收益最大只考虑当前收益最大,而背包可用容量消耗过快而背包可用容量消耗过快而背包可用容量消耗过快而背包可用容量消耗过快.M=20,P(25,24,15)W=(18，15，10)第14页，本讲稿共48页n贪心法求解背包问题贪心法求解背包问题q选择量度标准选择量度标准q计算在此量度标准下的计算在此量度标准下的”最优解最优解”n(2)选选重量重量作为量度作为量度,使背包容量尽可能慢地被消耗使背包容量尽可能慢地被消耗.6.3 6.3 背包问题背包问题按物品重量从小到大排序按物品重量从小到大排序:2,1,0;解为解为:(x0,x1,x2)=(0,2/3,1)收益收益:15+24*2/3=31 非最优解非最优解原因原因原因原因:虽然容量消耗慢，但效益没有很快的增加虽然容量消耗慢，但效益没有很快的增加虽然容量消耗慢，但效益没有很快的增加虽然容量消耗慢，但效益没有很快的增加.M=20,P(25,24,15)W=(18，15，10)第15页，本讲稿共48页n贪心法求解背包问题贪心法求解背包问题q选择量度标准选择量度标准q计算在此量度标准下的计算在此量度标准下的”最优解最优解”n(3)选选利润利润/重量重量为量度为量度 使每一次装入的物品应使它占用的每一单使每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。位容量获得当前最大的单位效益。6.3 6.3 背包问题背包问题M=20,P(25,24,15)W=(18，15，10)按物品的按物品的pi/wi重量从大到小排序重量从大到小排序:1,2,0;解为解为:(x0,x1,x2)=(0,1,1/2)收益收益:24+15/2=31.5 可见，可以可见，可以可见，可以可见，可以pi/wi 作为背包问题的最优量度标准作为背包问题的最优量度标准作为背包问题的最优量度标准作为背包问题的最优量度标准.最优解最优解第16页，本讲稿共48页算法算法6.2以以pi/wi为最优量度标准的背包问题的贪心算法为最优量度标准的背包问题的贪心算法 void GreedyKnapsack(float*p,float*w,float M,int n,float*x)/前置条件：前置条件：wi已按已按pi/wi的非增次序排列的非增次序排列 float u=M;/u为背包剩余载重量，初始时为为背包剩余载重量，初始时为m for(int i=0;in;i+)xi=0;/对解向量对解向量x初始化初始化 for(i=0;iu)break;xi=1.0;u=u wi;if(ipixi。不失一般性，可以假定不失一般性，可以假定wiyi=M。（2 2）设）设k是使得是使得ykxk的最小下标。可以推得的最小下标。可以推得ykxk。这可从三种可能发生的情况，即这可从三种可能发生的情况，即kj分别得证明：分别得证明：若若kj，(1,1,1,.,1,xj,0,0)K j因为因为 ykxk，从而，从而ykxk，显然有，显然有wiyiM，从而，从而ykj，(1,1,1,.,1,xj,0,0)j K反证法：所以,必有ykxk，有，有wiyiM，是不可能的。，是不可能的。第18页，本讲稿共48页 (3)(3)把把yk增加到增加到xk,那末必须从那末必须从(yk+1，yn-1)中减去同样多的量，使得所用的中减去同样多的量，使得所用的总容量仍是总容量仍是M。这导致一个新的解这导致一个新的解Z=(z0，zn-1)，其中，其中，zi=xi，0ik，并且并且 因此，对于因此，对于Z有有变换 Z不比不比Y差差,重复上面的讨论重复上面的讨论,把把Y Y转换成转换成X,从而证明了从而证明了X也是最优解也是最优解.证毕证毕。第19页，本讲稿共48页对于对于0/1背包问题，使用贪心法，并不一定能求得最优解，背包问题，使用贪心法，并不一定能求得最优解，因此，贪心法不能用来求解因此，贪心法不能用来求解0/1背包问题背包问题例例，n3，M=25，P(32，24，15)，W(16，15，10).P/W=(2,1.6,1.5)X=(0)p=32,CU=M-W(0)=9 不能放下任何物品，显然不能放下任何物品，显然X=(0)X=(0)不是最优解。不是最优解。最优解是最优解是(1,2)(1,2)，利润为，利润为3939。6.3 6.3 背包问题背包问题第20页，本讲稿共48页6.3 6.3 带有限期的作业排序带有限期的作业排序 在一单机无其他资源约束的处理系统中，运行在一单机无其他资源约束的处理系统中，运行n个作业，假设每个作个作业，假设每个作业运行业运行1个单位时间，且每个作业个单位时间，且每个作业i都都有一个截止期限有一个截止期限di0(它是整数它是整数)，若作业若作业i能能在它的期限截止前被完成，则可获得在它的期限截止前被完成，则可获得pi0的效益。要求找到作的效益。要求找到作业的子集业的子集X及及X的一个排列的一个排列，使得按，使得按调度作业运行，调度作业运行，X中的作业都中的作业都能如期完成，且获收益最大。能如期完成，且获收益最大。可行解：可行解：子集子集X中的作业都能如期完成，则中的作业都能如期完成，则X为可行解。为可行解。可行解的收益：可行解的收益：可行解可行解X中所有中所有作业的收益之和，即作业的收益之和，即 。最优解：最优解：具有最大收益的可行解就是最优解。具有最大收益的可行解就是最优解。6.3.1 问题描述问题描述 第21页，本讲稿共48页例6.2n=4,(p0,p1,p2,p3)(100,10,15,20)、(d0,d1,d2,d3)=(2,1,2,1)可行解和它们的效益值如下：可行解和它们的效益值如下：可行解可行解 处理顺序处理顺序 效益值效益值 (0)1 100 (1)1 10 (2)1 15(3)1 20(0，1)1，0 110(0，2)0，2或或2，0 115(0，3)3，0 120(1，2)1，2 25解解是最优的是最优的,所允许的处理次序是所允许的处理次序是:先处理作业先处理作业3,3,再处理作业再处理作业0.0.306.3 6.3 带有限期的作业排序带有限期的作业排序第22页，本讲稿共48页6.3.2 贪心法求解贪心法求解 (1),把把目标函数目标函数 作为量度作为量度.使用这一量度使用这一量度,下一个要计入的作业将是使得在满足所产生的下一个要计入的作业将是使得在满足所产生的X是是一个可行解的限制条件下让一个可行解的限制条件下让 得到最大增加的作业得到最大增加的作业.(2),按按pi 的非增次序来考虑这些作业的非增次序来考虑这些作业;如例如例6.26.2，按，按pi 的非增次序对作业进行排序的非增次序对作业进行排序（0 0，3 3，2 2，1 1）开始时开始时:X，X0，p0=100 作业0有最大效益 X0，3 p0+p3=120 作业3有第二大效益 作业2,1都被舍弃6.3 6.3 带有限期的作业排序带有限期的作业排序第23页，本讲稿共48页算法算法6.3 6.3 带时限作业排序算法带时限作业排序算法void GreedyJob(int*d，int*X，n)/作业按p0p1pn-1的次序输入，它们的期限值d(i)1，0in-1，n1。X是在它们的截止期限前完成的作业的集合/X0 for(int i=1;in;i+)if(Xi的所有作业都能在它们的截止期限前完成的所有作业都能在它们的截止期限前完成)X=X i6.3 6.3 带有限期的作业排序带有限期的作业排序思考思考:1 1，该算法能否得到最优解？，该算法能否得到最优解？2 2，如何变为有效的算法？，如何变为有效的算法？6.3.2 贪心法求解贪心法求解 第24页，本讲稿共48页定理定理6.2 6.2 算法算法6.36.3所描述的贪心方法对于作业排序问题总是得到一所描述的贪心方法对于作业排序问题总是得到一个最优解。个最优解。证明证明:设设X=(x0,x1,xk)是某个带时限作业排序问题实例的贪心法求得的解，是某个带时限作业排序问题实例的贪心法求得的解，若若X不是最优解，假设另有不是最优解，假设另有Y=(y0,y1,yr)是最优解是最优解.(1)假设假设XY,必有必有 且且 若若 ，则，则Y不是可行解；否则，不是可行解；否则，Y是可行解，那么贪心算法会将属于是可行解，那么贪心算法会将属于Y但不属于但不属于X的其他作业继续加入的其他作业继续加入X。若若 ，则，则Y不是最优解；不是最优解；(2)存在排列存在排列、，使，使X、Y可行可行6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.3 算法正确性算法正确性-(1)该算法能否找到最优解该算法能否找到最优解?第25页，本讲稿共48页(3)将将，中的相同作业移到相同位置。中的相同作业移到相同位置。设设x是既属于是既属于X又属于又属于Y的一个作业的一个作业;又设又设x在在中在中在t t到到t+1t+1时刻被调度时刻被调度,而在而在中中则在则在t到到t+1时刻被调度时刻被调度.可以调换可以调换 或或中的作业中的作业,使使x在在和和中中都在同一时刻被安都在同一时刻被安排排.如果如果tt，交换，交换中的中的x与与z;重复使用，可使重复使用，可使和和中都有的作业在相同的时刻被安排。中都有的作业在相同的时刻被安排。6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.3 算法正确性算法正确性-(1)该算法能否找到最优解该算法能否找到最优解?第26页，本讲稿共48页(4)对于对于和和中的不同作业，用中的不同作业，用中的相同位置的作业替换中的相同位置的作业替换中的中的作业。作业。设设 ，并且作业并且作业a a是使得是使得 的一个收益最的一个收益最大的作业，那么，对于任意作业大的作业，那么，对于任意作业b，都有，都有papb。否则作业。否则作业b被程序被程序6-3加入加入X中。假定中。假定b是其中一个作业，它在是其中一个作业，它在中的位置与中的位置与a a在在中的位置相同，用中的位置相同，用a a取代取代序序列中的列中的b，得到一个新序列得到一个新序列Y，显然，显然Y的效益值不小于的效益值不小于Y的效益值，并且的效益值，并且Y比比Y少一个与少一个与X不同的作业。不同的作业。重复使用上述的转换，将使重复使用上述的转换，将使Y能在不减效益值的情况下转换成能在不减效益值的情况下转换成X，因此，因此X也必定也必定是最优解。证毕。是最优解。证毕。tabpapb6.3 6.3 带有限期的作业排序带有限期的作业排序第27页，本讲稿共48页6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.4 可行性判定可行性判定-(2)如何变为有效算法如何变为有效算法?(1)(1)检查某种排列检查某种排列a a是否可行是否可行?只需检查作业只需检查作业aj是否满足是否满足daj=j+1 每个作业执行一个单位时间每个作业执行一个单位时间 排列位置为排列位置为j j的作业的作业aj应在应在j+1j+1时刻执行完毕时刻执行完毕(2)(2)判断判断X X子集是否可行子集是否可行?只需判断它的一个只需判断它的一个特殊排列特殊排列是否可行即可是否可行即可;这个特殊的排列就是这个特殊的排列就是X中作业按时限的非降次序的排列中作业按时限的非降次序的排列 算法算法6-36-3的核心步骤是的核心步骤是:判定判定集合集合Xi中的作业是否能在截止期限前中的作业是否能在截止期限前完成完成,这一操作步骤也就是这一操作步骤也就是所谓的可行性判定所谓的可行性判定.某一作业子集X是否是可行解，只需找到一种X的排列a,如果X中的作业能按a的次序执行而不超期，则X为可行解.第28页，本讲稿共48页6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.4 可行性判定可行性判定-(2)如何变为有效算法如何变为有效算法?定理定理6-36-3 X=(x0,x1,xk)是是k个作业的集合个作业的集合,a=(a0,a1,a2ak)是是X的一种特的一种特定排列定排列,它使得它使得da0=da1”如果如果X是可行解，则必存在是可行解，则必存在X的至少一种排列使得的至少一种排列使得X中作业可以按该排列执中作业可以按该排列执行而不会有超期，设行而不会有超期，设=(0,1,k),是这样的排列是这样的排列.令令i是使得是使得ii的最小下标，那么作业的最小下标，那么作业i的时限必然小于的时限必然小于i的时限的时限,由于由于和和是是X中作业的两种不同的排列中作业的两种不同的排列,所以所以中必定也包含作业中必定也包含作业i,很显然很显然,i在在中的位置比它在中的位置比它在中的位置靠后中的位置靠后.将将中的中的i与与i交换位置交换位置,不会引起作业超期不会引起作业超期.重复以上过程重复以上过程,最终将最终将变换成变换成,这就是说这就是说,按按次序调度作业不会出现次序调度作业不会出现超期超期,因此因此是可行的调度方案是可行的调度方案第29页，本讲稿共48页 带时限的且每个作业运行单位时间的作业排序过程带时限的且每个作业运行单位时间的作业排序过程:(1),按收益非增次序对作业排序按收益非增次序对作业排序:p0p1pn-1;(2),按作业收益从大到小考察作业按作业收益从大到小考察作业;初始时初始时,x0=0,即即X=x0;现在处理作业现在处理作业j,假设已处理了假设已处理了I-1个作业个作业,其中有其中有k+1个作业已计入部分解向个作业已计入部分解向量量X=x0,x1xk之中之中,且有且有dx0dx1dxk。部分解可行部分解可行 dxii+1(0ik)为了判断为了判断XUj是否可行是否可行,只需看能否找出按期限的非降次序插入作业只需看能否找出按期限的非降次序插入作业j的适的适当位置当位置r,使得作业使得作业j在此处插入后有在此处插入后有dXrr+1,0rk.6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.5 作业排序算法作业排序算法 kj第30页，本讲稿共48页(3)判断判断j是否允许添加到部分解向量是否允许添加到部分解向量X中中将作业将作业j按时限的非减次序插入向量按时限的非减次序插入向量X=x0,x1xk中的某个位置，使中的某个位置，使得作业得作业j插入后，由插入后，由k+2个分量组成的部分解向量仍按时限的非减次序排列个分量组成的部分解向量仍按时限的非减次序排列 假设假设j被插入于下标被插入于下标r+1处处,为了在为了在r+1处插入处插入j作业，作业，xr+1xk在向量中在向量中的位置都要依次后移一位，形成一个新的部分解向量的位置都要依次后移一位，形成一个新的部分解向量.为了保证在添加作业为了保证在添加作业j后的作业子集仍构成可行解，必须满足后的作业子集仍构成可行解，必须满足:a,dxjj+1(r+1jk)b,djr+1;6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.5 作业排序算法作业排序算法 第31页，本讲稿共48页【程序程序6-4】带时限的作业排序程序带时限的作业排序程序 int JS(int*d,int*x,int n)/设设p0p1pn 1 int k=0;x0=0;for(int j=1;j=0&dxrdj&dxrr+1)r-;if(r0|dxrr+1)for(int i=k;i=r+1;i-)xi+1=xi;xr+1=j;k+;return k;6.3 6.3 带有限期的作业排序带有限期的作业排序6.3.5 作业排序算法作业排序算法 n-1 /O(n)k+1k-r 每次迭代的总时间为每次迭代的总时间为O(k),若若s是是k的终的终值值,即即s是最后所得解的作业数是最后所得解的作业数.则则JS所需所需的总时间是的总时间是O(sn).由于由于s=0&dxr=2dj=1&dxrr+1 r=r-1=-1 r=-1r+1 可以后移,且j可以插入r+1处103.j=2,r=k=1,dxr=2=dj且且dxr=r+1 不可以后移；不可以后移；又又dj=r+1 j不可以插入。不可以插入。4.j=3,r=k=1,dxr=2dj=1但但dxr=2=r+1 不可以后移；又不可以后移；又 dj=1r+1 j不可以插入。不可以插入。X=1,06.3 6.3 带有限期的作业排序带有限期的作业排序6.3.5 作业排序算法作业排序算法 第33页，本讲稿共48页n改进的可行解判定方法的主要思想是改进的可行解判定方法的主要思想是:令令b=minn,max di|0in-1 b为可行的作业调度方案所需的最大时间为可行的作业调度方案所需的最大时间,b不会超过作业的最大时限不会超过作业的最大时限,也不也不会超过作业的总数会超过作业的总数n b是可行作业调度方案所需的最大时间是可行作业调度方案所需的最大时间;可将可将b分成分成b个时间片，每个时间片一个单位个时间片，每个时间片一个单位;为了实现算法方便，引入了虚拟时间片为了实现算法方便，引入了虚拟时间片-1,0,它不同用于时间分配它不同用于时间分配n作业排序过程作业排序过程:(1),设作业已按收益的非增次序排列设作业已按收益的非增次序排列 (2),作业作业i的时限是的时限是di,为它分配的时间片是为它分配的时间片是r-1,r,其中，其中，r是使是使0r,就可将作业就可将作业I在位置在位置r+1处插入处插入,从而得到一个按期限的从而得到一个按期限的非降次序排列的含有非降次序排列的含有k+1个作业的可行解。个作业的可行解。以上过程可反复进行到对第以上过程可反复进行到对第n个作业处理完毕个作业处理完毕,所得到的贪心解是一个最所得到的贪心解是一个最优解。优解。这一处理过程可用算法这一处理过程可用算法6.3来描述来描述.算法中引进了一个虚构的作业算法中引进了一个虚构的作业0,它放在它放在X(0),且且D(X(0)0.引入这一虚构作业是为了便于将作业插入位置引入这一虚构作业是为了便于将作业插入位置1。6.3 6.3 带有限期的作业排序带有限期的作业排序第40页，本讲稿共48页1.1.贪心选择性质贪心选择性质n所谓所谓贪心选择性质贪心选择性质是指所求问题的整体最优解可以通过一系列局是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。个基本要素，也是贪心算法与动态规划算法的主要区别。n动态规划算法通常以动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算的方式解各子问题，而贪心算法则通常以法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。n对于一个具体问题，要确定它是否具有贪心选择性质，必须证明对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。每一步所作的贪心选择最终导致问题的整体最优解。6.2 6.2 贪心法的基本要素贪心法的基本要素第41页，本讲稿共48页n当一个问题的最优解包含其子问题的最优解时当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子称此问题具有最优子结构性质结构性质.问题的最优子结构性质是该问题可用动态规划算法或贪心问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。算法求解的关键特征。2.2.最优子结构性质最优子结构性质6.2 6.2 贪心法的基本要素贪心法的基本要素3.3.贪心法与动态规划法的异同贪心法与动态规划法的异同n共同点共同点:都可用来求解最优化问题都可用来求解最优化问题;且要求问题具有最优子结构且要求问题具有最优子结构性质性质.n差异差异:贪心法是自顶向下的决策方法贪心法是自顶向下的决策方法,而动态规划法使用自底向而动态规划法使用自底向上的决策方法上的决策方法.对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是是否能用动态规划算法求解的问题也能用贪心算法求解否能用动态规划算法求解的问题也能用贪心算法求解?当具有最优子结构特性的当具有最优子结构特性的最优化问题找不到最优量度标准时，可以选用动态规划方法最优化问题找不到最优量度标准时，可以选用动态规划方法.第42页，本讲稿共48页定理定理6.2 6.2 算法算法6.36.3所描述的贪心方法对于作业排序问题总是得到一所描述的贪心方法对于作业排序问题总是得到一个最优解。个最优解。证明:设X=(x0,x1,xk)是某个带时限作业排序问题实例的贪心法求得的解，若X不是最优解，假设另有Y=(y0,y1,yr)是最优解.(1)假设XY,必有 且(2)存在排列a,b使X,Y可行(3)将a,b中的相同作业移到相同位置(4)对于不同作业用X中的相同位置上的作业替换Y的作业 假定IX,因此,至少存在着这样的两个作业a和b,使 且 ,bY且 .由贪心方法可以得出,对于在Y中又不在X中的所有作业b,都有papb.这是因为若pb pa,则贪心方法会先于作业a考虑作业b并且把b计入到X中去.tabpapb6.3 6.3 带有限期的作业排序带有限期的作业排序第43页，本讲稿共48页证明:设X=(x0,x1xk)是某个带时限作业排序问题实例的贪心算法求得的解，如果X不是最优解，另有Y=(y0,y1,yr)是最优解.设XY,则必有 因为若 则Y不是可行解;否则，若Y是可行解，那么贪心算法定会将属于Y但不属于X的其他作业继续加入X,若 则不是最优解。因为和是问题的两个可行解，设 分别是X和Y的可行的作业排列,也就是说,按 的次序调度作业执行，X和Y中的作业都不会超期.将将 中相同的作业移到相同的位置中相同的作业移到相同的位置,并且不影响两个排列的可行解性质.若存在作业x,使得 ,x在序列 中的位置先于在 中的位置可将a 序列中的x和z交换位置，这样不会引起任何作业超期.定理定理6.2 6.2 程序程序6-36-3的贪心方法对于作业排序问题总是得到一个最优解。的贪心方法对于作业排序问题总是得到一个最优解。6.3.36.3.3算法正确性算法正确性-(1)-(1)该算法能否找到最优解该算法能否找到最优解?y xt x ztx与与z交换前交换前y zt x xtx与与z交换后交换后第44页，本讲稿共48页因为 ,则必存在两个作业a和b,使得 假定作业a是使得 的一个收益最大的作业，那么，由贪心法可知，对任意作业b,都有papb,否则，作业b将被程序6-3加入X中，假定b是其中一作业，它在 中的位置与a在 中的位置相同，现用a取代序列 中的b,得到一个新序列，很显然 新序列仍然是可行的且新序列的收益不低于Y,可以重复这样的替换,最终要么将Y转换成X,要么，证明Y不是可行解.定理定理6.2 6.2 程序程序6-36-3的贪心方法对于作业排序问题总是得到一个最优解。的贪心方法对于作业排序问题总是得到一个最优解。abpapbtaapapb用X中的作业a替换Y中的作业b,得到新的作业集X。6.3.36.3.3算法正确性算法正确性-(1)-(1)该算法能否找到最优解该算法能否找到最优解?第45页，本讲稿共48页 下面对程序6-3的if语句进一步细化。if (Xi的所有作业都能在它们的截止期限前完成)XXi (1)检验X作业子集是否可行?检验X的所有可能的排列，假定X中有k个作业，这就需要检查k!个排列。事实上，对于X的可行性可以通过只检验X中作业的一种特殊的排列来确定，这个排列是按期限的非降次序来完成的。即将X中的K个作业按di1di2dik 排列。(2)判定一个排列a是否可行?检查检查a a中的每个作业中的每个作业a aj j是否满足是否满足d dajaj=j+1=j+1 ki6.3.46.3.4可行性判定可行性判定-(2)-(2)如何变为有效算法如何变为有效算法?第46页，本讲稿共48页定理6-3,X=(x0,x1,xk)是K+1个作业的集合，a=(a0,a1,ak)是X的一个特定的排列，它使得da0da1dak,其中,daj是作业aj的时限.X是一个可行解，当且仅当X中的作业能够按a次序调度而不会有作业超期.(1)(1)检验检验X X作业子集是否可行作业子集是否可行?证明证明(1)”如果如果X中作业能够按照中作业能够按照a次序调度而不会有作业超期，则次序调度而不会有作业超期，则X是可行是可行解解(2)”-”如果如果X是可行解，则必存在是可行解，则必存在X的至少一种排列使得的至少一种排列使得X中作业可以按该排中作业可以按该排列执行而不会有超期，设列执行而不会有超期，设=(0,1,k),!=是这样的排列是这样的排列.令令i是最小下标，使得是最小下标，使得i!=i,那么作业那么作业i的时限必然小于的时限必然小于i的时限，由的时限，由于于和和是是X中作业的两种不同的排列，所以中作业的两种不同的排列，所以中必定也包含作业中必定也包含作业i,很显很显然，然，i在在中的位置比它在中的位置比它在中的位置靠后中的位置靠后.将将中的中的i与与i交换位置，不会引起作业超期交换位置，不会引起作业超期.重复以上过程，最终将重复以上过程，最终将变换成变换成,这就是说，按这就是说，按次序调度作业不会次序调度作业不会出现超期，因此出现超期，因此是可行的调度方案是可行的调度方案第47页，本讲稿共48页6.3.56.3.5作业排序的贪心算法作业排序的贪心算法带时限且每个作业运行单位时间的作业排序过程带时限且每个作业运行单位时间的作业排序过程:(1)(1)按收益非增次序对作业排序按收益非增次序对作业排序:p0=p1=pn-1(2)(2)依作业收益从大到小考察作业依作业收益从大到小考察作业 初始时初始时,X0=0,即即X=X0 一般情况下一般情况下,假设考察第假设考察第j个作业个作业,此时此时,X=X0,X1,XK且且dX0=dX1=.=i+1(0=ij+1 r+1=jr+1第48页，本讲稿共48页