算法分析與設(shè)計(jì)2016第11講

1、第11講-2016山東大學(xué)計(jì)算機(jī)學(xué)院上次內(nèi)容：(1)什么是擬多項(xiàng)式算法PESEUDO polynomial，考慮問題實(shí)例的兩個(gè)參數(shù)，MaxI，LengthI。(2)什么是數(shù)問題，不受MaxIP(LengthI)限制。(3)什么是強(qiáng)NPC問題。限制數(shù)不很大時(shí)也很難解。數(shù)值參量受限時(shí)亦為NPC的。(4)什么是擬多項(xiàng)式變換?？梢灾苯幼C明強(qiáng)NPC，也可以用擬多項(xiàng)式變換證明。(5)什么是NP-hard問題，Turing規(guī)約。神喻圖靈機(jī)。(6)NPC問題對(duì)應(yīng)的優(yōu)化形式都是NP-hard問題。圖靈規(guī)約與擬多項(xiàng)式變換完全是兩件事!圖靈歸約，更一般地說明那些非NP問題的搜索問題的計(jì)算復(fù)雜性。說明含有數(shù)值參量的N

2、PC問題的子問題的計(jì)算復(fù)雜性：擬多項(xiàng)式變換數(shù)值參量不很大圖靈歸約：12，說明目的：若2有多項(xiàng)式時(shí)間求解算法，則1也有多項(xiàng)式時(shí)間求解算法。設(shè)求解2的算法為A2。有一個(gè)將1實(shí)例轉(zhuǎn)換為2實(shí)例的變換f：If(I)。設(shè)計(jì)求解1的算法A1(I)，其中調(diào)用A2(f(I)，(1)若若A2(f(I)能求得滿足條件的解，則能求得滿足條件的解，則A1(I)也能也能求得滿足條件的解。求得滿足條件的解。(2)若若A2(f(I)時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(1)，則則A1(I) 是多項(xiàng)式時(shí)間復(fù)雜度。是多項(xiàng)式時(shí)間復(fù)雜度。就把A1(I)叫做12的圖靈歸約。圖靈規(guī)約與擬多項(xiàng)式變換完全是兩件事!意味著A2(f(I) 為多項(xiàng)式時(shí)間復(fù)

3、雜度。NP-Hard的解釋：一個(gè)問題能由任意一個(gè)NP問題圖靈歸約到該問題，則該問題是NP-Hard的。一個(gè)問題是NPC的，則該問題為NP-hard問題，若1是NP-hard問題，1可以圖靈歸約到2，則2也是NP-hard問題。定義NP-Hard：若NP，每個(gè)NP問題都能多項(xiàng)式歸約到，則NPC。若每個(gè)NP問題都能圖靈歸約到，則NP-Hard。多項(xiàng)式變換是特殊的圖靈歸約A的時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間的若算法A的時(shí)間復(fù)雜性是O(1)，則上述算法能夠在多項(xiàng)式時(shí)間解答。所以TSP優(yōu)化問題是NP-hard問題。說明貨郎優(yōu)化問題有多項(xiàng)式算法，則貨郎判定問題有多項(xiàng)式算法。下面說明貨郎判定問題有多項(xiàng)式算法，則貨郎優(yōu)

4、化問題有多項(xiàng)式算法。先講一個(gè)貨郎延伸問題：實(shí)例：(1)城市集合C=C1,C2,Cm，(2)任意兩個(gè)城市之間的距離d(Ci, Cj)Z+，(3)正整數(shù)界值BZ+，(4)C中k個(gè)城市的部分旅游= C(1), C(2), , C(k)詢問：是否可將延伸為一個(gè)長(zhǎng)度不超過B的全程旅游回路： C (1), C (2), , C (k), C (k+1), , C (m), C (1) 定理：貨郎延伸問題是NP-hard。證明：貨郎優(yōu)化問題T貨郎延伸問題。即要證明：如果貨郎延伸問題有多項(xiàng)式算法，則貨郎優(yōu)化問題有多項(xiàng)式算法。設(shè)S(C, d, , B)為解答貨郎延伸問題的算法。設(shè)計(jì)貨郎優(yōu)化算法如下：折半法折半法

5、。(1) Bmin=m-1; Bmax=m*maxd(ci,cj)|ci,cjC/最大就這么大。(2)若Bmax-Bmin=1，則B*=Bmax，輸出B*。(3) Bmid=(Bmin+Bmax)/2; (4)調(diào)用子程序：SC, d, , Bmid，(5)若回答yes，則Bmax=Bmid，轉(zhuǎn)2；否則Bmin=Bmid，轉(zhuǎn)2。 隱含SC,d,Bmax返回YesSC,d,Bmin返回No為什么是多項(xiàng)式時(shí)間算法？時(shí)間復(fù)雜性：O(log2Bmax)/最優(yōu)解值為B*，最優(yōu)解怎么求？SC, d, , B*，是/否SC, d, , B*，是/否 ，SC, d, , B*，是/否由此確定C(2)SC, d,

6、 , B*，是/否SC, d, , B*，是/否 ，SC, d, , B*由此確定C(3) 確定城市C(m)1 C(1)=C1,2 for i=2 to m do for j=1 to m do若CjC1,C(2),C(i-1) 且SC, d, C1,C(2),C(i-1),Cj , B*回答yes，則C(i)=Cj。沒有關(guān)心貨郎延伸是否NP，但是已經(jīng)將貨郎優(yōu)化問題圖靈歸約到貨郎延伸問題。這樣最后求得C1, C(2), , C(i-1), C(m)，為最優(yōu)解。還有第k個(gè)最大子集問題是NP-Hard，證明自己看。 貨郎延伸圖靈規(guī)約到貨郎判定怎么辦？下面說明：若貨郎判定問題有多項(xiàng)式算法，則貨郎延伸

7、問題有多項(xiàng)式算法。設(shè)貨郎判定問題算法為TD(C,d,K) 貨郎判定與貨郎延伸問題的區(qū)別？123希望一定要用到已有的路徑c(1), c(2), , c(k)怎樣才能逼著算法一定用到某條邊？d(c1,c(1)d(c3,c(k)K+1實(shí)例：C=C1,Cm，d(Ci,Cj)Z+，KZ+詢問：是否存在貨郎旅游，使其長(zhǎng)度K。 C(1) C(k) C(1) C(k) c1c3c4c5c2c1c2cm-kc2c1cm-kc6d(c(1),c(2) + + d(c(k-1),c(k)d(c1,c(1)d(cm-k,c(k)K+1K+1K+1K+1歸約也是設(shè)計(jì)算法，所以設(shè)計(jì)算法是最重要的。最大團(tuán)問題怎么做，作業(yè)題

8、。 C(1) C(k) C(1) C(k) 所以圖靈規(guī)約為：算法：S(C,d,B)(1)ds(c(1),c(k)=d(c(1),c(2) + . + d(c(k-1),c(k)(2)C1 = C-c(1), ., c(k)(3)For each two vertices cu,cv C1(4) ds(cu,cv)=d(cu,cv)(5)For each two vertices cx,cy C1(6) (7) ds(c(1),cx)=d(c (1),cx);ds(c(k),cy)=d(c (k),cy);(8) For cz C1-cx,cy(9) ds(c(1),cz) = K+1; ds(

9、c(k),cz) = K+1(10) If TD(C1c(1),c(k),ds,K)=YES (11) then return YES(12) (13) Return NOcxcyK+1K+1 K+1K+1第7章：NP-難解問題近似算法只講近似算法，不講概率算法。概率算法就是隨機(jī)算法，人們發(fā)現(xiàn)隨機(jī)算法在計(jì)算中描述簡(jiǎn)單，效果也不錯(cuò)。含義：雖然不能得到最優(yōu)解，但能離最優(yōu)解不遠(yuǎn)。達(dá)不到最好，力爭(zhēng)更好。人們最求極限的意志，精神，和策略。7.1：近似算法及其性能評(píng)估符號(hào)：，D，ID，求解的目標(biāo)是最大化或最小化的搜索問題。詢問時(shí)要求解，按照解的格式，并滿足解的條件。S(I)：可行解集，現(xiàn)在不求最優(yōu)解了，只

10、要符合解的格式就叫可行解。M(I,S)：對(duì)于ID, SS(I)，表示解值，解的數(shù)值。總是用一個(gè)數(shù)值衡量解的優(yōu)化程度。S*S(I)：表示最優(yōu)解，顯然有：M (I,S*) M (I,S)，最小優(yōu)化問題。，最小優(yōu)化問題。M (I,S*) M (I,S)，最大優(yōu)化問題。，最大優(yōu)化問題。 通常用OPT(I) = M(I, S*)表示最優(yōu)解值。通常將實(shí)例I的最優(yōu)解的解值記為：OPT(I)。假設(shè)有算法A，對(duì)于任意實(shí)例I都能找到最優(yōu)解，A(I)=OPT(I)，則稱算法A為求解問題的精確算法。也有很多問題能夠求得最優(yōu)解。有時(shí)總也求不到最優(yōu)解，可以求出一個(gè)解，解的格式符合解格式的要求，但不能保證求到最優(yōu)解，求出的

11、解只是可行解。定義：給定問題，若有算法A，存在一個(gè)常數(shù)K0，使得所有實(shí)例ID，總有：|A(I)-OPT(I)|K則稱算法A為解答問題的絕對(duì)近似算法。若A為多項(xiàng)式時(shí)間算法，則稱A為解答問題的多項(xiàng)式時(shí)間絕對(duì)近似算法。已知當(dāng)PNP時(shí)，NP-hard優(yōu)化問題不存在多項(xiàng)式時(shí)間算法，但其中有些問題存在多項(xiàng)式時(shí)間絕對(duì)近似算法。 A(I):算法A所得到的解的解值存儲(chǔ)最多程序問題：實(shí)例：n個(gè)程序，每個(gè)程序的存儲(chǔ)容量分別為：L1,Ln。兩個(gè)磁盤，存儲(chǔ)容量都是L。詢問：若不允許一個(gè)程序同時(shí)存在于兩個(gè)磁盤內(nèi)，求兩個(gè)磁盤最多能存儲(chǔ)程序的個(gè)數(shù)求兩個(gè)磁盤最多能存儲(chǔ)程序的個(gè)數(shù)。這個(gè)問題是NP-hard，將劃分問題圖靈規(guī)約到該

12、問題就能證明。假設(shè)L1+L2+Ln=2L，即可。現(xiàn)在設(shè)計(jì)一個(gè)算法：貪心算法。(1)對(duì)n個(gè)程序，按其存儲(chǔ)容量的非降順序排序，L1L2Ln。(2)按程序編號(hào)從1到n，依次向磁盤1存放程序，直到磁盤1放不下為止，(3)再轉(zhuǎn)向存儲(chǔ)磁盤2，按照順序依次向磁盤2存儲(chǔ)程序，直到磁盤2不能存放為止。 放的程序越多越好，所以先放小的，后放大的。放的程序越多越好，所以先放小的，后放大的。 1 2 3 1 2 3 7 4 5 6 4 5 6 7按照從小到大順序存放在一個(gè)2L的盤上，存放程序個(gè)數(shù)一定不比任意放在兩張次盤上的最大程序個(gè)數(shù)少。并不是所有NP-Hard問題都有多項(xiàng)式時(shí)間絕對(duì)近似算法。最小度生成樹問題，只講什

13、么問題，怎么做？自己看書。 1 3 2 4 5 6 7 1 3 2 4 5 6 7 這個(gè)圖的最小度生成樹是什么？局部搜索算法可使所求解達(dá)到所能達(dá)到最優(yōu)解的值加1。絕大多數(shù)問題并不存在多項(xiàng)式時(shí)間絕對(duì)近似算法定理7.2：當(dāng)P NP時(shí)，背包問題沒有多項(xiàng)式時(shí)間絕對(duì)近似算法。證明：背包問題的優(yōu)化形式：背包優(yōu)化問題。優(yōu)化問題很多時(shí)候可以用整數(shù)規(guī)劃形式描述。 njxBxwxpjnjjjnjjj1,1 , 0,max11背包問題實(shí)例：(p1,w1), (p2,w2),(pn,wn)，B背包容量：B設(shè)背包問題存在多項(xiàng)式時(shí)間絕對(duì)近似算法A，則存在常數(shù)K，使對(duì)背包問題的任意實(shí)例I：(p1,w1),(pn,wn)，B

14、，有，|A(I)-OPT(I)| K。令p1i=(K+1)pi將背包問題實(shí)例變換為另一問題實(shí)例將背包問題實(shí)例變換為另一問題實(shí)例I1： nixBxwxpjniiiniii1,1 , 0,max111njxBxwxpjnjjjnjjj1,1 , 0,max11根據(jù)假設(shè)有：|A(I1)-OPT(I1)|K又有：OPT(I1)=(K+1)OPT(I) 11)(1)(1KKIOPTKIA可以認(rèn)為A(I1)是K+1的整數(shù)倍。I1:(p11,w1),(p1n,wn)A(I1)(K+1)OPT(I)=OPT(I1) a b c d 解值為裝箱問題：實(shí)例：(1)n個(gè)物體的集合：S=a1,an，(2)每個(gè)物體aiS，體積為：w(ai)。(3)容量為C的箱子。詢問：最少需要多少個(gè)箱子，才能將S中物體都裝入箱子內(nèi)。每個(gè)箱子裝入物體的體積和不超過C。首次適合算法最簡(jiǎn)單：fit-first W(Bi)表示Bi裝入物體的體積之和(1)設(shè)箱子為：B1，Bm，按照一定順序?qū)1，an依次裝入箱子，一個(gè)箱子裝完，再裝另一個(gè)箱子。這就是