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

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

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

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

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

5、。自圓其說(shuō)，說(shuō)明自然界中的問(wèn)題，解決問(wèn)題。 英文名字：DTM,(1)一個(gè)硬殼,存儲(chǔ)帶：一個(gè)方格存一個(gè)符號(hào)； 讀寫頭在那里，可以左右移動(dòng)，一次移動(dòng)一個(gè)方格。狀態(tài)控制器可以讀寫帶方格中的內(nèi)容； (2)硬殼中放入數(shù)據(jù)； 帶上放的符號(hào)：有限個(gè)，其中包括空白符號(hào)b， =b，是輸入符號(hào)集合。符號(hào)有限個(gè)，不能無(wú)限多個(gè)。 (3)有限個(gè)狀態(tài)；狀態(tài)個(gè)數(shù)不隨問(wèn)題實(shí)例長(zhǎng)度變化而變化。 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)帶符號(hào)s，現(xiàn)在不關(guān)心讀寫頭位置，只關(guān)心讀寫頭指定帶方格的符號(hào)。在造計(jì)算機(jī)時(shí)，有一個(gè)地址寄存器。 狀態(tài)轉(zhuǎn)換規(guī)則就是程序： (Q-qf)Q：這是一個(gè)映射，程序語(yǔ)句，怎么改變狀態(tài)。 (qi, si)( )： 含義，當(dāng)前狀態(tài)qi，當(dāng)前讀寫頭所指方格中的符號(hào)si，則下一個(gè)狀態(tài) ， 將帶方格中的符號(hào)修改為 ，讀寫頭移動(dòng)一個(gè)位置： = 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ī)，還有很多工作，怎樣用語(yǔ)言的形式描述狀態(tài)轉(zhuǎn)換規(guī)則。哪些硬件，哪些軟件

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

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

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

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

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

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

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

15、符號(hào)去執(zhí)行最好的動(dòng)作。求出最優(yōu)解。 根據(jù)猜測(cè)部件求出的解回答結(jié)果。 (2)猜測(cè)部件猜測(cè)正確，則我們只需要編驗(yàn)證程序就可以。 猜測(cè)部件猜測(cè)錯(cuò)了，就不能保證最后回答對(duì)了。 (3)猜測(cè)部件應(yīng)該能夠保證，若是就能猜出來(lái)。 因此猜測(cè)部件到底有什么樣的猜測(cè)能力？可以想象。 (4)Sat問(wèn)題若猜測(cè)部件給定一個(gè)解，能否編一個(gè)程序驗(yàn)證是否滿足？ 能否編一個(gè)程序?qū)θ我獠聹y(cè)的解去驗(yàn)證是否滿足？ 當(dāng)然能，這有什么不確定的地方？ 因?yàn)椴恢啦聹y(cè)什么解，所以下一步不確定。 問(wèn)題是猜測(cè)部件有多大能力?？梢哉J(rèn)為猜測(cè)解。,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，回答是的長(zhǎng)度為n的實(shí)例集合。 TNTM(n)=maxTNTM(I)|IL(n) SNTM(n)=maxSNTM(I)|IL(n) 時(shí)間復(fù)雜度只算執(zhí)行人編的程序的時(shí)間，猜測(cè)時(shí)間不算。,定義3.7：NP類問(wèn)題， 存在解答的一個(gè)驗(yàn)證程序M，TNTM(n)P(n)。 問(wèn)題類。NTM多項(xiàng)式時(shí)間可解的問(wèn)題。 驗(yàn)證時(shí)間是多項(xiàng)式的就是NTM多項(xiàng)式時(shí)間可解的。 是否可以編個(gè)程序，解答SAT問(wèn)題，解答Hamilton回路問(wèn)題。 說(shuō)明： P類，NP類，多項(xiàng)式時(shí)間可驗(yàn)證的問(wèn)題類NP類。 PNP,定理3.1：NP類的問(wèn)題，均可用DTM在T(n)=O(2P(n)時(shí)間內(nèi)求解。 存在P(n)。 簡(jiǎn)單說(shuō)明怎

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

19、述2，若1存在多項(xiàng)式算法，則2也存在多項(xiàng)式算法。,舉個(gè)例子： sat,n皇后問(wèn)題,第一行：x11,x1n, (ij,1i,jn) 第n行：xn1,xnn, (ij,1i,jn) 第1列：x11,xn1, (ij,1i,jn) 第n列：xn1,xnn, (ij,1i,jn),加上斜線：大家寫完。,每列只有一個(gè)取1： 每個(gè)斜線只有一個(gè)取1。 項(xiàng)個(gè)數(shù)，不超過(guò),時(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