算法分析与设计2009第b讲

上次内容：(1)什么是拟多项式算法PESEUDOpolynomial，在考虑问题实例描述的两个参数，Max[I]，Length[I]。(2)什么是拟多项式变换，什么是数问题。(3)什么是强NPC问题，限制数不很大时也很难解。数值参量受限时亦为NPC的。(4)什么是NP-hard问题。Turing规约。神喻图灵机。(5)NPC问题对应的优化形式都是NP-hard问题。图灵规约与拟多项式变换完全是两件事!!图灵归约：12，要说明若2有多项式时间求解算法，则1也有多项式时间求解算法。设求解2的算法为A2。有一个将1实例转换为2实例的变换f：If(I)。设计求解1的算法A1(I)，其中调用A2(f(I))，(1)若A2(*)能求得满足条件的解，则A1(*)求得的解也满足条件。(2)若A2(*)时间复杂度为O(1)，则A1(*)时间复杂度是多项式时间复杂度。实际可以假设A2(f(I))的计算不需要时间。这样就叫1图灵归约到2NP-Hard的定义：一个问题是NPC的，则该问题推广称为NP-hard问题，若1是NP-hard问题，1可以图灵归约到2，则2也是NP-hard问题。TSP优化问题：实例：城市集合C={C1,…,Cm}，城市之间距离d(Ci,Cj)，询问：求城市排列：*1C,*2C,…,*mC，使miiiCCd1*1*),(=min{miiiCCd11),(|C1C2…Cm为城市排列}定理：TSP优化问题是NP-hard。证明：TSP判定问题图灵归约到TSP优化问题。TSP判定问题是NPC，所以是NP-Hard。设存在TSP优化问题求解算法A，设计TSP判定问题的算法如下：1对于给定TSP判定问题的给定实例：G,d,K，调用A(G,d)，求得城市排列：***...21mCCC，2若miiiCCd1*1*),(K，则回答Yes，否则回答No。若A是多项式算法，则上述算法能够在多项式时间解答。所以TSP优化问题是NP-hard问题。说明货郎优化问题有多项式算法，则货郎判定问题有多项式算法。下面说明货郎判定问题有多项式算法，则货郎优化问题有多项式算法。货郎延伸问题实例：(1)城市集合C={C1,C2,…,Cm}，(2)任意两个城市之间的距离d(Ci,Cj)Z+，(3)正整数界值BZ+，(4)C中K个城市的部分旅游=C(1),C(2),…,C(k)询问：是否可将延伸为一个长度不超过B的全程旅游回路：C(1),C(2),…,C(k),C(k+1),…,C(m),C(1)定理：货郎延伸问题是NP-hard。证明：将货郎优化问题图灵归约到货郎延伸问题。即如果货郎延伸问题有多项式算法，则货郎优化问题有多项式算法。S(C,d,,B)为解答货郎延伸问题的算法。设计货郎优化算法如下：折半法。1Bmin=m;Bmax=m*max{d(ci,cj)}|ci,cjC}//最大就这么大。2若Bmax-Bmin=0，则B*=Bmin，暂停。3Bmid=(Bmin+Bmax)/2;4调用子程序：S[C,d,C1,Bmid]，若回答yes，则Bmax=Bmid，转2；否则Bmin=Bmid，转2。//最优解值为B*，最优解怎么求？S[C,d,C1,C2,B*]，S[C,d,C1,C3,B*]，………，S[C,d,C1,Cm,B*]由此确定C(2)S[C,d,C1,C(2),C2,B*]，S[C,d,C1,C(2),C3,B*]，………，S[C,d,C1,C(2),Cm,B*]由此确定C(3)5C(1)=C1,6fori=2tomdoforj=1tomdo若Cj{C1,C(2),…,C(i-1)}且S[C,d,C1,C(2),…,C(i-1),Cj,B*]回答yes，则C(i)=Cj。没有判定货郎延伸是否NP，但是已经将货郎优化问题图灵归约到货郎延伸问题。这样最后求得C1,C(2),…,C(i-1),…,C(m)，为最优解。还有第k个最大子集问题是NP-Hard，证明自己看。货郎延伸图灵规约到货郎判定怎么办？设货郎判定问题算法为TD(C,d,K)C(1)C(k)C(1)C(k)D1=d(C(1),C(2))+…+d(C(k-1),C(k))K1=K-D1只要存在一条回路长度不大于K1，原来实例即回答Yes。设C-{c(1),c(2),…,c(k)}={c1,c2,c3}最短的旅游回路为如下情况之一：c1,c(1),c(2),…,c(k),…c2,c(1),c(2),…,c(k),…c3,c(1),c(2),…,c(k),…所以图灵规约为：算法：S(C,d,,B)1C1C-{c(1),c(2),…,c(k)}+{c0},KB-1()(1)1(,)kiiidcc.2ForeverycxC1-{c0}3{ds(c0,cx)=d(c(1),cx),4ForcyC1-{c0,cx}5{ds(c0,cy)=d(c(k),cy)}6IfTD(C1,ds,K)==YES,returnYES7}8ReturnNO第7章：NP-难解问题近似算法只讲近似算法，不讲概率算法。含义：虽然不能得到最优解，但能离最优解不远。达不到最好，力争更好。§7.1：近似算法及其性能评估符号：，D，ID，求解的目标是最大化或最小化的优化问题。询问时要求解，按照解的格式，并满足解的条件。S(I)：可行解集，现在不求最优解了，只要符合解的格式就叫可行解。M(I,S)：对于ID,SS(I)，表示解值，解的数值。总是用一个数值衡量解的优化程度。S*S(I)：表示最优解，显然有：M(I,S*)M(I,S)，最小优化问题。M(I,S*)M(I,S)，最大优化问题。通常用OPT(I)=M(I,S*)表示最优解值。通常将实例I的最优解的解值记为：OPT(I)。假设有算法A，对于任意实例I都能找到最优解，A(I)=OPT(I)，则称算法A为求解问题的精确算法。也有很多问题能够求得最优解。有时总也求不到最优解，可以求出一个解，解的格式符合规则，但不能保证求到最优解，求出的解只是可行解。定义：给定问题，若有算法A，存在一个常数K0，使得所有实例ID，总有：|A(I)-OPT(I)|K则称算法A为解答问题的绝对近似算法。若A为多项式时间算法，则称A为解答问题的多项式时间绝对近似算法。已知当PNP时，NP-hard优化问题不存在多项式时间算法，但其中有些问题存在多项式时间绝对近似算法。存储最多程序问题：实例：n个程序，每个程序的存储容量分别为：L1,…,Ln。两个磁盘，存储容量都是L。询问：若不允许一个程序同时存在于两个磁盘内，求两个磁盘最多能存储程序的个数。这个问题是NP-hard，将划分问题图灵规约到该问题就能证明。假设L1+L2+…+Ln=2L，即可。现在设计一个算法：贪心算法。(1)对n个程序，按其存储容量的非降顺序排序，L1L2…Ln。(2)按程序编号从1到n，依次向磁盘1存放程序，直到磁盘1放不下为止，(3)再转向存储磁盘2，按照顺序依次向磁盘2存储程序，直到磁盘2不能存放为止。*这个算法的时间复杂度为O(nlogn)定理7.1：设I是存储最多程序问题的任意实例，OPT(I)为其最优解的解值，A(I)为算法A所求出的解的解值，有：|OPT(I)-A(I)|1。即算法A为多项式时间绝对近似算法。证明：考虑一个容量为2L的磁盘，按照L1,…,Ln的顺序存入磁盘可以存p个程序。OPT(I)p。LLpii21，两个磁盘按照前面算法：最少可以存储p-1个程序。所以：|A(I)-OPT(I)|1。放的程序越多越好，所以先放小的，后放大的。1231237456456并不是所有NP-hard问题都有多项式时间近似算法。最小度生成树问题，只讲什么问题，自己看吧。1324567这个图的最小度生成树是什么？局部搜索算法可使所求解达到所能达到最优解的值加1。绝大多数问题并不存在多项式时间绝对近似算法定理7.2：当PNP时，背包问题没有多项式时间绝对近似算法。证明：背包问题的优化形式：背包优化问题。优化问题很多时候可以用整数规划形式描述。njxBxwxpjnjjjnjjj1},1,0{,max11设背包问题存在多项式时间绝对近似算法A，则存在常数K，使对背包问题的任意实例I：有，|A(I)-OPT(I)|K。令p1i=(K+1)pi将背包问题实例变换为另一问题实例I1：nixBxwxpjniiiniii1},1,0{,max111根据假设有：|A(I1)-OPT(I1)|K又有：OPT(I1)=(K+1)OPT(I)所以：11)(1)(1KKIOPTKIA，可以认为A(I1)是K+1的整数倍。A(I1)(K+1)OPT(I)由于背包问题的实例中，每个元素的价值均为正整数，所以OPT(I)=1()1AIK，由此可以得到最优解值，这样货郎判定问题就可以解决了。与PNP矛盾。可以假设A(I1)是K+1的整数倍。一个问题的最优解值能知道，则其判定形式可多项式时间解答。定理7.3：若PNP，则最大独立集问题不存在多项式时间绝对近似算法。证明：设最大独立集问题的实例为G，有绝对近似算法A，使得：|A(G)-OPT(G)|K，构造最大独立集问题另一实例G’：G’由图G复制K+1个副本组成。显然有：OPT(G’)=(K+1)OPT(G)对于新构造的G’调用算法A得到：|A(G’)-OPT(G’)|K，得到11)(1)'(KKGOPTKGAOPT(G)=1)'(KGA，可以求到G的最优解值。可以认为A(G’)是K+1的倍数，所以OPT(G)=(')1AGK，与PNP矛盾。绝大多数NP-hard问题不存在多项式时间绝对近似算法。存在绝对近似算法的问题实在太少。所以人们更多地研究如下类型的算法。定义7.1：最小优化问题，实例I，解答的近似算法A，则算法A对实例I的近似性能比定义为：RA(I)=)()(IOPTIA，基本假设：A(I)OPT(I)ApproximationratioPerformanceratioPerformancefactor若最大优化问题，实例I，解答的近似算法A，RA(I)=)()(IAIOPT，基本假设：A(I)OPT(I)。显然这样定义后，不论最大优化还是最小优化，近似性能比总比1大。近似性能比越接近1越说明算法好。背包问题：}10{}{max11,，xBWxPxiniiiniii定理7.4：背包问题有多项式时间近似算法，任意I近似性能比RA(I)2。证明：设计一个算法：思想，价值重量比犹大到小排序。精打细算法，价值重量比排序不加思索法，直接选择两者从中选优。(1)将A中的元素排序，按照性能价格比。nnwPwPwP...2211(2)从一开始装入背包，直到不能装下为止，得到可行解GA(I)。(3)A(I)=max{GA(I),max{Pi|i=1,…,n}}//考虑最大价值的装法得Pi设正整数r满足：Bwrii1，Bwrii11，显然a1,…,ar是装入背包的物体。OPT(I))(2max1111IAPPPiniriirii所以RA(I)=)()(IAIOPT2装箱问题：实例：(1)n个物体的集合：S={a1,…,an}，(2)每个物体aiS，体积为：w(ai)。(3)容量为C的箱子。询问：最少需要多少个箱子，才能将S中物体都装入箱子内。每个箱子装入物体的体积和不超过C。首次适合算法最简单：fit-first(1)设箱子为：B1，…，Bm，按照一定顺序将a1，…，an依次装入箱子，一个箱子装满