算法分析与设计-2016第11讲讲义.ppt

RA(I1)?r RA(I2)?r RA(I1) ? RA(I2) RA(I1)?r RA(I2)?r RA(I1) ? RA(I2) 若r1r，则任意I?D(?)，RA(I)?r1 若r1r，是否任意I?D(?)，有RA(I)?r1 假设算法A的近似性能比满足：RA(I) ? r (1)团判定图灵归约到团优化问题。 (2)针对刚才背包问题的算法，试着找一个实例，使算法求解这个实例的近似性能比尽可能大。 算法分析与设计 第11讲-2016 山东大学计算机学院 上次内容： (1)什么是拟多项式算法PESEUDO polynomial，考虑问题实例的两个参数，Max[I]，Length[I]。 (2)什么是数问题，不受Max[I]?P(Length[I])限制。 (3)什么是强NPC问题。限制数不很大时也很难解。数值参量受限时亦为NPC的。 (4)什么是拟多项式变换。 可以直接证明强NPC，也可以用拟多项式变换证明。 (5)什么是NP-hard问题，Turing规约。神喻图灵机。 (6)NPC问题对应的优化形式都是NP-hard问题。 图灵规约与拟多项式变换完全是两件事!! 图灵归约，更一般地说明那些非NP问题的有哪些信誉好的足球投注网站问题的计算复杂性。 说明含有数值参量的NPC问题的子问题的计算复杂性：拟多项式变换 数值参量不很大 图灵归约：?1??2， 说明目的：若?2有多项式时间求解算法，则?1也有多项式时间求解算法。 设求解?2的算法为A2。 有一个将?1实例转换为?2实例的变换f：I?f(I)。 设计求解?1的算法A1(I)，其中调用A2(f(I))， (1)若A2(f(I))能求得满足条件的解，则A1(I)也能求得满足条件的解。 (2)若A2(f(I))时间复杂度为O(1)， 则A1(I) 是多项式时间复杂度。 就把A1(I)叫做?1??2的图灵归约。 图灵规约与拟多项式变换完全是两件事!! 意味着A2(f(I)) 为多项式时间复杂度。 NP-Hard的解释： 一个问题能由任意一个NP问题图灵归约到该问题， 则该问题是NP-Hard的。 一个问题是NPC的，则该问题为NP-hard问题， 若?1是NP-hard问题，?1可以图灵归约到?2，则?2也是NP-hard问题。 定义NP-Hard： 若??NP，每个NP问题都能多项式归约到?，则??NPC。 若每个NP问题都能图灵归约到?，则??NP-Hard。 多项式变换是特殊的图灵归约 A的时间复杂度为多项式时间的 若算法A的时间复杂性是O(1)，则上述算法能够在多项式时间解答。 所以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。 证明：货郎优化问题?T货郎延伸问题。 即要证明： 如果货郎延伸问题有多项式算法， 则货郎优化问题有多项式算法。 设S(C, d, ?, B)为解答货郎延伸问题的算法。 设计货郎优化算法如下：折半法。 (1) Bmin=m-1; Bmax=m*max{d(ci,cj)}|ci,cj?C}//最大就这么大。 (2)若Bmax-Bmin=1，则B*=Bmax，输出B*。 (3) Bmid=?(Bmin+Bmax)/2?; (4)调用子程序：S[C, d, C1, Bmid]， (5)若回答yes，则Bmax=Bmid，转2；否则Bmin=Bmid，转2。 隐含 S[C,d,C1,Bmax]返回Yes S[C,d,C1,Bmin]返回No 为什么是多项式时间算法？ 时间复杂性：O(log2Bmax) //最优解值为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) ………… ………… 确定城市C?(m) 1 C?(1)=C1, 2 for i=2