算法分析与设计2007第d讲

《算法分析与设计2007第d讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第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。两件事(*)和(**)都很难做到。但是如果可以碰

2、到这么一种情况：能够找到r，使得RA(I)£r=2，又能举出一个实例I，满足RA(I)=r=2。绝对近似性能比定义的原因即在于此。渐进近似性能比也具有同样的含义。回到另一面去看看定理：若P¹NP，则图的着色问题不存在的多项式时间近似算法。已知图的3着色问题是NP-hard问题，两个图相乘是什么意思：第11页第D讲G=G1*G2的做法反证法，若图着色问题存在<的近似算法，则存在K，当OPT(G)³K时，A(G)

3、*=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，则货郎旅游问题不存在近似度<¥的多项式时间近似算法。为什么不说绝对近似性能比呢？顶点个数少时，枚举也能得到较好的解。说明：TSP问题不是在metric空间，所以不满足三角不等式。第11页第D讲证

4、明：实际是证明若反之，则Hamilton回路问题存在多项式时间精确算法。(1)用反证法，设存在常数K，使£K。即存在算法A，对TSP的任意最优解值超过某个常数的实例G，有：A(G)£K*OPT(G)。(2)设GH=(V,E)是Hamilton回路问题任意实例，由GH构造TSP问题实例GTSP如下：lV(GTSP)=V(GH)=Vl(3)分析GH存在hamilton回路«OPT(GTSP)=

5、V

6、A(GTSP)£K*OPT(GTSP)=K

7、V

8、GH不存在Hamilton回路«OPT(GTSP)>K

9、V

10、第11页第D讲A(

11、GTSP)³OPT(GTSP)>K

12、V

13、这样我们就能设计Hamilton回路问题的多项式时间算法。说明：(1)找错一条边，就会出大问题，近似度超过任意常数，边太长了。(2)这不是metric空间的TSP问题，是任意空间的TSP问题，不存在任意常数近似度的近似算法。§7.3多项式时间近似方案独立任务排工的进一步讨论，n个任务，m台机器，每个任务加工时间长度ti。新算法，想办法多费点功夫，前K个任务求最优排工。也与问题有关。(1)任务排序：T={T1,T2,…,Tn}，t1³t2³…³tn(2)确定正整数K,对前K个任务，

14、求最优排工，后n-K个任务，按照先大后小顺序排工。上述算法叫F。举个例子：T={T1,T2,T3,T4,T5,T6}加工时间：8，6，5，4，4，1T1,T2,T3,T4先求最优排工。后两任务再排，得15。最优为14。第11页第D讲这个不是最优的。定理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，j>k，所以[0,F(I)-tj

15、]区间所有机器非空闲，又tk+1³tj最后一个完成的任务tj

16、度越好。定义7.2：若问题p的近似算法A(e)若满足对任意实例I任意e>0(1)RA(e)[I]<1+e(2)A(e)的时间复杂度是实例I的多项式函数，则，A(e)称为求解问题p的多项式时间近似方案。解释：(1)1+e很容易说明，但后面的多项式不容易说明,时间复杂度一定与e有关。例子：近似性能比为1+e，时间复杂度为：O()，O(