第六章贪心法.ppt

1、第六章 贪心法,贪心法的学习提纲,一般方法 适合求解的问题 基本思想(求解问题的过程 ) 算法控制流程 算法的正确性证明 应用举例 背包问题 带时限的作业排序问题,贪心算法的直观含义,例1.如：找硬币0.15元，要求硬币数最少。找硬币方法就是一种贪心算法. （1）面值；5分、2分、1分： （2）面值：11分、5分、1分： 从此例可以看出： 1，贪心法未必总能求得问题的最优解； 2，贪心算法总是作出在当前看来是最好的选择.也就是说贪心算法不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。 虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它都能产生最优解。

2、如单源最短路径问题，最小生成树问题等。 而且,在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解！,3个5分 (最优),1个11分4个1分 (次优),6.1 一般方法,贪心方法适合的问题是最优化问题。 最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。,目标函数：,约束条件（函数）：,其中：,可行解：,如找硬币问题可描述如下：,最优化问题的解

3、可表示成一个n元组X=（x1,x2xn），其中每个分量取自某个值集S，所有允许的n-元组组成一个侯选解集。,6.1 一般方法,贪心方法适合的问题是最优化问题。 最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。,最优化问题的解是一个n元组,贪心法是通过分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策，产生n-元组的一个分量，贪心法要求根据题意，选定一种最优

4、量度标准，作为选择当前分量的依据，这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准（贪心准则，也称贪心选择性质）。,6.1 一般方法,贪心法的基本思想: 是依据题意选取一种量度标准，然后按照这种量度标准对这n个输入进行排序，并按序一次输入一个量，作为n-元组的一个分量，如果这个输入量的加入不满足约束条件,则不把此输入加入到部分解向量中.,贪心法求解问题的过程: 选取最优量度标准 依最优量度标准对n个输入排序 初始状态下,解向量solution=中; 按序一次取一个输入量，作为n-元组的一个分量，若加入该分量满足给定的约束条件，则加入，否则，不加入，继续检测下一个分量.,贪心方法的抽

5、象化控制,算法6.1 贪心法的控制流程 SolutionType Greedy(SType a，int n) SolutionType solutions= /将解向量solution初始化为空 for(int i=0;in;i+) SType x=Select(a); if (Feasiable(solution,x) solutions=UNION(solution,x); return solution; ,从算法6.1可看出，一旦能选择出某个问题的最优量度标准，那么用贪心方法求解这个问题则特别简单有效。,n个输入按某种量度标准排序,按序一次选择一个输入量。,满足约束条件，加入解,解,不

6、满足约束条件，扬弃,.,对于一个给定的问题，往往可能有好几种量度标准。用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优。 选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。,6.1 一般方法,贪心法小结: 适合求解的问题:解为n-元组的最优化问题; 贪心法是分步决策,每一步决策产生n-元组的一个分量 贪心法并不是从整体上考虑最佳，而是做当前看来是最佳的选择，这种选择依赖于以前的选择，但不依赖于以后的选择和子问题,故它的特征是自顶向下一步一步地做出贪心决策. 自顶向下:是以迭代的方式作出相继的贪心选择,每一次贪心选择就将所求问题简化为规模更小

7、的子问题.,1.最优量度标准,所谓贪心法的最优量度标准,是指可以根据该量度标准，实行多步决策进行求解，虽然在该量度意义下所做的这些选择都是局部最优的，但最终得到的解却是全局最优的。 因此，选择最优量度标准是使用贪心法求解问题的核心问题.,6.2 贪心法的基本要素,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质.问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,2.最优子结构性质,6.3 背包问题,0-1背包问题： 给定n种物品和一个背包.物品i的重量是Wi,其价值为pi,背包的容量为C.应如何选择装入背包的物品,使得装入背包中物品的总价值最大？ 在选

8、择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包. 背包问题: 与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1in。 这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心法求解,而0-1背包问题却不能用贪心法求解。,6.3 背包问题,已知有n种物品和一个可容纳M重量的背包,每种物品i的重量为wi.假定将物品i的一部分xi放入背包就会得到pixi的效益,这里，0 xi1，pi0.如果这些物品重量的和大于M,要求所有选中要装入背包的物品总重量不得超过M,而装入背包物品获得的总效益最大.即,0 xil，pi0，

9、wi0，0in-1,满足约束条件的任一集合(x0，xn-1)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。,背包问题描述：,约束条件：,例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 在这四个可行解中，第个解的效益值最大。但这个解是否是背包问题的最优解，尚无法确定，但有一点是可以肯定的，

10、即对于一般背包问题，其最优解显然必须装满背包。,6.3 背包问题,贪心法求解背包问题 选择量度标准 计算在此量度标准下的”最优解” (1)选目标函数作为量度标准, 即”效益”优先,使每装入一件物品就使背包获得最大可能的效益值增量. 按物品收益从大到小排序0,1,2 解为: (x0,x1,x2)=(1, 2/15, 0) 收益: 25+24*2/15=28.2,6.3 背包问题,非最优解,原因:只考虑当前收益最大,而背包可用容量消耗过快.,M=20, P(25, 24, 15) W= (18，15，10),贪心法求解背包问题 选择量度标准 计算在此量度标准下的”最优解” (2)选重量作为量度 ,

11、使背包容量尽可能慢地被消耗.,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),贪心法求解背包问题 选择量度标准 计算在此量度标准下的”最优解” (3)选利润/重量为量度 使每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。,6.3 背包问题,M=20, P(25, 24, 15) W= (18，15，10),按物品的pi/wi重量从大到小排序:1,2,0; 解为:

12、 (x0,x1,x2)=(0, 1, 1/2) 收益: 24+15/2=31.5,可见，可以pi/wi 作为背包问题的最优量度标准.,最优解,算法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; iu) break; xi=1.0; u=uwi; if (in) xi=u/wi; ,6.3 背包问题,（1）由此算法所得解的形式为:

13、(1,1,1,.,1,xj,0,0) （2）算法的正确性： 贪心法得到的解是否是最优解需要证明,定理6.1 如果p0/w0p1w1pn-1wn-1，则算法GreedyKnapsack对于给定的背包问题实例生成一个最优解。,证明:设X=(x0，xn-1)是GreedyKnapsack所生成的解.设j是使x(i)1的最小下标。由算法可知，有：(1,.,1, xj，0,0),j,（1）假设X不是最优解，另有最优解为Y=(y0，yn-1)，则定有piyipixi。不失一般性，可以假定wiyi=M。 （2）设k是使得ykxk的最小下标。可以推得ykj分别得证明：,若kj， (1,1,1,.,1, xj

14、,0,0),K j,因为 ykxk ，从而ykxk。,若kj， (1,1,1,.,1, xj ,0,0),K=j,若ykxk，显然有wiyiM，从而ykxk。,若kj， (1,1,1,.,1, xj ,0,0),j K,反证法：,所以,必有ykxk,若ykxk ，有wiyiM，是不可能的。,(3) 把yk增加到xk, 那末必须从(yk+1，yn-1)中减去同样多的量，使得所用的总容量仍是M。这导致一个新的解Z=( z0，zn-1)，其中， zi=xi，0ik，并且,因此，对于Z有,变换,Z不比Y差,重复上面的讨论,把Y转换成X,从而证明了X也是最优解.证毕。,对于0/1背包问题，使用贪心法，并

15、不一定能求得最优解，因此，贪心法不能用来求解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)不是最优解。 最优解是(1,2)，利润为39。,6.3 背包问题,6.3 带有限期的作业排序,在一单机无其他资源约束的处理系统中，运行n个作业，假设每个作业运行1个单位时间，且每个作业i都有一个截止期限di0(它是整数)，若作业i能在它的期限截止前被完成，则可获得pi0的效益。要求找到作业的子集X及X的一个排列，使得按调度作业运行，X中的作业都能如期完成

16、，且获收益最大。 可行解：子集X中的作业都能如期完成，则X为可行解。 可行解的收益：可行解X中所有作业的收益之和，即 。 最优解：具有最大收益的可行解就是最优解。,6.3.1 问题描述,例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,

17、再处理作业0.,3,0,6.3 带有限期的作业排序,6.3.2 贪心法求解,(1),把目标函数 作为量度. 使用这一量度,下一个要计入的作业将是使得在满足所产生的X是一个可行解的限制条件下让 得到最大增加的作业. (2),按pi 的非增次序来考虑这些作业; 如例6.2，按pi 的非增次序对作业进行排序（0，3，2，1） 开始时: X， ，,X0， p0=100 作业0有最大效益 X0，3 p0+p3=120 作业3有第二大效益 作业2,1都被舍弃,6.3 带有限期的作业排序,算法6.3 带时限作业排序算法,void GreedyJob(int *d，int *X，n) /作业按p0p1pn-1

18、的次序输入，它们的期限值d(i)1，0in-1，n1。X是在它们的截止期限前完成的作业的集合/ X0 for (int i=1;in;i+) if( Xi的所有作业都能在它们的截止期限前完成) X =X i ,6.3 带有限期的作业排序,思考:1，该算法能否得到最优解？ 2，如何变为有效的算法？,6.3.2 贪心法求解,定理6.2 算法6.3所描述的贪心方法对于作业排序问题总是得到一个最优解。,证明:设X=(x0,x1,xk)是某个带时限作业排序问题实例的贪心法求得的解，若X不是最优解，假设另有Y =(y0,y1,yr)是最优解. (1)假设XY,必有 且 若 ，则Y不是可行解；否则，Y是可行

19、解，那么贪心算法会将属于Y但不属于X的其他作业继续加入X。 若 ，则Y不是最优解； (2)存在排列、，使X、Y可行,6.3 带有限期的作业排序,6.3.3 算法正确性-(1)该算法能否找到最优解?,(3)将，中的相同作业移到相同位置。 设x是既属于X又属于Y的一个作业;又设x在中在t到t+1时刻被调度,而在中则在t到t+1时刻被调度.可以调换 或中的作业,使x在和中都在同一时刻被安排.如果tt，交换中的x与y;,t,z,x,t,x,t,y,t,x,y,t,z,t,x,如果tt，交换中的x与z;重复使用，可使和中都有的作业在相同的时刻被安排。,6.3 带有限期的作业排序,6.3.3 算法正确性-

20、(1)该算法能否找到最优解?,(4)对于和中的不同作业，用中的相同位置的作业替换中的作业。 设 ，并且作业a是使得 的一个收益最大的作业，那么，对于任意作业b， ，都有papb。否则作业b被程序6-3加入X中。假定b是其中一个作业，它在中的位置与a在中的位置相同，用a取代序列中的b，得到一个新序列Y ，显然Y的效益值不小于Y的效益值，并且Y比Y少一个与X不同的作业。 重复使用上述的转换，将使Y能在不减效益值的情况下转换成X，因此X也必定是最优解。证毕。,t,a,b,papb,6.3 带有限期的作业排序,6.3 带有限期的作业排序,6.3.4 可行性判定-(2)如何变为有效算法?,(1)检查某种

21、排列a是否可行? 只需检查作业aj是否满足daj=j+1 每个作业执行一个单位时间 排列位置为j的作业aj应在j+1时刻执行完毕,(2)判断X子集是否可行? 只需判断它的一个特殊排列是否可行即可; 这个特殊的排列就是X中作业按时限的非降次序的排列,算法6-3的核心步骤是:判定集合Xi中的作业是否能在截止期限前完成,这一操作步骤也就是所谓的可行性判定.,某一作业子集X是否是可行解，只需找到一种X的排列a,如果X中的作业能按a的次序执行而不超期，则X为可行解.,6.3 带有限期的作业排序,6.3.4 可行性判定-(2)如何变为有效算法?,定理6-3 X=(x0,x1,xk)是k个作业的集合,a=(

22、a0,a1,a2ak)是X的一种特定排列,它使得da0=da1=.dak,其中，daj是作业aj的时限.X是一个可行解当且仅当X中的作业能够按a次序调度而不会有作业超期.,证明:(1)”如果X中作业能够按照a次序调度而不会有作业超期, 则X是可行解. (2)”-”如果X是可行解，则必存在X的至少一种排列使得X中作业可以按该排列执行而不会有超期，设=(0,1,k), 是这样的排列. 令i是使得ii的最小下标，那么作业i的时限必然小于i的时限, 由于和是X中作业的两种不同的排列, 所以中必定也包含作业i,很显然, i在中的位置比它在中的位置靠后. 将中的i与i交换位置, 不会引起作业超期. 重复以

23、上过程, 最终将变换成,这就是说,按次序调度作业不会出现超期, 因此是可行的调度方案,带时限的且每个作业运行单位时间的作业排序过程: (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.5 作业排序算法,

24、k,j,(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.5 作业排序算法,【程序6-4】 带时限的作业排序程序 int JS(int *d, int *x, int n) /设p0p1pn1 in

25、t k=0; x0=0; for (int j=1; j=0 ,6.3 带有限期的作业排序,6.3.5 作业排序算法,n-1 /O(n),k+1,k-r,每次迭代的总时间为O(k),若s是k的终值,即s是最后所得解的作业数.则JS所需的总时间是O(sn).由于s=n,因此最坏时间是O(n2)(当di=n-i 0in-1时),所以最坏时间是: O(n2),复杂度分析：对于JS，其复杂度参数有两个：即作业数n和包含在解中的作业数s.,例n=4，P(100，20， 15， 10，)和d=(2,1,2,1),0,1. X0=0,k=0,2. j=1,r=k=0, r=0 可将b分成b个时间片，每个时间

26、片一个单位; 为了实现算法方便，引入了虚拟时间片-1,0,它不同用于时间分配 作业排序过程: (1),设作业已按收益的非增次序排列 (2),作业i的时限是di,为它分配的时间片是r-1,r,其中，r是使0r di的最大整数且r-1,r是空闲的,6.3 带有限期的作业排序,6.3.6 改进的作业排序算法,具体做法是:为收益最大的0作业分配时间片d0-1,d0,为收益次大的作业1分配时间片时，首先考虑时间片d1-1,d1,如果该时间片已分配,再考虑前一时间片d1-2,d1-1,依次向前寻找第一个空闲的时间片分配之,如果d1之前的所有时间片均已分配，则作业1舍弃， 原则:尽可能推迟对作业的处理。,6

27、.3 带有限期的作业排序,6.3.6 改进的作业排序算法,例6-3 n=5 (d0,d1,d2,d3,d4)=(2,2,1,3,3) (p0,p1,p2,p3,p4)=(20,15,10,5,1) 解： b=min5，3=3,1,0,3,贪心法-总结与作业,总结与作业,总结：,（1）适合求解的问题-解为n-元组的最优化问题 问题应该具备的特征是: 具有最优量度标准 具有最优子结构特性 （2）贪心法的特征:自顶向下,多步决策,每次产生n-元组的一个分量,贪心法当前的选择可能依赖于已经做出的选择,但不依赖于尚未作出的选择和子问题 （3）贪心法求解问题的过程： 选择最优量度标准 依最优量度标准对输入

28、排序 依最优量度标准选择输入产生解向量中的一个分量 算法的正确性证明,贪心法-总结与作业,总结与作业,P132： 6-1，6-2,6-3,6-17,作业：,思考：,P133： 6-4,定理6-3提供了一种高效的可行解的判定方法。使得在按最优量度标准，即按作业收益的非增次序选择下一个作业后，可以有效地判定是否可将该作业加入已生成的部分解向量X中，具体判定方法是：对任意一个部分解作业子集X =(x0,x1,xk) ，使X中的作业按期限的非降次序排列，设a=(a0,a1,a2ak) ，da0da1dak 是X的这样的排列,为了判定a是否可行，只需对每个作业aj判断daj=j+1是否成立。作业i能否加

29、入X的充要条件是，作业i能否加入这个序列。,k,i,6.3 带有限期的作业排序,6.3.5 作业排序算法,假设已处理了I-1个作业,其中有k个作业已计人X(0),X(1),X(k)之中,且有D(X(1)D(X(2)D(X(k),现在处理作业i.为了判断XUi是否可行,只需看能否找出按期限的非降次序插入作业i的适当位置r,使得作业i在此处插入后有D(X(r)r,1rk+1.,k,i,r,D(X(r)D(i),作业i应该放在r+1处,D(i)r，作业i可以放在r+1处， 从r+1到k的作业应向后移动。,6.3 带有限期的作业排序,找作业i可能的插入位置可如下进行: 将D(X(k)，D(X(k一1)

30、，D(X(1)逐个与D(i)比较，直到找到位置r,它使得D(X(r)D(i)，只要D(i) r,就可将作业I在位置r+1处插入,从而得到一个按期限的非降次序排列的含有k+1个作业的可行解。 以上过程可反复进行到对第n个作业处理完毕,所得到的贪心解是一个最优解。 这一处理过程可用算法6.3来描述.算法中引进了一个虚构的作业0,它放在X(0),且D(X(0)0.引入这一虚构作业是为了便于将作业插入位置1。,6.3 带有限期的作业排序,1.贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法

31、的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,6.2 贪心法的基本要素,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质.问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,2.最优子结构性质,6.2 贪心法的基本要素,3.贪心法与动态规划法的异同,共同点:都可用来求解最优化问题;且要求问题具有最优子结构性质. 差异:

32、贪心法是自顶向下的决策方法,而动态规划法使用自底向上的决策方法. 对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?当具有最优子结构特性的最优化问题找不到最优量度标准时，可以选用动态规划方法.,定理6.2 算法6.3所描述的贪心方法对于作业排序问题总是得到一个最优解。,证明:设X=(x0,x1,xk)是某个带时限作业排序问题实例的贪心法求得的解，若X不是最优解，假设另有Y =(y0,y1,yr)是最优解. (1)假设XY,必有 且 (2)存在排列a,b使X,Y可行 (3)将a,b中的相同作业移到相同位置 (4)对于不同作业用X中的相

33、同位置上的作业替换Y的作业 假定IX,因此,至少存在着这样的两个作业a和b,使 且 , bY且 .由贪心方法可以得出,对于在Y中又不在X中的所有作业b,都有papb.这是因为若pb pa,则贪心方法会先于作业a考虑作业b并且把b计入到X中去.,t,a,b,papb,6.3 带有限期的作业排序,证明:设X=(x0,x1xk)是某个带时限作业排序问题实例的贪心算法求得的解，如果X不是最优解，另有Y=(y0,y1,yr)是最优解. 设XY,则必有 因为若 则Y不是可行解;否则，若Y是可行解，那么贪心算法定会将属于Y但不属于X的其他作业继续加入X,若 则不是最优解。 因为和是问题的两个可行解，设 分别

34、是X和Y的可行的作业排列,也就是说,按 的次序调度作业执行，X和Y中的作业都不会超期. 将 中相同的作业移到相同的位置,并且不影响两个排列的可行解性质.若存在作业x,使得 ,x在序列 中的位置先于在 中的位置可将a 序列中的x和z交换位置，这样不会引起任何作业超期.,定理6.2 程序6-3的贪心方法对于作业排序问题总是得到一个最优解。,6.3.3算法正确性-(1)该算法能否找到最优解?,因为 ,则必存在两个作业a和b,使得 假定作业a是使得 的一个收益最大的作业，那么，由贪心法可知，对任意作业b, 都有papb,否则，作业b将被程序6-3加入X中，假定b是其中一作业，它在 中的位置与a在 中的位置相同，