算法分析与设计2007第d讲

第D讲第1页上次内容：(1)TSP问题近似性能比为2的近似算法。(2)近似算法设计：TSP问题近似度为3/2近似算法。(3)多任务排工近似度为2-1/m的近似算法。(4)独立任务排工3m134的多项式时间近似算法。再解释绝对近似性能比：1.51.11.8我们设计了算法以后希望能找到一个界r,使得RA(I)r。r显然比1.8不会小。比如说能找到r=2.5，使得RA(I)2.5=r。(*)如果算法A求解每个实例I都会有RA(I)2.5，(**)显然对于算法A，必有小于2.5的r1，使得RA(I)r1。两件事(*)和(**)都很难做到。但是如果可以碰到这么一种情况：能够找到r，使得RA(I)r=2，又能举出一个实例I，满足RA(I)=r=2。绝对近似性能比定义的原因即在于此。渐进近似性能比也具有同样的含义。回到另一面去看看定理：若PNP，则图的着色问题不存在34AR的多项式时间近似算法。已知图的3着色问题是NP-hard问题，两个图相乘是什么意思：第D讲第2页abcxyzxayaxbybxcyczazbzcG=G1*G2的做法反证法，若图着色问题存在RA34的近似算法，则存在K，当OPT(G)K时，A(G)34OPT(G)设计图3着色判定问题算法如下：设3着色问题的实例为G=(V,E)(1)设G’为K点的完全图，构造G*=G*G’(2)调用算法A得到着色数A(G*)。分析：(3x)若G可以三着色OPT(G*)3K，A(G*)(4/3)3K=4K(4x)若G不能三着色OPT(G*)4K(说明为什么)，A(G*)OPT(G*)4K所以：(3)A(G*)4K，回答Yes。(4)若A(G*)4K，回答No。定理7.13：若PNP，则货郎旅游问题不存在近似度RA的多项式时间近似算法。为什么不说绝对近似性能比呢？顶点个数少时，枚举也能得到较好的解。说明：TSP问题不是在metric空间，所以不满足三角不等式。第D讲第3页证明：实际是证明若反之，则Hamilton回路问题存在多项式时间精确算法。(1)用反证法，设存在常数K，使RAK。即存在算法A，对TSP的任意最优解值超过某个常数的实例G，有：A(G)K*OPT(G)。(2)设GH=(V,E)是Hamilton回路问题任意实例，由GH构造TSP问题实例GTSP如下：V(GTSP)=V(GH)=V)E(Gv)(u,|,|)E(Gv)(u,,1),(HHVKvudaedcbaedcb1K|V|aedcbaedcb(3)分析GH存在hamilton回路OPT(GTSP)=|V|A(GTSP)K*OPT(GTSP)=K|V|GH不存在Hamilton回路OPT(GTSP)K|V|第D讲第4页A(GTSP)OPT(GTSP)K|V|这样我们就能设计Hamilton回路问题的多项式时间算法。说明：(1)找错一条边，就会出大问题，近似度超过任意常数，边太长了。(2)这不是metric空间的TSP问题，是任意空间的TSP问题，不存在任意常数近似度的近似算法。§7.3多项式时间近似方案独立任务排工的进一步讨论，n个任务，m台机器，每个任务加工时间长度ti。新算法，想办法多费点功夫，前K个任务求最优排工。也与问题有关。(1)任务排序：T={T1,T2,…,Tn}，t1t2…tn(2)确定正整数K,对前K个任务，求最优排工，后n-K个任务，按照先大后小顺序排工。上述算法叫F。举个例子：T={T1,T2,T3,T4,T5,T6}加工时间：8，6，5，4，4，1T1,T2,T3,T4先求最优排工。后两任务再排，得15。最优为14。第D讲第5页T1T4T2T3T5T61234567891011121314151612345678910111213141516这个不是最优的。定理7.14：m台处理器，独立任务排工。实例I。mkmIOPTIF1111)()(证明：(1)设T是前K个任务的排工时间长度，若F(I)=T，则F(I)=OPT(I)，以下设F(I)T。(2)在[0，F(I)-tk+1]区间所有处理器非空闲。由(1)决定，最后完成任务为Tj，jk，所以[0,F(I)-tj]区间所有机器非空闲，又tk+1tj最后一个完成的任务tjtk+1。(3)111))((kkniittIFmttk+1F(I)(**)OPT(I)niitm11F(I)-mm1tk+1第D讲第6页所以，F(I)OPT(I)+mm1tk+1(4)至少有一台机器加工1+km个任务。因为有至少k+1个任务，所以(***)OPT(I)(1+km)tk+1，最少也这么大。OPT(I)tmmIOPTIFk111)()(1111111(1)1kkmtmmkktmm第一个不等号由(**)而来，第二个不等号由(***)而来。(5)分析算法时间复杂度TA(m,n)=O(mk+nlogn)，k=m，近似性能比小于1+1/2，k=2m；近似性能比小于1+1/3；说明：k越大时间复杂度越高，解的优化程度越好。定义7.2：若问题的近似算法A()若满足对任意实例I任意0(1)RA()[I]1+(2)A()的时间复杂度是实例I的多项式函数，则，A()称为求解问题的多项式时间近似方案。解释：(1)1+很容易说明，但后面的多项式不容易说明,时间复杂度一定与有关。例子：近似性能比为1+，时间复杂度为：O(1n)，O(12n)，O(12n2)O(21n)等等，各种情况。一定是越小，时间复杂度越大。第D讲第7页(2)为什么叫多项式近似方案，而不叫多项式近似算法。因为没有确定大小，只有程序运行时才能确定。再考虑背包问题：MxwxPniiiniii11max，xi{0,1},I=1,…,n设元素：a1,a2,…,anp1,p2,…,pnw1,w2,…,wnnnwPwPwP...2211(1)简单算法描述先挑k个元素放入背包，然后调用前面7.1节算法选择其他元素装包，直到不能装入为止。这样装法显然不一定多么好，若对任意一种K个元素的组合都先放入背包尝试，则最后结果一定比直接装入好。全部尝试完后选择最好的，作为最后结果。先固定k个元素，再按照价值重量比显达后小装入的情况全试遍，则效果就好了。算法描述：Procedure-approx(P,W,M,n,K)1Pmax=0;2forallcombinationsIofsizeKandweightMdo//所有情况都试遍。3PI=IiiP;第D讲第8页4Pmax=max{Pmax,PI+L(I,P,W,M,n)}//L(.,.,.,.)是子程序。5endfor6end下面这个算法是先试装K个后再继续装的算法。ProcedureL(I,P,W,M,n)S=0;T=M-IiiW//计算剩余的空。Fori=1tondoIfiIandWiTthenS=S+Pi;T=T-WiEndifEndfor//有先后顺序的装包。Return(max{S,max{Pi|iI,1in}})//S是装进包的，与最大价值的元素比较。End例子：n=8P1P2P3P4P5P6P7P81121313343535565w1w2w3w4w5w6w7w8111212333434555M=110第D讲第9页上面已经按照价值重量比排好序了。(1)K=0时，直接从头开始装入：x1,x2,x3,x4,x5,x6,x7,x8=11111000前5个装入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，时，先装入1个，再装入其他，得到x1,x2,x3,x4,x5,x6,x7,x8=11110010Pmax=11+21+31+33+45=151W=1+11+21+23+45=101(3)k=2，先装入2个，再装入其他，得到x1,x2,x3,x4,x5,x6,x7,x8=1,1,1,0,1,1,0,0Pmax=11+21+31+43+53=159W=109=1+11+21+33+43这是最优解。定理7.15设背包问题最优解为P*，Pmax是前述先装算法-approx得到的解，则111max*KPP证明：(1)设R是最优解的背包元素下标集合，R虽然求不出来，但可以假设。第D讲第10页*PPRii，MWRii若|R|K，则能够求到最优解，以下假设|R|K。(2)将R中的物体排序排成有序对：(11ˆ,ˆwP),(22ˆ,ˆwP),…,(||||ˆ,ˆRRwP)，按照以下规则：(1)(11ˆ,ˆwP),(22ˆ,ˆwP),…,(KKwPˆ,ˆ)是R中前K个价值最大元素，任意i,j，1iK，K+1jn，jPPˆˆi。用数对表示元素，价值重量对表示元素。(2)从i=k+1开始到|R|满足11ˆˆˆˆiiiiWPWP。满足价值重量比由大到小排列。在此假设下：有1ˆ*KPPtk，t=1,…,|R|-K，但是这个没有用。(3)设考虑装包实验到R的前K个元素时的情况，有一种这样情况。PI=KiiP1ˆ，算法肯定会碰到这种情况。设S是调用L(I,P,W,M,n)增加的收益。说明：P*PI+S+mPˆ，mPˆ是调用L(I,P,W,M,n)第一个没有装入背包的元素价值(mmw,Pˆˆ)是R中的元素。这一步特别关键，要找一个比P*还好的界限，要说明白。为什么，因为装入以后就超重了。还是很难说明的。第D讲第11页k21Pˆ,...,Pˆ,Pˆ|R|1KPˆ,...,Pˆk21Pˆ,...,Pˆ,PˆSmPˆ为什么放进背包别的东西了，因为那些元素价值重量比更大。如果将同样重量，不属于最优解的元素替换出来，一定使价值变小。PmaxPI+S(K+1)mPˆ,|S|mPˆ//要回忆前面的算法。曾经选了最大的与价值重量比先大后小装出来的，两种情况的最好的。mPˆ1maxKP，mk,SmPˆ，所以前面的不等式成立。要保证第三个不等式成立，必须在求装入元素时采用前面近似度为2的算法装入。imPˆPˆ，1ik，SPˆm，所以*maxPPmaxˆImPSPP=maxIPSP+maxˆmPP1+11K=1+时间复杂度O(nK)=O(1n)主要是每种先装K个的情况都要尝试。