資源描述：
《算法分析與設(shè)計2007第b講》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第B講上次內(nèi)容：(1)什么是擬多項式算法PESEUDOpolynomial，在考慮問題實例描述的兩個參數(shù)，Max[I]，Length[I]。(2)什么是擬多項式變換，什么是數(shù)問題。(3)什么是強NPC問題，限制數(shù)不很大時也很難解。數(shù)值參量受限時亦為NPC的。(4)什么是NP-hard問題。Turing規(guī)約。神喻圖靈機。(5)NPC問題對應(yīng)的優(yōu)化形式都是NP-hard問題。很多問題具有與NPC問題同樣的復(fù)雜度，但不是NP問題，用圖靈規(guī)約，可以把這些問題統(tǒng)一起來。圖靈歸約：p1?p2，要說明若p2有多項式時間求解算法，則p1也有多項式時間求解算法。設(shè)求解p2的算法為A2。有一個將p1
2、實例轉(zhuǎn)換為p2實例的變換f：I?f(I)。設(shè)計求解p1的算法A1(I)，其中調(diào)用A2(f(I))，(1)若A2(*)能求得滿足條件的解，則A1(*)求得的解也滿足條件。(2)若A2(*)時間復(fù)雜度為O(1)，則A1(*)時間復(fù)雜度是多項式時間復(fù)雜度。實際可以假設(shè)A2(f(I))的計算不需要時間。這樣就叫p1圖靈歸約到p2，圖靈規(guī)約是多項式變換的推廣。若p1能圖靈規(guī)約到p2，則p2就不必p1容易。仔細(xì)解釋，難：不存在多項式算法易：存在多項式算法若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優(yōu)化問題：實例：城市集合C={C1,…,Cm}，城市之間距離d(Ci,Cj)，詢問：求城市排列：,,…,，使=min{
4、Cp1Cp2…Cpm為城市排列}定理：TSP優(yōu)化問題是NP-hard。證明：TSP判定問題圖靈歸約到TSP優(yōu)化問題。TSP判定問題是NPC，所以是NP-Hard。l設(shè)存在TSP優(yōu)化問題求解算法A，設(shè)計tsp判定問題的算法如下：1對于給定TSP判定問題的給定實例：G,d,K，調(diào)用A(G,d)，求得城市排列：，2若￡K，則回答yes，否則回答No。若A是多項
5、式算法，則上述算法能夠在多項式時間解答。所以TSP優(yōu)化問題是NP-hard問題。貨郎延伸問題實例：(1)城市集合C={C1,C2,…,Cm}，(2)任意兩個城市之間的距離d(Ci,Cj)?Z+，(3)正整數(shù)界值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。證明：將貨郎優(yōu)化問題圖靈歸約到貨郎延伸問題。設(shè)計貨郎判定算法如下：折半法。假設(shè)貨郎延伸問題算法為：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調(diào)用子程序：S[C,d,,Bmid]，若回答yes，則Bmax=Bmid轉(zhuǎn)2，否則Bmin=Bmid，轉(zhuǎn)2。//最優(yōu)解值為B*，最優(yōu)解怎么求？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，但是已經(jīng)將貨郎判定問題圖靈歸約到貨郎延伸。這樣最后求得C1,Cp(2),…,Cp(i-1),…,Cp(m)，為最優(yōu)解。還有第k個最大子集問題是NP-Hard，證明自己看。第7章：近似算法和概率算法只講近似算法，不講概率算法。搜索問題，就是求解，求滿足條
9、件的解，不再是判定問題了。含義：雖然不能得到最優(yōu)解，但能離最優(yōu)解不遠(yuǎn)。達(dá)不到最好，力爭更好?！?.1：近似算法及其性能評估符號：p，Dp，I?Dp，求解的目標(biāo)是最大化或最小化的優(yōu)化問題。詢問時要求解，按照解的格式，并滿足解的條件。Sp(I)：可行解集，現(xiàn)在不求最優(yōu)解了，只要符合解的格式就叫可行解。Mp(I,S)：對于I?Dp,S?Sp(I)，表示解值，解的數(shù)值?？偸怯靡粋€數(shù)值衡量解的優(yōu)化程度。S*?Sp(I)：表示最優(yōu)解，顯然有：Mp(I,S*)￡Mp(I,S)，最小優(yōu)化問題。M
