资源描述：
《算法分析与设计2007第b讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第B讲上次内容：(1)什么是拟多项式算法PESEUDOpolynomial，在考虑问题实例描述的两个参数，Max[I]，Length[I]。(2)什么是拟多项式变换，什么是数问题。(3)什么是强NPC问题，限制数不很大时也很难解。数值参量受限时亦为NPC的。(4)什么是NP-hard问题。Turing规约。神喻图灵机。(5)NPC问题对应的优化形式都是NP-hard问题。很多问题具有与NPC问题同样的复杂度，但不是NP问题，用图灵规约，可以把这些问题统一起来。图灵归约：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图灵归约到p2，图灵规约是多项式变换的推广。若p1能图灵规约到p2，则p2就不必p1容易。仔细解释，难：不存在多项式算法易：存在多项式算法若p1µTp2则p1难p2也难，p2易p1也易，p1易p2难易均可能。NP-Hard的定义：第13页第B讲一个问题是NPC的，则该问题推广称
3、为NP-hard问题，若p1是NP-hard问题，p1可以图灵归约到p2，则p2也是NP-hard问题。TSP优化问题：实例：城市集合C={C1,…,Cm}，城市之间距离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是多项
5、式算法，则上述算法能够在多项式时间解答。所以TSP优化问题是NP-hard问题。货郎延伸问题实例：(1)城市集合C={C1,C2,…,Cm}，(2)任意两个城市之间的距离d(Ci,Cj)ÎZ+，(3)正整数界值BÎZ+，(4)C中K个城市的部分旅游Q=询问：能否将Q延伸为一个长度不超过B的全程旅游回路：áCp(1),Cp(2),…,Cp(k),Cp(k+1),…,Cp(m),Cp(1)ñ第13页第B讲定理：货郎延伸问题是NP-hard。证明：将货郎优化问题图灵归约到货郎延伸问题。设计货郎判定算法如下：折半法。假设货郎延伸问题算法为：S[C
6、,d,,Bmid]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,,B*]，………，S[C,d,,B*]由此确定Cp(2)S[C,d,,B*]，S[C,d,,
8、B*]，………，S[C,d,,B*]由此确定Cp(3)5Cp(1)=C1,第13页第B讲6fori=2tomdoforj=1tomdo若CjÏ{C1,Cp(2),…,Cp(i-1)}且S[C,d,,B*]回答yes，则Cp(i)=Cj。没有判定货郎延伸是否NP，但是已经将货郎判定问题图灵归约到货郎延伸。这样最后求得C1,Cp(2),…,Cp(i-1),…,Cp(m)，为最优解。还有第k个最大子集问题是NP-Hard，证明自己看。第7章：近似算法和概率算法只讲近似算法，不讲概率算法。搜索问题，就是求解，求满足条
9、件的解，不再是判定问题了。含义：虽然不能得到最优解，但能离最优解不远。达不到最好，力争更好。§7.1：近似算法及其性能评估符号：p，Dp，IÎDp，求解的目标是最大化或最小化的优化问题。询问时要求解，按照解的格式，并满足解的条件。Sp(I)：可行解集，现在不求最优解了，只要符合解的格式就叫可行解。Mp(I,S)：对于IÎDp,SÎSp(I)，表示解值，解的数值。总是用一个数值衡量解的优化程度。S*ÎSp(I)：表示最优解，显然有：Mp(I,S*)£Mp(I,S)，最小优化问题。M
