第六章贪心法.ppt

第六章贪心法,贪心法的学习提纲,一般方法适合求解的问题基本思想(求解问题的过程)算法控制流程算法的正确性证明应用举例背包问题带时限的作业排序问题,贪心算法的直观含义,例1.如：找硬币0.15元，要求硬币数最少。找硬币方法就是一种贪心算法.（1）面值；5分、2分、1分：（2）面值：11分、5分、1分：从此例可以看出：1，贪心法未必总能求得问题的最优解；2，贪心算法总是作出在当前看来是最好的选择.也就是说贪心算法不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题，最小生成树问题等。而且,在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解！,3个5分(最优),1个11分4个1分(次优),6.1一般方法,贪心方法适合的问题是最优化问题。最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。,目标函数：,约束条件（函数）：,其中：,可行解：,如找硬币问题可描述如下：,最优化问题的解可表示成一个n元组X=（x1,x2xn），其中每个分量取自某个值集S，所有允许的n-元组组成一个侯选解集。,6.1一般方法,贪心方法适合的问题是最优化问题。最优化问题：有n个输入，而它的解就由这n个输入的满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的，为了衡量可行解的好坏，问题还给出某个值函数，称为目标函数，使目标函数取极值(极大或极小)的可行解，称为最优解。,最优化问题的解是一个n元组,贪心法是通过分步决策的方法来解决问题的。贪心法在求解问题的每一步上作出某种决策，产生n-元组的一个分量，贪心法要求根据题意，选定一种最优量度标准，作为选择当前分量的依据，这种在贪心法每一步上用做决策依据的选择准则被称为最优量度标准（贪心准则，也称贪心选择性质）。,6.1一般方法,贪心法的基本思想:是依据题意选取一种量度标准，然后按照这种量度标准对这n个输入进行排序，并按序一次输入一个量，作为n-元组的一个分量，如果这个输入量的加入不满足约束条件,则不把此输入加入到部分解向量中.,贪心法求解问题的过程:选取最优量度标准依最优量度标准对n个输入排序初始状态下,解向量solution=中;按序一次取一个输入量，作为n-元组的一个分量，若加入该分量满足给定的约束条件，则加入，否则，不加入，继续检测下一个分量.,贪心方法的抽象化控制,算法6.1贪心法的控制流程SolutionTypeGreedy(STypea，intn)SolutionTypesolutions=/将解向量solution初始化为空for(inti=0;i0.如果这些物品重量的和大于M,要求所有选中要装入背包的物品总重量不得超过M,而装入背包物品获得的总效益最大.即,0xil，pi0，wi0，0in-1,满足约束条件的任一集合(x0，xn-1)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。,背包问题描述：,约束条件：,例6.1n3，M=20，P(25，24，15)，W=(18，15，10)假设物品可分，故有可行解无数个，其中的四个可行解是：(x0，x1，x2)wixipixi(1/2，1/3，1/4)16.524.25(1，2/15，0)2028.2(0，2/3，1)2031(0，1，1/2)2031.5在这四个可行解中，第个解的效益值最大。但这个解是否是背包问题的最优解，尚无法确定，但有一点是可以肯定的，即对于一般背包问题，其最优解显然必须装满背包。,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)选重量作为量度,使背包容量尽可能慢地被消耗.,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;解为:(x0,x1,x2)=(0,1,1/2)收益:24+15/2=31.5,可见，可以pi/wi作为背包问题的最优量度标准.,最优解,算法6.2以pi/wi为最优量度标准的背包问题的贪心算法voidGreedyKnapsack(float*p,float*w,floatM,intn,float*x)/前置条件：wi已按pi/wi的非增次序排列floatu=M;/u为背包剩余载重量，初始时为mfor(inti=0;iu)break;xi=1.0;u=uwi;if(ipixi。不失一般性，可以假定wiyi=M。（2）设k是使得ykxk的最小下标。可以推得ykj分别得证明：,若kM，从而ykj，(1,1,1,.,1,xj,0,0),jK,反证法：,所以,必有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背包问题，使用贪心法，并不一定能求得最优解，因此，贪心法不能用来求解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中的作业都能如期完成，且获收益最大。可行解：子集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)1100(1)110(2)115(3)120(0，1)1，0110(0，2)0，2或2，0115(0，3)3，0120(1，2)1，225解是最优的,所允许的处理次序是:先处理作业3,再处理作业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，3p0+p3=120作业3有第二大效益作业2,1都被舍弃,6.3带有限期的作业排序,算法6.3带时限作业排序算法,voidGreedyJob(int*d，int*X，n)/作业按p0p1pn-1的次序输入，它们的期限值d(i)1，0in-1，n1。X是在它们的截止期限前完成的作业的集合/X0for(inti=1;i=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-3X=(x0,x1,xk)是k个作业的集合,a=(a0,a1,a2ak)是X的一种特定排列,它使得da0j+1(r+1jk)b,djr+1;,6.3带有限期的作业排序,6.3.5作业排序算法,【程序6-4】带时限的作业排序程序intJS(int*d,int*x,intn)/设p0p1pn1intk=0;x0=0;for(intj=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=0可将b分成b个时间片，每个时间片一个单位;为了实现算法方便，引入了虚拟时间片-1,0,它不同用于时间分配作业排序过程:(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带有限期的作业排序,1.贪心选择性质,所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。,6.2贪心法的基本要素,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质.问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,2.最优子结构性质,6.2贪心法的基本要素,3.贪心法与动态规划法的异同,共同点:都可用来求解最优化问题;且要求问题具有最优子结构性质.差异:贪心法是自顶向下的决策方法,而动态规划法使用自底向上的决策方法.对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解?当具有最优子结构特性的最优化问题找不到最优量度标准时，可以选用动态规划方法.,定理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中的相同位置上的作业替换Y的作业假定IX,因此,至少存在着这样的两个作业a和b,使且,bY且.由贪心方法可以得出,对于在Y中又不在X中的所有作业b,都有papb.这是因为若pbpa,则贪心方法会先于作业a考虑作业b并且把b计入到X中去.,t,a,b,papb,6.3带有限期的作业排序,证明:设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-3的贪心方法对于作业排序问题总是得到一个最优解。,6.3.3算法正确性-(1)该算法能否找到最优解?,因为,则必存在两个作业a和b,使得假定作业a是使得的一个收益最大的作业，那么，由贪心法可知，对任意作业b,都有papb,否则，作业b将被程序6-3加入X中，假定b是其中一作业，它在中的位置与a在中的位置相同，现用a取代序列中的b,得到一个新序列，很显然新序列仍然是可行的且新序列的收益不低于Y,可以重复这样的替换,最终要么将Y转换成X,要么，证明Y不是可行解.,定理6.2程序6-3的贪心方法对于作业排序问题总是得到一个最优解。,用X中的作业a替换Y中的作业b,得到新的作业集X。,6.3.3算法正确性-(1)该算法能否找到最优解?,下面对程序6-3的if语句进一步细化。if(Xi的所有作业都能在它们的截止期限前完成)XXi(1)检验X作业子集是否可行?检验X的所有可能的排列，假定X中有k个作业，这就需要检查k!个排列。事实上，对于X