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

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

1、算法分析与设计第11讲-2016山东大学计算机学院上次内容：(1)什么是拟多项式算法PESEUDOpolynomial，考虑问题实例的两个参数，Max[I]，Length[I]。(2)什么是数问题，不受Max[I]P(Length[I])限制。(3)什么是强NPC问题。限制数不很大时也很难解。数值参量受限时亦为NPC的。(4)什么是拟多项式变换。可以直接证明强NPC，也可以用拟多项式变换证明。(5)什么是NP-hard问题，Turing规约。神喻图灵机。(6)NPC问题对应的优化形式都是NP-hard问题。图灵规约与拟多项式变换完全是两件事!!图灵归约，更一般地说明那些非

2、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

3、(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问题。说明货郎优化问题有多项式算法，则货

4、郎判定问题有多项式算法。下面说明货郎判定问题有多项式算法，则货郎优化问题有多项式算法。先讲一个货郎延伸问题：实例：(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货郎延伸问题。即要证明：如果货郎延伸问题有多项式算法，则货郎优化问题有多

5、项式算法。设S(C,d,,B)为解答货郎延伸问题的算法。设计货郎优化算法如下：折半法。(1)Bmin=m-1;Bmax=m*max{d(ci,cj)}

6、ci,cjC}//最大就这么大。(2)若Bmax-Bmin=1，则B*=Bmax，输出B*。(3)Bmid=(Bmin+Bmax)/2;(4)调用子程序：S[C,d,,Bmid]，(5)若回答yes，则Bmax=Bmid，转2；否则Bmin=Bmid，转2。隐含S[C,d,,Bmax]返回YesS[C,d,,Bmin]返回No为什么是多项式时间算法？时间复杂性：O(log2Bmax)//最优解

7、值为B*，最优解怎么求？S[C,d,,B*]，是/否S[C,d,,B*]，是/否………，S[C,d,,B*]，是/否由此确定C(2)S[C,d,,B*]，是/否S[C,d,,B*]，是/否………，S[C,d,,B*]由此确定C(3)……………………确定城市C(m)1C(1)=C1,2fori=2tomdoforj=1tomdo若Cj{C1,C(2),…,C(i-1)}且S[C,d,C1,C(2),…,C(i-1),Cj,B*]回答ye

8、s，则C(i)=Cj。没有关心货郎延伸是否NP，但是已经将货郎优化问题图灵归约到货郎延伸问题。这样最后求得C1,C(2),…,C(i-1),…,C(m)，为最优解。还有第k个最大子集问题是NP-Hard，证明自己看。货郎延伸图灵规约到货郎判定怎么办？下面说明：若货郎判定问题有多项式算法，则货郎延伸问题有多项式算法。设货郎判定问题算法为TD(C,d,K)货郎判定与货郎延伸问题的区别？123希望一定要用到已有的路径c(1),c(2),…,c(k)怎样才能逼着算法一定用到某条边？d(c1,c(1))d(c