算法分析与设计2007第d讲.doc

第D讲上次内容：(1)TSP问题近似性能比为2的近似算法。(2)近似算法设计：TSP问题近似度为3/2近似算法。(3)多任务排工近似度为2-1/m的近似算法。(4)独立任务排工的多项式时间近似算法。再解释绝对近似性能比：我们设计了算法以后希望能找到一个界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。绝对近似性能比定义的原因即在于此。渐进近似性能比也具有同样的含义。回到另一面去看看定理：若PNP，则图的着色问题不存在的多项式时间近似算法。已知图的3着色问题是NP-hard问题，两个图相乘是什么意思：G=G1*G2的做法反证法，若图着色问题存在的近似算法，则存在K，当OPT(G)K时，A(G)OPT(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：若PNP，则货郎旅游问题不存在近似度K|V|A(GTSP)OPT(GTSP)K|V|这样我们就能设计Hamilton回路问题的多项式时间算法。说明：(1)找错一条边，就会出大问题，近似度超过任意常数，边太长了。(2)这不是metric空间的TSP问题，是任意空间的TSP问题，不存在任意常数近似度的近似算法。7.3多项式时间近似方案独立任务排工的进一步讨论，n个任务，m台机器，每个任务加工时间长度ti。新算法，想办法多费点功夫，前K个任务求最优排工。也与问题有关。(1)任务排序：T=T1, T2, , Tn，t1t2tn(2)确定正整数K,对前K个任务，求最优排工，后n-K个任务，按照先大后小顺序排工。上述算法叫F。举个例子：T=T1,T2,T3,T4,T5,T6加工时间：8，6，5，4，4，1T1,T2,T3,T4先求最优排工。后两任务再排，得15。最优为14。这个不是最优的。定理7.14：m台处理器，独立任务排工。实例I。证明：(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+1tj最后一个完成的任务tj0(1)RA(e)IK。(2)将R中的物体排序排成有序对：(),(), , ()，按照以下规则：(1)(),(), , ()是R中前K个价值最大元素，任意i,j，1iK，K+1jn，。用数对表示元素，价值重量对表示元素。(2)从i=k+1开始到|R|满足。满足价值重量比由大到小排列。在此假设下：有，t=1,|R|-K，但是这个没有用。(3)设考虑装包实验到R的前K个元素时的情况，有一种这样情况。PI=，算法肯定会碰到这种情况。设S是调用L(I,P,W,M,n)增加的收益。说明：P*k, S，所以前面的不等式成立。要保证第三个不等式