搜索
第8章近似算法8.1近似算法及其近似比8.2多机调度问题8.2.1贪心的近似算法822改进的贪心近似算法8.2.2改进的贪心近似算法8.3货郎问题最邻近法8.3.1最邻近法8.3.2最小生成树法833最小权匹配法8.3.3最小权匹配法8.4背包问题841一个简单的贪心算法8.4.1一个简单的贪心算法8.4.2多项式时间近似方案8.4.3伪多项式时间算法与完全多项式时间近似方案伪多项式时间算法与完全多项式时间近似方案8.1近似算法及其近似比近似算法:A是一个多项式时间算法且对组合优化问题Π的每个实例I输出个可行解记A(I)()()是的值每一个实例I输出一个可行解σ.记A(I)=c(σ),c(σ)是σ的值最优化算法:恒有A(I)=OPT(I),即A总是输出I的最优解.当Π是最小化问题时,记rA(I)=A(I)/OPT(I);当Π是最大化问题时,记rA(I)=OPT(I)/A(I).,A()()()A的近似比为r(A是r–近似算法):对每一个实例I,rA(I)≤r.A具有常数比:r是一个常数.可近似性分类假设P≠NP,NP难的组合优化问题按可近似性可分成3类:(1)完全可近似的:对任意小的ε0,存在(1+ε)-近似算法.0-1背包问题0-1背包问题(2)可近似的:存在具有常数比的近似算法.机度等最小顶点覆盖、多机调度、满足三角不等式的货郎问题(3)不可近似的:不存在具有常数比的近似算法.()不可近似的不存在具有常数比的近似算法近似比是输入规模的对数多项式或多项式，如一般性的货郎问题的货郎问题最小顶点覆盖问题问题:任给图G=V,E,求G的顶点数最少的顶点覆盖.算法MVC:开始时令V′=∅.任取一条边(u,v),把u和v加入V′并删去u和v及其关联的边.重复上述过程,直至删去所有的边为止V′为所求的顶点覆盖边为止.V′为所求的顶点覆盖.234234146146{1,2}{1,2,3,4}569659{1,2,3,4,5,6}578578一个最优解：{1369}MVC的解：{123456}个最优解：{1,3,6,9}，MVC的解：{1,2,3,4,5,6}最小顶点覆盖问题分析:算法时间复杂度为O(m),m=|E|.记由条互不关联的边的端点组成为了覆盖记|V′|=2k,V′由k条互不关联的边的端点组成.为了覆盖这k条边需要k个顶点,从而OPT(I)≥k.于是,MVC(I)/OPT(I)≤2k/k=2.又,设图G由k条互不关联的边构成,显然又,设图G由k条互不关联的边构成,显然MVC(I)=2k,OPT(I)=k,这表明MVC的近似比不会小于2上面估计的MVC的近似这表明MVC的近似比不会小于2,上面估计的MVC的近似比已不可能再进一步改进.近似算法的分析研究近似算法的两个基本方面⎯⎯设计算法和分析算法的运行时间与近似比运行时间与近似比.分析近似比(1)关键是估计最优解的值.(2)构造使算法产生最坏的解的实例如果这个解的值与最(2)构造使算法产生最坏的解的实例.如果这个解的值与最优值的比达到或者可以任意的接近得到的近似比(这样的实例称作紧实例),那么说明这个近似比已经是最好的、不可例称作紧实例),那么说明这个近似比已经是最好的、不可改进的了;否则说明还有进一步的研究余地.(3)研究问题本身的可近似性即在P≠NP(或其他更强)的假(3)研究问题本身的可近似性,即在P≠NP(或其他更强)的假设下,该问题近似算法的近似比的下界.8.2多机调度问题多机调度问题:任给有穷的作业集A和m台相同的机器,作业a的处理时任给有穷的作集和台相同的机器,作的处时间为正整数t(a),每一项作业可以在任一台机器上处理.如何把作业分配给机器才能使完成所有作业的时间最短?即,如何把A划分成m个不相交的子集Ai使得⎬⎫⎨⎧∑最小?⎭⎬⎩⎨=∑∈miatiAa,,2,1|)(maxL最小负载: 分配给一台机器的作业的处理时间之和. 贪心法GMPS按输入的顺序分配作业把每项作业分贪心法G-MPS:按输入的顺序分配作业,把每一项作业分配给当前负载最小的机器.如果当前负载最小的机器有2台或2台以上,则分配给其中的任意一台.或2台以上,则分配给其中的任意台.实例例如，3台机器,8项作业,处理时间为3,4,3,6,5,3,8,41426714358G-MPS的解完成时间15358134完成时间1525678最优解完成时间12算法给出的分配方案是{1,4},{2,6,7},{3,5,8},负载分别为3+6=9,4+3+8=15,3+5+4=12最优的分配方案是{1,3,4},{2,5,6},{7,8},负载分别为3+3+6=12,4+5+3=12,8+4=12贪心法的性能定理8.1对多机调度问题的每一个有m台机器的实例I,⎞⎛).(OPT12)(MPSGImI⎟⎠⎞⎜⎝⎛−≤−证显然,).(max)(OPT)2(,)(1)(OPT)1(atIatmIAaAa∈∈≥≥∑设机器Mj的负载最大,记作t(Mj).又设b是最后被分配给机器Mj的作业.根据算法,在考虑分配b时Mj的负载最小,jj故)()(1)()(⎟⎞⎜⎛≤∑bbM.)()()()(⎟⎟⎠⎞⎜⎜⎝⎛−≤−∑∈btatmbtMtAaj证明于是)()(MPSGMtI=−)()()(1)()(MPSGbtbtatMtIj+⎟⎠⎞⎜⎝⎛−≤=∑)(11)(1btatmAa⎟⎠⎞⎜⎝⎛−+=⎠⎝∑∑∈)(OPT11)(OPT)()(IImmAa⎟⎠⎞⎜⎝⎛−+≤⎠⎝∑∈).(OPT12)()(Im⎟⎞⎜⎛−=⎟⎠⎜⎝).(OPT2Im⎟⎠⎜⎝紧实例M台机器,m(m−1)+1项作业,前m(m1)项作业的处理时间都为1最后一项作业的处理前m(m−1)项作业的处理时间都为1,最后一项作业的处理时间为m.算法把前项作业平均地分配给台机器每台算法把前m(m−1)项作业平均地分配给m台机器,每台m−1项,最后一项任意地分配给一台机器.GMPS(I)21G-MPS(I)=2m−1.最优分配方案是把前m(m−1)项作业平均地分配给m−1台机器,每台m项,最后一项分配给留下的机器,OPT(I)=m.G-MPS是2-近似算法m=5的紧实例16111621271217381318G-MPS算法的解491419510152021最优解最优解128.2.2改进的贪心近似算法递降贪心法DG-MPS:首先按处理时间从大到小重新排列作业然后运用G-MPS业,然后运用GMPS.例如对上一小节的紧实例得到最优解.对另个实例先重新排序对另一个实例：先重新排序8,6,5,4,4,3,3,3;3台机器的负载分别为8+3=11,6+4+3=13,5+4+3=12.的结比G-MPS的结果好.71的解486523DG-MPS的解完成时间13分析：DG-MPS增加排序时间O(nlogn),仍然是多项式时间近似比定理8.2对多机调度问题的每一个有m台机器的实例I,)(OPT13)(PMSDGII⎟⎞⎜⎛≤证设作业按处理时间从大到小排列为a1,a2,…,an,仍考虑负)(OPT22)(PMSDGImI⎟⎠⎜⎝−≤−载最大的机器Mj和最后分配给Mj的作业ai.(1)Mj只有一个作业,则i=1,必为最优解.(2)Mj有2个或2个以上作业,则i≥m+1,OPT(I)≥2t(ai))()()(1)()(MPSDGatatatMtIn+⎟⎞⎜⎛≤=∑)(OPT111)(OPT)(11)(1)()()()()(MPSDG1IIatatatatatmMtIniikkj⋅⎟⎞⎜⎛−+≤⎟⎞⎜⎛−+=+⎟⎠⎜⎝−≤=−∑∑=)(OPT13)(OPT21)(OPT)(1)(1IImIatmatmikk⎟⎠⎞⎜⎝⎛−=⎟⎠⎜⎝+≤⎟⎠⎜⎝+=∑=)(O22m⎟⎠⎜⎝8.3货郎问题本节考虑满足三角不等式的货郎问题831最邻近法8.3.1最邻近法最邻近法NN:从任意一个城市开始,在每一步取离当前所在城市最近的尚未到过的城市作为下个城市若这样的在城市最近的尚未到过的城市作为下一个城市.若这样的城市不止一个,则任取其中的1111一个.直至走遍所有城市,最后回到开始出发的城市.11121111215一个NN性能很坏的实例I,NN(I)21OPT(I)153112123111NN(I)=21,OPT(I)=151111最邻近法的性能定理8.3对于货郎问题所有满足三角不等式的n个城市的实例I总有实例I,总有⎡⎤()).(OPT1log1)(NN2InI+≤而且,对于每一个充分大的n,存在满足三角不等式的n个城市的实例I使得⎡⎤()).(OPT1log2)(NN2InI+≤城市的实例I使得41⎟⎞⎜⎛).(OPT34)1(log31)(NN2InI⎟⎠⎞⎜⎝⎛++8.3.2最小生成树法最小生成树法MST:首先,求图的一棵最小生成树T.然后,沿着T走两遍得到图的条欧拉回路最后顺着这条欧拉沿着T走两遍得到图的一条欧拉回路.最后,顺着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路.例例求最小生成树和欧拉回路都可以在多项式时间内完成,故求最小生成树和欧拉回路都可以在多项式时间内完成,故算法是多项式时间的.最小生成树法的性能定理8.4对货郎问题的所有满足三角不等式的实例I,MST(I)2OPT(I).证因为从哈密顿回路中删去一条边就得到一棵生成树故证因为从哈密顿回路中删去条边就得到棵生成树,故T的权小于OPT(I).沿T走两遍的长小于2OPT(I).因为满足三角不等式,抄近路不会增加长度,故足三角不等式,抄近路不会增加长度,故MST(I)2OPT(I).MST是2-近似算法.紧实例OPT(I)=2nOPT(I)=2nMST(I)=4n2MST(I)=4n-2⎞⎛)(OPT12In⎟⎠⎞⎜⎝⎛−=8.3.3最小权匹配法最小权匹配法MM:首先求图的一棵最小生成树T首先求图的棵最小生成树T.记T的所有奇度顶点在原图中的导出子图为H,H有偶数个顶点,求H的最小匹配M.把M加入T得到一个欧拉图,个顶点,求的最小匹配.把加入得到个欧拉图,求这个欧拉图的欧拉回路;最后,沿着这条欧拉回路,跳过已走过的顶点,抄近路得到一条哈密顿回路.生成树T导出子图H欧拉图哈密顿回路求任意图最小权匹配的算法是多项式时间的,因此MM是生成树T导出子图H欧拉图哈密顿回路多项式时间的.最小权匹配法的性能定理8.5对货郎问题的所有满足三角不等式的实例I,3证由于满足三角不等式导出子图H中的最短哈密顿回路C)(OPT23)(MMII证由于满足三角不等式,导出子图H中的最短哈密顿回路C的长度不超过原图中最短哈密顿回路的长度OPT(I).沿着C隔一条边取一条边得到H的一个匹配总可以使这个匹配隔条边取条边,得到H的个匹配.总可以使这个匹配的权不超过C长的一半.因此,H的最小匹配M的权不超过OPT(I)/2求得的欧拉回路的长小于(3/2)OPT(I)抄近过OPT(I)/2,求得的欧拉回路的长小于(3/2)OPT(I).抄近路不会增加长度,得证MM(I)(3/2)OPT(I)MM(I)(3/2)OPT(I).MM是3/2-近似算法货郎问题的难度定理8.6货郎问题(不要求满足三角不等式)是不可近似的,除非P=NP除非P=NP.证假设不然,设A是货郎问题的近似算法,其近似比r≤K,K是常数.任给图G=V,E,如下构造货郎问题的实例IG:城市集V,∀u,v∈V,若则令否则令其中若(u,v)∈E,则令d(u,v)=1;否则令d(u,v)=Kn,其中|V|=n.若G有哈密顿回路,则OPT(I)A(I)≤OPT(I)≤KOPT(IG)=n,A(IG)≤rOPT(IG)≤Kn否则OPT(I)KnA(I)≥OPT(I)KnOPT(IG)Kn,A(IG)≥OPT(IG)Kn所以,G有哈密顿回路当且仅当A(IG)≤Kn证明于是,下述算法可以判断图G是否有哈密顿回路:首先构造货郎问题的实例IG,然后对IG运用算法A.若A(IG)≤Kn,则输出“Yes”;否则输出“No”.由于K是固定的常数,构造IG可在O(n2)时间内完成且,G()|IG|=O(n2).A是多