资源描述：
《算法分析与设计2009第b讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、上次内容：(1)什么是拟多项式算法PESEUDOpolynomial，在考虑问题实例描述的两个参数，Max[I]，Length[I]。(2)什么是拟多项式变换，什么是数问题。(3)什么是强NPC问题，限制数不很大时也很难解。数值参量受限时亦为NPC的。(4)什么是NP-hard问题。Turing规约。神喻图灵机。(5)NPC问题对应的优化形式都是NP-hard问题。图灵规约与拟多项式变换完全是两件事!!图灵归约：p1®p2，要说明若p2有多项式时间求解算法，则p1也有多项式时间求解算法。设求解p2的算法为A2。有一个将p1实例
2、转换为p2实例的变换f：I®f(I)。设计求解p1的算法A1(I)，其中调用A2(f(I))，(1)若A2(*)能求得满足条件的解，则A1(*)求得的解也满足条件。(2)若A2(*)时间复杂度为O(1)，则A1(*)时间复杂度是多项式时间复杂度。实际可以假设A2(f(I))的计算不需要时间。这样就叫p1图灵归约到p2NP-Hard的定义：一个问题是NPC的，则该问题推广称为NP-hard问题，若p1是NP-hard问题，p1可以图灵归约到p2，则p2也是NP-hard问题。TSP优化问题：实例：城市集合C={C1,…,Cm}，
3、城市之间距离d(Ci,Cj)，询问：求城市排列：,,…,，使=min{
4、Cp1Cp2…Cpm为城市排列}定理：TSP优化问题是NP-hard。证明：TSP判定问题图灵归约到TSP优化问题。TSP判定问题是NPC，所以是NP-Hard。l设存在TSP优化问题求解算法A，设计TSP判定问题的算法如下：1对于给定TSP判定问题的给定实例：G,d,K，调用A(G,d)，求得城市排列：，2若£K，则回答Yes，否则回答No。若A是多项式算法，则上述算法能够在多项式时间解答。所以TSP优化问题是NP-hard问题。说明货郎优化问题有多项式
5、算法，则货郎判定问题有多项式算法。下面说明货郎判定问题有多项式算法，则货郎优化问题有多项式算法。货郎延伸问题实例：(1)城市集合C={C1,C2,…,Cm}，(2)任意两个城市之间的距离d(Ci,Cj)ÎZ+，(3)正整数界值BÎZ+，(4)C中K个城市的部分旅游Q=áCp(1),Cp(2),…,Cp(k)ñ询问：是否可将Q延伸为一个长度不超过B的全程旅游回路：áCp(1),Cp(2),…,Cp(k),Cp(k+1),…,Cp(m),Cp(1)ñ定理：货郎延伸问题是NP-hard。证明：将货郎优化问题图灵归约到货郎延伸问题。即
6、如果货郎延伸问题有多项式算法，则货郎优化问题有多项式算法。S(C,d,Q,B)为解答货郎延伸问题的算法。设计货郎优化算法如下：折半法。1Bmin=m;Bmax=m*max{d(ci,cj)}
7、ci,cjÎC}//最大就这么大。2若Bmax-Bmin=0，则B*=Bmin，暂停。3Bmid=ë(Bmin+Bmax)/2û;4调用子程序：S[C,d,,Bmid]，若回答yes，则Bmax=Bmid，转2；否则Bmin=Bmid，转2。//最优解值为B*，最优解怎么求？S[C,d,,B*]，S[C,d,8、C3>,B*]，………，S[C,d,,B*]由此确定Cp(2)S[C,d,,B*]，S[C,d,,B*]，………，S[C,d,,B*]由此确定Cp(3)5Cp(1)=C1,6fori=2tomdoforj=1tomdo若CjÏ{C1,Cp(2),…,Cp(i-1)}且S[C,d,,B*]回答yes，则Cp(i)=Cj。没有判定货郎延伸是否NP，但是已经将货郎优化问题图灵归约到货郎延伸问题。这
9、样最后求得C1,Cp(2),…,Cp(i-1),…,Cp(m)，为最优解。还有第k个最大子集问题是NP-Hard，证明自己看。货郎延伸图灵规约到货郎判定怎么办？设货郎判定问题算法为TD(C,d,K)®D1=d(Cp(1),Cp(2))+…+d(Cp(k-1),Cp(k))K1=K-D1只要存在一条回路长度不大于K1，原来实例即回答Yes。设C-{cp(1),cp(2),…,cp(k)}={c1,c2,c3}最短的旅游回路为如下情况之一：c1,cp(1),cp(2),…,cp(k),…c2,cp(1),cp(2),…,cp(k)
10、,…c3,cp(1),cp(2),…,cp(k),…所以图灵规约为：算法：S(C,d,Q,B)1C1¬C-{cp(1),cp(2),…,cp(k)}+{c0},K¬B-.2ForeverycxÎC1-{c0}3{ds(c0,cx)=d(cp(1),cx),4ForcyÎC1-
