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

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

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

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

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

5、。自圓其說，說明自然界中的問題，解決問題。 英文名字：DTM,(1)一個硬殼,存儲帶：一個方格存一個符號； 讀寫頭在那里，可以左右移動，一次移動一個方格。狀態(tài)控制器可以讀寫帶方格中的內(nèi)容； (2)硬殼中放入數(shù)據(jù)； 帶上放的符號：有限個，其中包括空白符號b， =b，是輸入符號集合。符號有限個，不能無限多個。 (3)有限個狀態(tài)；狀態(tài)個數(shù)不隨問題實(shí)例長度變化而變化。 Q =q0, q1, q2, , qy, qn，q0：起始狀態(tài)，qy, qn都是停機(jī)狀態(tài)，qy表示停機(jī)時(shí)回答yes，qn表示停機(jī)時(shí)回答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ì)算機(jī)時(shí)，有一個地址寄存器。 狀態(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é)束時(shí)狀態(tài)qf，回答yes或no。,我們編的程序就是告訴計(jì)算機(jī)怎樣改變狀態(tài)。真正實(shí)現(xiàn)計(jì)算機(jī)，還有很多工作，怎樣用語言的形式描述狀態(tài)轉(zhuǎn)換規(guī)則。哪些硬件，哪些軟件

7、，電子計(jì)算機(jī)怎樣實(shí)現(xiàn)。 經(jīng)過多層翻譯，到達(dá)計(jì)算機(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í)例，,以下是輸入的帶符號，輸入數(shù)據(jù)，實(shí)例，,(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：把問題的任意實(shí)例I輸入給DTM，都能經(jīng)過DTM有限步計(jì)算到達(dá)停機(jī)狀態(tài)qfqy, qn，則稱問題是確定turing可計(jì)算的，否則稱為確定turing不可計(jì)算的。有的問題不可計(jì)算。不是所有問題都可以DTM計(jì)算。 這里只關(guān)心可計(jì)算的，不可計(jì)算的問題咱不管。 前面的Sat問題，TSP問題，Hamilton回路問題都是DTM可計(jì)算的。,團(tuán)問題： 實(shí)例：無向圖G = (V, E)，正整數(shù)J Z+， 詢問：是否存在G的一個完全子圖G, |V(G)| J？ 輸入數(shù)據(jù)格式認(rèn)為是一種語言，規(guī)則當(dāng)然是語言,字符串|字符串是團(tuán)問題回答yes的實(shí)例。,所以叫做語言,問題的描

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

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

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

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

13、|V| = n。 詢問：是否存在定點(diǎn)排列v(1), v(2), , v(n)， 使(v(i),v(i+1)E(G), i=1,n-1，(v(n),v(1) E(G)。,驗(yàn)證容易求解難。五個問題都是多項(xiàng)式時(shí)間可驗(yàn)證的。,d(i,j),團(tuán)問題： 實(shí)例：無向圖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，等價(jià)？變成另外一種描述方式。 (1)硬殼：,一個狀態(tài)的下一個狀態(tài)是好幾個狀態(tài)中的某一個，具體哪個狀態(tài)，程序

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

15、符號去執(zhí)行最好的動作。求出最優(yōu)解。 根據(jù)猜測部件求出的解回答結(jié)果。 (2)猜測部件猜測正確，則我們只需要編驗(yàn)證程序就可以。 猜測部件猜測錯了，就不能保證最后回答對了。 (3)猜測部件應(yīng)該能夠保證，若是就能猜出來。 因此猜測部件到底有什么樣的猜測能力？可以想象。 (4)Sat問題若猜測部件給定一個解，能否編一個程序驗(yàn)證是否滿足？ 能否編一個程序?qū)θ我獠聹y的解去驗(yàn)證是否滿足？ 當(dāng)然能，這有什么不確定的地方？ 因?yàn)椴恢啦聹y什么解，所以下一步不確定。 問題是猜測部件有多大能力?？梢哉J(rèn)為猜測解。,v1,vm：所有圖的點(diǎn) (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可計(jì)算的。,定義3.6： 時(shí)空復(fù)雜度。還是要考慮S(n),T(n) TNTM(I):解答實(shí)例I的步驟數(shù)目。 L(n)=I|IL,(I

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

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

19、述2，若1存在多項(xiàng)式算法，則2也存在多項(xiàng)式算法。,舉個例子： 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。 項(xiàng)個數(shù)，不超過,時(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