算法分析与设计6_贪心法

第6章贪心法ch6.2学习要点：理解贪心算法的概念掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法的一般方法通过应用范例学习贪心设计策略。（1）背包问题;（2）最优归并模式;（3）最小代价生成树;ch6.3章节内容6.1一般方法6.2背包问题6.4最优归并模式6.5最小代价生成树ch6.4可行解——问题给定某些约束条件，满足约束条件的问题解，即称为可行解。最优解——问题给出目标函数衡量可行解的好坏，使目标函数取最大（或最小）值的可行解称为最优解。贪心法求解最优化问题。6.1贪心法的一般方法ch6.5贪心法通过分步决策的方法求解问题，每一步决策产生n-元组解（x0,x1,…,xn-1）的一个分量。贪心法每一步上用作决策依据的选择准则被称为最优量度标准。在选择解分量的过程中，添加新的解分量xk后，形成的部分解（x0,x1,…,xk)不违反可行解约束条件。每一次贪心选择都将所求问题简化为规模更小的子问题。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择，仅依赖以前的选择，但不依赖于以后的选择。对于一个贪心算法，必须证明该算法的每一步上作出的选择，都必然最终导致问题的一个整体最优解。ch6.6贪心算法不能保证对所有问题都得到整体最优解。对许多问题，如：一般背包问题、最佳合并模式问题、单源最短路径问题，最小生成树问题等，贪心算法确实能产生整体最优解。一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。ch6.7能用贪心算法求解的问题一般具有两个性质：贪心选择性质和最优子结构性质。ch6.81、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。ch6.92、最优子结构性质一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。ch6.10程序6-1贪心法算法框架SolutionTypeGreedy(STypea[],intn){SolutionTypesolution=Ø；//初始时，解向量不包含任何分量for(inti=0;in;i++){STypex=Select(a);//问题的解用n元组(x0,x1,...,xn-1)表示//遵循最优度量标准选择一个分量xif(Feasiable(solution,x))//判断加入新分量x后部分解是否可行solution=Union(solution,x);//形成新的部分解}returnsolution;//返回生成的最优解}ch6.11给定n种物品和一个容量为M的背包。物品i的重量是wi，其价值为pi。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?物品不能分割：在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品——0/1背包问题物品是可分割的。选择物品i装入背包时，可以选择物品i的一部分xi（0≤xi≤1）装入，而不一定要全部装入背包——一般背包问题，简称背包问题6.2背包问题ch6.12这2类问题都具有最优子结构性质，极为相似。但一般背包问题可以用贪心算法求解；而0-1背包问题却不能用贪心算法求解，而只能得到它的近似解。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品时所导致的最终方案，然后再作出最好选择。由此导出许多互相重叠的子问题，这正是该问题可用动态规划算法求解的重要特征。实际上，动态规划算法的确可以有效求解0-1背包问题。一般背包问题用贪心选择可保证背包刚好能装满。而对于0-1背包问题，贪心选择无法保证最终能将背包装满。部分闲置的背包空间使每公斤背包空间的价值降低了，因此不能得到最优解。ch6.13贪心法求解背包问题背包问题的解可表示成一个n-元组:X=(x0,x1,...xn-1),0≤xi≤1,0≤in.xi为第i件物品装入背包中的那部分。可行解的约束条件:最优解的目标函数:(见P104例6-1表6-1)100,01,0niiiwxMwixiin10max0,01,0niiipxpixiin用贪心法求解,找出最优量度标准是至关重要的.ch6.14选择最优量度标准标准1选取目标函数(总价值)作为量度标准,每次取价值最大的物品装包,不考虑重量.得到近似解,而不是最优解.原因:只考虑当前最大收益,背包载重消耗太快.标准2选取重量作为量度标准,每次取重量最小的物体装包,不考虑收益.得到近似解,而不是最优解.标准3选取单位重量价值最大的物品装包,即每次选pi/wi最大的物品装包.标准最合理,得到最优解.(正确性有待证明)ch6.15基本步骤:1、首先计算每种物品单位重量的价值Pi/Wi并按非增次序进行排序；2、然后依贪心选择策略，选择单位重量价值最高的物品装入背包。依此策略一直地进行下去，将尽可能多的物品全部装入背包，直到将背包装满。3、若装入某件物品时，不能全部装下，而背包内的物品总重量仍未达到W，则根据背包的剩余载重，选择单位重量价值次高的物品并尽可能多地装入背包。具体算法可描述如下页：背包问题的贪心算法ch6.16程序6-2背包问题的贪心算法（最优度量标准：单位重量价值pi/wi最大）voidGreedyKnapsack(float*x){//前置条件：w[i]已按p[i]/w[i]的非增次序排序floatu=m;//将背包剩余载重量u初始化为mfor(inti=0;in;i++)x[i]=0;//对解向量x初始化for(i=0;in;i++){//按最优量度标准选择解分量xiif(w[i]u)break;//若当前物品i已无法全部装下，则跳出x[i]=1.0;//否则，整个装入当前物品iu=u-w[i];}//同时背包剩余载重减w[i]if(in)x[i]=u/w[i];//背包剩余空间只够放下当前物品i的x[i]部分}数组w存放物品的重量，数组p存放物品的价值，数组x存放背包问题的最优解。m为背包载重量，u为背包剩余载重量。如果不计按p[i]/w[i]的非增次序排列w[i]的时间，程序6-2的时间复杂度为O(n)。算法Greedyknapsack的主要计算时间在于将各种物品按单位重量价值p[i]/w[i]从大到小排序，为O(nlogn)。因此，算法的计算时间上界为O(nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。ch6.17最优解证明定理6-1：如果p0/w0≥p1/w1≥...≥pn-1/wn-1,则程序6-2求得的背包问题的解是最优解。证明：设X=(x0,x1,...,xn-1),0≤xi≤1,0≤in是贪心背包算法的解。则由贪心背包算法可知，解的形式一定为X=(1,...,1,xj,0,...,0),0≤xj1如果X不是最优解，另有可行解Y=(y0,y1,...,yk,...,yn-1)是最优解，则应有：设k是使得yk≠xk的最小下标，必有ykxk(见P106)。1100nniiiiiipypxch6.18假定以xk替换Y中的yk，得到新的解Z=(z0,...,zk-1,zk,zk+1,...,zn-1)。可知：替换前后X、Y、Z的前k个分量相等zi=yi=xi=1，0≤i≤k-1，但替换后zk=xk。为保证Z是可行解，应有：。11()()niiikkkikwyzwzy1011001111010110()(/)()(/)()(/)ZY()(/)()(/)nniiiiiiiiinniikkkkkiiiiiinniikkkkkiiikkiiniiiniiiikkpyyzwwppyyzwwpyyzwpwyzwpwpyzwwpzpyp（新的可行解的收益假定的最优解则：的收益）因此假设不成立，证得贪心背包算法的解X即为最优解！（重复这样的替换过程，最终可得到一个与X完全相等的解。）ch6.19课堂练习题：找换硬币考虑用最少的硬币数来找n分钱的问题，假设每个硬币的值都是整数。1）请给出一个贪心算法，使得所换硬币包括1角的，5分的，2角5分的和1分的？2）假设可换的硬币的单位是c的幂，也就是c0,c1,...,ck,其中整数c1,k≥1。证明贪心算法总可以产生一个最优解。3）对任意给定的硬币单位集合，用贪心法来求解，是否总能保证得到最优解（即：硬币数最少的最优硬币组合方案）？所给集合应当包括1分，以保证对任意n值均有解。ch6.202）证明：（反证）假设贪心法所得的解X=(xn-1,xn-2,…,x0)并非最优解，而是另有Y=(yn-1,yn-2,…,y0)为最优解。则一定有：0011(1)iiiiininxcycM且易知：最优解中（除面值为Cn-1的硬币以外，其他）任何一种硬币的个数yi一定小于C。因为若某一种面值为Ci-1的硬币个数C，则将C个面值为Ci-1的硬币用一个Ci面值的硬币来取代，可获得比最优解中的硬币数更少的硬币数，即获得更优解。ch6.21证明（续）：因此00111(1)(1)11(2)kiikkiikikcyccccccc从前向后依次比较X和Y中的解分量，若首个不相等的解分量下标为k，则定有xkyk（因为在贪心法求解时，xk已是当前情况下面值为Ck的硬币所能取的最大个数）。又因为xk和yk均为整数，因此xk-yk≥1。即所有面值小于Ck的硬币面值之和，一定小于Ck。ch6.22证明（续）：由于（1）式中下标n-1~k+1的分量均相等，因此可将（1）式简化为：000011()(3)iiiiikikiikkiikkikikxcycycxcxycc即：显然（2）式和（3）式产生矛盾，因此假设不成立，贪心法求得的解就是最优解。得证！ch6.233）对任意给定的硬币单位集合，用贪心法来求解，是否总能保证得到最优解（即：硬币数最少的最优硬币组合方案）？所给集合应当包括1分，以保证对任意n值均有解。不能。例如：硬币单位集合为（4,3,1），n=10。贪心法求得的解为（2,0,2），总共需要4枚硬币。而最优解为（1,2,0），总共需要3枚硬币。ch6.24补充：6.3带时限的(单位时间)作业排序有n个作业，每个作业都有一个截止期限di0（di为整数）。每个作业运行时间为1个单位时间。每个作业若能够在截止期限内完成，可获得pi0的收益。要求：得到一种作业调度方案，给出作业的一个子集和该子集的一种排列，使子集中的作业都能如期完成，并且获得最大的收益。ch6.25最优量度标准：按收益的非增次序选择作业，在不违反截止时限的前提下，加入部分解向量中。程序6-3带时限（单位时间）作业排序的贪心算法voidGreedyJob(intd[],SetX,intn){//前置条件：p0≥p1≥......≥pn-1X={0}//将作业0选入Xfor(intj=1;jn;j++)if(集合X∪{j}中作业都能在给定的时限内完成)X=X∪{j};//可行性判定}问题一：如何证明求得的一定是最优解？ch6.26定理6-2证明该贪心算法对于带时限（单位时间）作业排序问题将得到最优解。证明：设X=(x0,x1,...,xk)是贪心算法求得的解。并且X不是最优解，另有Y=(y0,y1,...,yr)是最优解。则必有X≠Y。若X=Y无需证明。若XY，则Y不是可行解，否则贪心法会将属于Y但不属于X的其他作业继续加入X。若YX，则Y不是最优解，矛盾！ch6.2