第6章-贪心法

2019/12/18第5章贪心法12学习要点：理解贪心算法的概念掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法的一般方法通过应用范例学习贪心设计策略。（1）背包问题;（2）最优归并模式;（3）最小代价生成树;章节内容6.1一般方法6.2背包问题6.4最优归并模式6.5最小代价生成树6.1贪心法的一般方法贪心法的基本思想求解最优化问题的算法包含一系列步骤每一步都有一组选择作出在当关看来最好的选择希望通过作出局部优化选择达到全局优化选择贪心算法不一定总产生优化解贪心法是否产生优化解，需要严格证明贪心算法产生优化解的条件贪心选择性：若一个优化问题的全局优化解可以通过局部优化选择得到，则该问题称为具有贪心选择性。优化子结构：若一个优化问题的优化解包含它的优化解，则称其具有优化子结构。贪心算法正确性证明方法证明算法所求解的问题具有优化子结构证明算法所求解的问题具有贪心选择性证明算法确实按照贪心选择性进行局部优化选择可行解——问题给定某些约束条件，满足约束条件的问题解，即称为可行解。最优解——问题给出目标函数衡量可行解的好坏，使目标函数取最大（或最小）值的可行解称为最优解。贪心法求解最优化问题。贪心法通过分步决策的方法求解问题，每一步决策产生的一个分量。贪心法每一步上用作决策依据的选n-元组解（x0,x1,…,xn-1）择准则被称为最优量度标准。在选择解分量的过程中，添加新的解分量xk后，形成的部分解（x0,x1,…,xk)不违反可行解约束条件。每一次贪心选择都将所求问题简化为规模更小的子问题。贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择，仅依赖以前的选择，但不依赖于以后的选择。对于一个贪心算法，必须证明该算法的每一步上作出的选择，都必然最终导致问题的一个整体最优解。贪心算法不能保证对所有问题都得到整体最优解。对许多问题，如：一般背包问题、最佳合并模式问题、单源最短路径问题，最小生成树问题等，贪心算法确实能产生整体最优解。一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。能用贪心算法求解的问题一般具有两个性质：贪心选择性质和最优子结构性质。1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。2、最优子结构性质一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。程序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;//返回生成的最优解}给定n种物品和一个容量为M的背包。物品i的重量是wi，其价值为pi。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?物品不能分割：在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品——0/1背包问题物品是可分割的。选择物品i装入背包时，可以选择物品i的一部分xi（0≤xi≤1）装入，而不一定要全部装入背包——一般背包问题，简称背包问题.6.2背包问题这2类问题都具有最优子结构性质，极为相似。但一般背包问题可以用贪心算法求解；而0-1背包问题却不能用贪心算法求解，而只能得到它的近似解。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品时所导致的最终方案，然后再作出最好选择。由此导出许多互相重叠的子问题，这正是该问题可用动态规划算法求解的重要特征。实际上，动态规划算法的确可以有效求解0-1背包问题。一般背包问题用贪心选择可保证背包刚好能装满。而对于0-1背包问题，贪心选择无法保证最终能将背包装满。部分闲置的背包空间使每公斤背包空间的价值降低了，因此不能得到最优解。贪心法求解背包问题背包问题的解可表示成一个n-元组:X=(x0,x1,...xn-1),0≤xi≤1,0≤in.xi为第i件物品装入背包中的那部分。可行解的约束条件:最优解的目标函数:(见P104例6-1表6-1)100,01,0niiiwxMwixiin10max0,01,0niiipxpixiin用贪心法求解,找出最优量度标准是至关重要的.选择最优量度标准标准1选取目标函数(总价值)作为量度标准,每次取价值最大的物品装包,不考虑重量.得到近似解,而不是最优解.原因:只考虑当前最大收益,背包载重消耗太快.标准2选取重量作为量度标准,每次取重量最小的物体装包,不考虑收益.得到近似解,而不是最优解.标准3选取单位重量价值最大的物品装包,即每次选pi/wi最大的物品装包.标准最合理,得到最优解.(正确性有待证明)基本步骤:1、首先计算每种物品单位重量的价值Pi/Wi并按非增次序进行排序；2、然后依贪心选择策略，选择单位重量价值最高的物品装入背包。依此策略一直地进行下去，将尽可能多的物品全部装入背包，直到将背包装满。3、若装入某件物品时，不能全部装下，而背包内的物品总重量仍未达到W，则根据背包的剩余载重，选择单位重量价值次高的物品并尽可能多地装入背包。具体算法可描述如下页：背包问题的贪心算法程序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）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。最优解证明定理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假定以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1110001101110110()(/)()(/)()(/)()(/)()(/)ZYnnniiiiiiiiiiiinniikkkkkiiiiiiiknniikkkkkiiikkiikniiipzpyyzwwppyyzwwpyzwwppyyzwpwyzwpwpy因此假设不成立，证得贪心背包算法的解X即为最优解！（重复这样的替换过程，最终可得到一个与X完全相等的解。）课堂练习题：找换硬币考虑用最少的硬币数来找n分钱的问题，假设每个硬币的值都是整数。1）请给出一个贪心算法，使得所换硬币包括1角的，5分的，2角5分的和1分的？2）假设可换的硬币的单位是c的幂，也就是c0,c1,...,ck,其中整数c1,k≥1。证明贪心算法总可以产生一个最优解。3）对任意给定的硬币单位集合，用贪心法来求解，是否总能保证得到最优解（即：硬币数最少的最优硬币组合方案）？所给集合应当包括1分，以保证对任意n值均有解。2）假设可换的硬币的单位是c的幂，也就是c0,c1,...,ck,其中整数c1,k≥1。证明贪心算法总可以产生一个最优解。证明：（反证）令（nk,nk-1,...,n1,n0）是贪心算法的解，其中的解分量依次对应值为ck,ck-1,...,c1,c0的硬币个数。假设该贪心算法的解（nk,nk-1,...,n1,n0）不是最优解，另有（bk,bk-1,...,b1,b0)为最优解。则必有：kk-110kk-110kk-110kk-110kk-110kk-110nc+nc+...+nc+nc=bc+bc+...+bc+bc=n(1)n+n+...+n+nb+b+...+b+b(2)证明（续）：从左至右依次比较贪心法的解(nk,nk-1,...,n1,n0)和最优解(bk,bk-1,...,b1,b0)。设t是使得nt≠bt的最小下标.由于贪心法中nt是值为ct的硬币可取的最大个数，所以必有ntbt。所以有（1）式可得硬币的总价值相同：0tittiii=t-1t-1t-20t-1t-1t-2t-200tttt-1t-1t-2t-200tt-1t-20t-1t-20(n-b)c=(b-n)c=c(b-n)+c(b-n)+...+c(b-n)c(b-n)+c(b-n)+...+c(b-n)=c[(b+b+...+b)-(n+n+...+n)]tt-10tt-10n+n+...+nb+b+...+b得：与假设中（2）式矛盾。因此假设不成立，即：贪心法求得的解必定是最优解。证明（续）：又因为下标从k到t+1的解分量是相等的，所以可得：kk-10kk-10n+n+...+nb+b+...+bkk-10kk-10n+n+...+nb+b+...+b3）对任意给定的硬币单位集合，用贪心法来求解，是否总能保证得到最优解（即：硬币数最少的最优硬币组合方案）？所给集合应当包括1分，以保证对任意n值均有解。不能。例如：硬币单位集合为（4,3,1），n=10。贪心法求得的解为（2,0,2），总共需要4枚硬币。而最优解为（1,2,0），总共需要3枚硬币。6.4最优归并模式例6-4：将5个长度分别为(20,30,30,10,5)的有序文件(F1,F2,F3,F4,F5)两两合并成一个有序文件。两路合并外排序：通过反复执行将两个有序子序列合并成一个有序文件的操作，将n个长度不等的有序子文件合并成一个有序文件。整个合并过程中需要读/写记录数最少的合并方案为最佳合并模式。每一种合并模式可以用合并树描述：例6-4的两路合并树：95801550303020105F1F2F3F4F5(a)一种合并模式9535