算法分析與設(shè)計-2012-3.ppt

1、算法分析與設(shè)計,第3講-2012 山東大學(xué)計算機(jī)學(xué)院,上次內(nèi)容： (1)5個算法設(shè)計技術(shù)，分而治之，貪心法，回溯搜索(,-刪除,分支定界)，動態(tài)規(guī)劃，局部搜索 (2)局部搜索設(shè)計近似算法，現(xiàn)在也有了。 (3)說明什么是好算法，什么是壞算法。 多項式時間算法是好算法，指數(shù)時間算法叫壞算法。 (4)許多問題設(shè)計不出多項式時間求解算法，也有很多問題能找到多項式算法，以前的算法絕大多數(shù)都是多項式時間的。告訴人們正面的東西。 (5)企圖把問題分類，能否分為兩類，一類可以設(shè)計多項式時間算法，另一類不能設(shè)計多項式時間算法。 前人建立了一種模型，說明問題很難，怎樣說明。也是多年思考認(rèn)識的結(jié)果。,例子：先講問題

2、，這些問題找不到多項式時間算法。 實例：布爾變量集合：U=u1, u2, u3, u4, u5， C = , , , 詢問：是否存在真值指派， 使( ) ( ) ( ) ( ) = 1 布爾變量字母: ui, , 項(Clause):C1= , , Cm= ,應(yīng)用背景：硬件測試，軟件測試，知識庫表達(dá)，推理,u2,u3,u5,SAT問題一般描述： 實例：布爾變量集合：U=u1,u2,un，項集合C=c1, c2, , cm， ck=yk1,yk2,ykt, ykju1,u2,un, . 詢問：是否存在U的真值指派，使c1c2cm=1，就是為真(T)， ck=yk1yk2ykt 在人工智能的搜索求

3、解中，推理規(guī)則均采用合取范式表示。 芯片測試，測試條件都表示為邏輯表達(dá)式。,Satisfiability Problem,不需要求出解來，只需要判定是或否。,TSP問題：貨郎問題 實例：城市集合：C = c1,c2,cm, d(ci, cj) Z+，ci, cjC，正整數(shù)K. 詢問：是否存在城市排列 c(1),c(2),c(m)，使,Hamilton回路問題： 實例：無向簡單圖G = (V, E)，|V| = n。 詢問：是否存在V的頂點排列v(1), v(2), , v(n)，使(v(i),v(i+1)E(G), i=1,n，v(n+1)=v(1)。,上述三個問題均是詢問解的存在性，判斷是否

4、具有滿足條件的解。 這三個問題都找不到多項式時間算法，但都能找到指數(shù)時間算法。 什么是多項式時間？什么是指數(shù)時間？ 輸入長度：問題實例的規(guī)模。,問題的算法時間復(fù)雜性有很多，什么樣的好呢？ 每秒1百萬次/運(yùn)算速度,表說明多項式時間復(fù)雜度與指數(shù)時間復(fù)雜度，區(qū)別大。 主要是增長速度區(qū)別。,多項式時間算法是好算法，指數(shù)時間算法是壞算法。 這樣的定義未必絕對合理，很多人接受。,從頭所起，從定義圖靈機(jī)開始。,3.2確定型圖靈機(jī)與P類 前面定義的時間復(fù)雜度概念還比較模糊，模糊就解決不了問題。下面要說明什么是多項式時間可以求解的問題，實際要定義多項式時間復(fù)雜度，什么是時間復(fù)雜度，什么是空間復(fù)雜度，重新精確定義

5、。自圓其說，說明自然界中的問題，解決問題。 英文名字：DTM,(1)一個硬殼,存儲帶：一個方格存一個符號； 讀寫頭在那里，可以左右移動，一次移動一個方格。狀態(tài)控制器可以讀寫帶方格中的內(nèi)容； (2)硬殼中放入數(shù)據(jù)； 帶上放的符號：有限個，其中包括空白符號b， =b，是輸入符號集合。符號有限個，不能無限多個。 (3)有限個狀態(tài)；狀態(tài)個數(shù)不隨問題實例長度變化而變化。 Q =q0, q1, q2, , qy, qn，q0：起始狀態(tài)，qy, qn都是停機(jī)狀態(tài)，qy表示停機(jī)時回答yes，qn表示停機(jī)時回答no。qf=qy, qn,q0,q1,qy,(4)狀態(tài)轉(zhuǎn)換規(guī)則。 什么是狀態(tài)，三要素表示DTM狀態(tài)：

6、(1)q; (2)讀寫頭指向位置; (3)帶符號s，現(xiàn)在不關(guān)心讀寫頭位置，只關(guān)心讀寫頭指定帶方格的符號。在造計算機(jī)時，有一個地址寄存器。 狀態(tài)轉(zhuǎn)換規(guī)則就是程序： (Q-qf)Q：這是一個映射，程序語句，怎么改變狀態(tài)。 (qi, si)( )： 含義，當(dāng)前狀態(tài)qi，當(dāng)前讀寫頭所指方格中的符號si，則下一個狀態(tài) ， 將帶方格中的符號修改為 ，讀寫頭移動一個位置： = L, R, S 程序?qū)嶋H就是狀態(tài)轉(zhuǎn)換規(guī)則：初始狀態(tài)q0，按照程序轉(zhuǎn)換狀態(tài)，到結(jié)束時狀態(tài)qf，回答yes或no。,我們編的程序就是告訴計算機(jī)怎樣改變狀態(tài)。真正實現(xiàn)計算機(jī)，還有很多工作，怎樣用語言的形式描述狀態(tài)轉(zhuǎn)換規(guī)則。哪些硬件，哪些軟件

7、，電子計算機(jī)怎樣實現(xiàn)。 經(jīng)過多層翻譯，到達(dá)計算機(jī)最底層，就是狀態(tài)改變。,例子：利用Turing機(jī)判斷正整數(shù)的奇偶性。 (1)=0,1,b；(2)Q=q0, q1, q2, qy, qn (3)狀態(tài)轉(zhuǎn)換規(guī)則如下：想法，找到最后一位，判斷0或,以下是輸入的帶符號，輸入數(shù)據(jù)，實例，,以下是輸入的帶符號，輸入數(shù)據(jù)，實例，,(1)q0,1,r-q0,0讀寫頭位置1; (2)q0,0,r-q0,1讀寫頭位置2 (3)q0,1,r-q0,0讀寫頭位置3; (4)q0,0,r-q0,b讀寫頭位置4； (5)q0,b,l-q1,0讀寫頭位置3; (6)q1,0,s-q2,0讀寫頭位置3,q0,q1,q2,找到最

8、后一位，判斷0/1，確定奇偶性。 定義3.1：把問題的任意實例I輸入給DTM，都能經(jīng)過DTM有限步計算到達(dá)停機(jī)狀態(tài)qfqy, qn，則稱問題是確定turing可計算的，否則稱為確定turing不可計算的。有的問題不可計算。不是所有問題都可以DTM計算。 這里只關(guān)心可計算的，不可計算的問題咱不管。 前面的Sat問題，TSP問題，Hamilton回路問題都是DTM可計算的。,團(tuán)問題： 實例：無向圖G = (V, E)，正整數(shù)J Z+， 詢問：是否存在G的一個完全子圖G, |V(G)| J？ 輸入數(shù)據(jù)格式認(rèn)為是一種語言，規(guī)則當(dāng)然是語言,字符串|字符串是團(tuán)問題回答yes的實例。,所以叫做語言,問題的描

9、述：用一個三元組合表示， 描述問題的符號集合， 形式化描述實例，輸入數(shù)據(jù)的格式是什么，L， 也稱為一種語言。 在計算機(jī)上描述為符號串，abcda,fxcder,gtv 那不就是語言嗎？ L也可以認(rèn)為是符號串集合。 針對任意一個輸入I L，回答是什么？ (I) yes, no 實例有了以后，就有答案了，解也就有了, 回答yes的解可能多個。每個實例對應(yīng)一個確定的答案。 實質(zhì)上，(I)函數(shù)就描述問題的詢問,定義3.2： 問題是用某個DTM程序可解的， 任意實例IL，只要I寫在帶上， 從q0狀態(tài)開始執(zhí)行，總可經(jīng)過有限步計算停機(jī)， 且在帶上保留著該問題的解答(I)yes,no。 所用的狀態(tài)數(shù)為計算的時

10、間復(fù)雜度：TM(I)。 計算中所占用的帶方格數(shù)為空間復(fù)雜度SM(I)。,但是前面我們經(jīng)常用T(n)，而不去考慮T(I), 用某個實例的時間復(fù)雜性不能肯定客觀地說明算法好壞。 只看一個實例的時間沒法表達(dá)算法解決問題的好壞， 所以還是要看T(n)。這里n表示實例規(guī)模。,TM(I)：M解決I的時間復(fù)雜性。有問題，有程序M。 把M看作一個算法或一個程序。 L(n)=I|IL, |I|=n，實例集合，長度為n的語言集合。 問題規(guī)模怎么描述，就是實例所占用的帶方格數(shù)。 TM(n)=maxTM(I)|IL(n)，問題輸入長度為n時的時間復(fù)雜度。 SM(n)=maxSM(I)|IL(n)，問題輸入長度為n時的

11、空間復(fù)雜度。 這樣的定義是客觀的， 所有長度為n的實例中，計算時間最長的那個實例的時間復(fù)雜性定義為T(n)。 本質(zhì)上，TM(n)也是幾乎不可能精確得到的，往往只能得到TM(n)的一個(上)界。,定義3.4:多項式時間可解的：存在多項式函數(shù)P(n)， 使TM(n)P(n)。 則稱問題是多項式時間可計算的。 P類問題-DTM多項式時間可計算的。 在計算機(jī)上多項式時間算法，等價于DTM多項式時間程序。,3.3非確定圖靈機(jī)與NP類 先考慮多項式時間可驗證的問題，那就要先定義這種問題。 Rabin與Scott兩位科學(xué)家發(fā)明了這種非確定型計算,Sat問題： 實例: U = u1,u2,u3,u4,u5,

12、C1 = u1,u2, C2=u2, ,u5 C3= ,u3, C4=u2,u3,u5,素數(shù)分解問題： 實例：大整數(shù)n 詢問：是否存在兩個(素)數(shù)p1, p2，使得：p1*p2=n? 密碼學(xué)上十分重要的問題。驗證容易，求解難。 貨郎判定問題，團(tuán)問題都是這樣，Hamilton回路問題。,詢問：是否存在U的真值指派使C中的項均滿足。 解釋何謂滿足，就是使項對應(yīng)布爾表達(dá)式取值為1。,TSP問題： 實例：城市集合：C=c1,c2,cm,d(ci,cj)Z+，ci,cjC， 正整數(shù)K. 詢問：是否存在城市排列c(1)c(2)c(m)，使,Hamilton回路問題： 實例：無向簡單圖G = (V, E)，

13、|V| = n。 詢問：是否存在定點排列v(1), v(2), , v(n)， 使(v(i),v(i+1)E(G), i=1,n-1，(v(n),v(1) E(G)。,驗證容易求解難。五個問題都是多項式時間可驗證的。,d(i,j),團(tuán)問題： 實例：無向圖G = (V, E)，正整數(shù)J Z+， 詢問：是否存在G的一個完全子圖G, |V(G)| J？ 輸入數(shù)據(jù)格式認(rèn)為是一種語言，規(guī)則當(dāng)然是語言,所以給出NTM模型如下：給DTM強(qiáng)加另外一種超人的能力。 現(xiàn)在講述的NTM并不是Rabin的NTM，等價？變成另外一種描述方式。 (1)硬殼：,一個狀態(tài)的下一個狀態(tài)是好幾個狀態(tài)中的某一個，具體哪個狀態(tài)，程序

14、本身不能決定。因此有一棵狀態(tài)樹，狀態(tài)樹中有一個分支可到達(dá)Yes態(tài)，則M的計算結(jié)果就是Yes。,(2)機(jī)器的符號，=b (3)狀態(tài)集合：Q=q0,q1,q2,qf，qfqy,qn (4)NTM的工作分兩個階段，猜測階段和驗證階段 猜測：猜測部件寫在讀寫帶上一些符號。 (5)狀態(tài)轉(zhuǎn)換函數(shù)：在驗證階段執(zhí)行的程序,(qi,si)(qi,si,),哪一個狀態(tài)，哪一個符號，怎么移動，NTM的執(zhí)行過程與DTM相同， 但是為什么是非確定的，因為中間有符號si是由猜測部件猜測的， NTM動作依賴于si，當(dāng)然是非確定的。,解釋什么是NTM， (1)實際就是驗證機(jī)器，由猜測部件猜測最好的符號串， 然后狀態(tài)控制器根據(jù)

15、符號去執(zhí)行最好的動作。求出最優(yōu)解。 根據(jù)猜測部件求出的解回答結(jié)果。 (2)猜測部件猜測正確，則我們只需要編驗證程序就可以。 猜測部件猜測錯了，就不能保證最后回答對了。 (3)猜測部件應(yīng)該能夠保證，若是就能猜出來。 因此猜測部件到底有什么樣的猜測能力？可以想象。 (4)Sat問題若猜測部件給定一個解，能否編一個程序驗證是否滿足？ 能否編一個程序?qū)θ我獠聹y的解去驗證是否滿足？ 當(dāng)然能，這有什么不確定的地方？ 因為不知道猜測什么解，所以下一步不確定。 問題是猜測部件有多大能力。可以認(rèn)為猜測解。,v1,vm：所有圖的點 (1)Guess(x1m) (2)P1=x1;P2=Pm=;L=0. For i=

16、 2 To m step 1 do If xiP1,Pi-1 return error If xi=v1 L=L+d(Pi-1,v1)；Pi=v1 If xi=v2 L=L+d(Pi-1,v2)；Pi=v2 If xi=vm L=L+d(Pi-1,vm)；Pi=vm End for If LK return YES else return NO.,定義3.5：NTM可解， = 給定， 任意IL, NTM總可在有限步停機(jī)，給出正確答案， 則稱是NTM可解的，或NTM可計算的。,定義3.6： 時空復(fù)雜度。還是要考慮S(n),T(n) TNTM(I):解答實例I的步驟數(shù)目。 L(n)=I|IL,(I

17、)=1,|I|=n，回答是的長度為n的實例集合。 TNTM(n)=maxTNTM(I)|IL(n) SNTM(n)=maxSNTM(I)|IL(n) 時間復(fù)雜度只算執(zhí)行人編的程序的時間，猜測時間不算。,定義3.7：NP類問題， 存在解答的一個驗證程序M，TNTM(n)P(n)。 問題類。NTM多項式時間可解的問題。 驗證時間是多項式的就是NTM多項式時間可解的。 是否可以編個程序，解答SAT問題，解答Hamilton回路問題。 說明： P類，NP類，多項式時間可驗證的問題類NP類。 PNP,定理3.1：NP類的問題，均可用DTM在T(n)=O(2P(n)時間內(nèi)求解。 存在P(n)。 簡單說明怎

18、樣為什么。因為解的長度為q(n)：x1,x2,xq(n) 每個符號有種選擇， 不讓猜測部件猜了，把所有可能的解都舉出來，每個都驗證， 因為一次驗證多項式時間：q(n),解的長度不會超過q(n)， 總時間復(fù)雜度不超過：|q(n)=2P(n),3.4多項式變換與NPC類 前面的東西沒法證明TSP問題不存在多項式時間復(fù)雜度。 舉例子，很多人花費大量時間企圖證明TSP問題不存在多項式算法， 但是都沒有證出來。 求解問題時想到用變換。實際上求解問題用變換效果并不好。 但是可以用變換證明問題的計算難度。 用一個問題的語言描述另一個問題，任何一個實例都行方可。 把一個問題轉(zhuǎn)換為另一個問題解決。 用1的語言描

19、述2，若1存在多項式算法，則2也存在多項式算法。,舉個例子： sat,n皇后問題,第一行：x11,x1n, (ij,1i,jn) 第n行：xn1,xnn, (ij,1i,jn) 第1列：x11,xn1, (ij,1i,jn) 第n列：xn1,xnn, (ij,1i,jn),加上斜線：大家寫完。,每列只有一個取1： 每個斜線只有一個取1。 項個數(shù)，不超過,時間復(fù)雜度O(n3),x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x41 x42 x43 x44,x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 x41 x42 x43 x44,1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0,用yij表示邊(i,j)是否存在 y11 y12 y13 y14 y21 y22 y23 y24 y31 y32 y33 y34 y41 y42 y43