第五講：易解問(wèn)題與難解問(wèn)題

1、2021/8/61 本章首先介紹一個(gè)對(duì)問(wèn)題進(jìn)行抽象的典型實(shí)例哥尼斯堡七橋問(wèn)題。然后，通過(guò)“梵天塔”問(wèn)題和“停機(jī)問(wèn)題”分別介紹學(xué)科中的可計(jì)算問(wèn)題和不可計(jì)算問(wèn)題。從“梵天塔”問(wèn)題再引出算法復(fù)雜性中的難解性問(wèn)題、P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題，證比求易算法，PNP是否成立的問(wèn)題。2021/8/621 哥尼斯堡七橋問(wèn)題17世紀(jì)的東普魯士有一座哥尼斯堡城，城中有一座奈佛夫島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個(gè)區(qū)域，全城共有7座橋?qū)?個(gè)城區(qū)相連起來(lái)。通過(guò)這7座橋到各城區(qū)游玩，問(wèn)題：尋找走遍這7座橋的路徑，要求過(guò)每座橋只許走一次，最后又回到原出發(fā)點(diǎn)。2021/8/63問(wèn)題的抽象1

2、736年，大數(shù)學(xué)家列昂納德歐拉（L.Euler）發(fā)表了關(guān)于“哥尼斯堡七橋問(wèn)題”的論文。他抽象出問(wèn)題最本質(zhì)的東西，忽視問(wèn)題非本質(zhì)的東西（如橋的長(zhǎng)度等），從而將哥尼斯堡七橋問(wèn)題抽象為一個(gè)數(shù)學(xué)問(wèn)題，即經(jīng)過(guò)圖中每邊一次且僅一次的回路問(wèn)題了。 D C B A 2021/8/64歐拉回路歐拉給出了哥尼斯堡七橋問(wèn)題 的證明，還用數(shù)學(xué)方法給出了三條判定規(guī)則(判定每座橋恰好走過(guò)一次,不一定回到原點(diǎn), 即對(duì)歐拉路徑的判定)：如果通奇數(shù)座橋的地方不止兩個(gè)，滿(mǎn)足要求的路線(xiàn)是找不到的。如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路線(xiàn)。如果沒(méi)有一個(gè)地方是通奇數(shù)座橋的，則無(wú)論從哪里出發(fā)，所要求的路線(xiàn)都

3、能實(shí)現(xiàn)。根據(jù)第3點(diǎn),可以得出,任一連通圖存在歐拉回路的充分必要條件是所有頂點(diǎn)均有偶數(shù)度.2021/8/65哈密爾頓回路問(wèn)題問(wèn)題：在某個(gè)圖G中，能不能找到這樣的路徑，即從一點(diǎn)出發(fā)不重復(fù)地走過(guò)所有的結(jié)點(diǎn)，最后又回到原出發(fā)點(diǎn)?！肮軤栴D回路問(wèn)題”與“歐拉回路問(wèn)題”的不同點(diǎn)“哈密爾頓回路問(wèn)題”是訪(fǎng)問(wèn)每個(gè)結(jié)點(diǎn)一次，而“歐拉回路問(wèn)題”是訪(fǎng)問(wèn)每條邊一次。對(duì)圖G是否存在“歐拉回路”前面已給出充分必要條件，而對(duì)圖G是否存在“哈密爾頓回路”至今仍未找到滿(mǎn)足該問(wèn)題的充分必要條件。2021/8/66圖論的形成和發(fā)展歐拉的論文為圖論的形成奠定了基礎(chǔ)。圖論已廣泛地應(yīng)用于計(jì)算學(xué)科運(yùn)籌學(xué)信息論控制論等學(xué)科圖論已成為我們對(duì)現(xiàn)實(shí)

4、問(wèn)題進(jìn)行抽象的一個(gè)強(qiáng)有力的數(shù)學(xué)工具。圖論在計(jì)算學(xué)科中的作用越來(lái)越大，圖論本身也得到了充分的發(fā)展。2021/8/672 可計(jì)算問(wèn)題與不可計(jì)算問(wèn)題 計(jì)算學(xué)科的問(wèn)題，無(wú)非就是計(jì)算問(wèn)題，從大的方面來(lái)說(shuō)，分可計(jì)算問(wèn)題與不可計(jì)算問(wèn)題?？捎?jì)算問(wèn)題是存在算法可解的問(wèn)題，不可計(jì)算問(wèn)題是不存在算法可解的問(wèn)題。 為便于理解，下面，分別以梵天塔（Hanoi，又譯為漢諾）問(wèn)題和停機(jī)問(wèn)題來(lái)介紹可計(jì)算問(wèn)題與不可計(jì)算問(wèn)題。2021/8/682.1排序問(wèn)題隨機(jī)給出n個(gè)數(shù)，要求對(duì)它們進(jìn)行排序。比如：8，2，7，6，4，12對(duì)于排序問(wèn)題，有多種算法。一種選擇排序算法是：從n個(gè)數(shù)中挑出最小的數(shù)，再?gòu)膎-1個(gè)數(shù)中挑出第二小的數(shù).那么，

5、在這些眾多的算法中，如何來(lái)比較誰(shuí)的速度更快？事后分析：機(jī)器的運(yùn)行時(shí)間？事前分析：與問(wèn)題規(guī)模有關(guān)的表達(dá)式，表示算法中基本操作的執(zhí)行次數(shù)。2021/8/69一種選擇排序算法是：從n個(gè)數(shù)中挑出最小的數(shù)，再?gòu)膎-1個(gè)數(shù)中挑出第二小的數(shù).時(shí)間復(fù)雜性與n有關(guān)，大概是n+(n-1)+1=1/2(n(n+1)，忽略常數(shù)項(xiàng)，取最大的指數(shù)，記為O(n2)。最快的算法是快速排序算法，時(shí)間復(fù)雜度為O(nlogn)。2021/8/6102.2 梵天塔問(wèn)題相傳印度教的天神梵天在創(chuàng)造地球這一世界時(shí)，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個(gè)銅座支撐。梵天將64個(gè)直徑大小不一的金盤(pán)子，按照從大到小的順序依次套放在第一根

6、柱子上，形成一座金塔（如圖2.3所示），即所謂的梵天塔（又稱(chēng)漢諾塔）。天神讓廟里的僧侶們將第一根柱子上的64個(gè)盤(pán)子借助第二根柱子全部移到第三根柱子上，即將整個(gè)塔遷移，同時(shí)定下3條規(guī)則：2021/8/611每次只能移動(dòng)一個(gè)盤(pán)子；盤(pán)子只能在三根柱子上來(lái)回移動(dòng)，不能放在他處；在移動(dòng)過(guò)程中，三根柱子上的盤(pán)子必須始終保持大盤(pán)在下，小盤(pán)在上。2021/8/612遞歸算法(重點(diǎn)掌握）遞歸是一種特別有用的工具,不僅在數(shù)學(xué)中廣泛應(yīng)用,在日常生活中也常常遇到。以下使用遞歸算法來(lái)解決梵塔問(wèn)題。2021/8/613遞歸算法在數(shù)學(xué)中幾個(gè)熟知的數(shù)學(xué)定義：在數(shù)學(xué)中幾個(gè)熟知的數(shù)學(xué)定義：1)!1(01!) 1 (nnnnn(2

7、) (2) 若若t1,t2t1,t2是樹(shù)，則是樹(shù)，則 也是樹(shù)也是樹(shù)1101) 3(111nCCnmnCnmnmnm2021/8/614遞歸遞歸算法包括遞歸算法包括遞推遞推和和回歸回歸兩部分：兩部分：遞推遞推就是為了得到問(wèn)題的解就是為了得到問(wèn)題的解, ,將它推到比原問(wèn)題更簡(jiǎn)單的問(wèn)題求解。將它推到比原問(wèn)題更簡(jiǎn)單的問(wèn)題求解。例如：例如：n!=f(n),n!=f(n),為了計(jì)算為了計(jì)算f(n),f(n),將它推到比原問(wèn)題更簡(jiǎn)單的問(wèn)題將它推到比原問(wèn)題更簡(jiǎn)單的問(wèn)題f(n-f(n-1),1),即即f(n)=f(n-1)f(n)=f(n-1)* *n,n,而計(jì)算而計(jì)算f(n-1)f(n-1)比計(jì)算比計(jì)算f(n

8、)f(n)簡(jiǎn)單簡(jiǎn)單, ,因?yàn)橐驗(yàn)閒(n-1)f(n-1)比比f(wàn)(n)f(n)更加接近已知解更加接近已知解0!=10!=1使用遞推要注意使用遞推要注意（1 1）遞推應(yīng)有終止之時(shí)）遞推應(yīng)有終止之時(shí), ,例如當(dāng)例如當(dāng)n=0n=0時(shí)時(shí),0!=1,0!=1為遞推終止條件為遞推終止條件, ,所謂終所謂終止條件就是指在此條件下問(wèn)題的解時(shí)明確的止條件就是指在此條件下問(wèn)題的解時(shí)明確的, ,缺少終止條件會(huì)使算法缺少終止條件會(huì)使算法失敗。失敗。（2 2）簡(jiǎn)單問(wèn)題表示離遞推終止條件更接近的問(wèn)題。簡(jiǎn)單的問(wèn)題與原）簡(jiǎn)單問(wèn)題表示離遞推終止條件更接近的問(wèn)題。簡(jiǎn)單的問(wèn)題與原問(wèn)題其解的算法是一致的問(wèn)題其解的算法是一致的, ,其差

9、別主要反映在參數(shù)上其差別主要反映在參數(shù)上, ,例如例如,f(n-1),f(n-1)比比計(jì)算計(jì)算f(n)f(n)更簡(jiǎn)單更簡(jiǎn)單, ,因?yàn)橐驗(yàn)閒(n-1)f(n-1)比比f(wàn)(n)f(n)參數(shù)少參數(shù)少1 1。參數(shù)變化使問(wèn)題遞推。參數(shù)變化使問(wèn)題遞推到有明確解。到有明確解。2021/8/615遞歸算法回歸回歸指當(dāng)簡(jiǎn)單問(wèn)題得到解后指當(dāng)簡(jiǎn)單問(wèn)題得到解后, ,回歸到原問(wèn)題的解上來(lái)。例如回歸到原問(wèn)題的解上來(lái)。例如, ,當(dāng)計(jì)算完當(dāng)計(jì)算完(n-1)!(n-1)!后后, ,回歸計(jì)算回歸計(jì)算n n* *(n-1)!,(n-1)!,即得到即得到n!n!的值。的值。使用回歸要注意使用回歸要注意（1 1）當(dāng)回歸到原問(wèn)題的解時(shí)）

10、當(dāng)回歸到原問(wèn)題的解時(shí), ,算法中所涉及的處理對(duì)象算法中所涉及的處理對(duì)象是關(guān)于當(dāng)前問(wèn)題的是關(guān)于當(dāng)前問(wèn)題的, ,即遞歸算法所涉及的參數(shù)與局部處即遞歸算法所涉及的參數(shù)與局部處理對(duì)象是有層次的。當(dāng)解一問(wèn)題的時(shí)候理對(duì)象是有層次的。當(dāng)解一問(wèn)題的時(shí)候, ,有它的一套參有它的一套參數(shù)與局部處理對(duì)象。當(dāng)遞推進(jìn)入一個(gè)數(shù)與局部處理對(duì)象。當(dāng)遞推進(jìn)入一個(gè) 簡(jiǎn)單問(wèn)題簡(jiǎn)單問(wèn)題 的時(shí)候。的時(shí)候。這套參數(shù)與局部對(duì)象便隱藏起來(lái)這套參數(shù)與局部對(duì)象便隱藏起來(lái), ,在解簡(jiǎn)單問(wèn)題的時(shí)候在解簡(jiǎn)單問(wèn)題的時(shí)候又有它自己的一套。當(dāng)回歸時(shí)又有它自己的一套。當(dāng)回歸時(shí), ,原問(wèn)題的一套參數(shù)與局原問(wèn)題的一套參數(shù)與局部處理對(duì)象又活躍起來(lái)了。部處理對(duì)象又活

11、躍起來(lái)了。（2 2）回歸到原問(wèn)題已經(jīng)得到問(wèn)題的解）回歸到原問(wèn)題已經(jīng)得到問(wèn)題的解, ,回歸并不引起其回歸并不引起其他動(dòng)作。他動(dòng)作。2021/8/616遞歸的例子計(jì)算n!根據(jù)公式 n!=1 當(dāng)n=0 =n*(n-1)! 當(dāng)n!=0函數(shù)參數(shù)為nint f(int n) if (!n) return 1; else return (n*f(n-1); 2021/8/617遞歸的例子斐波那契數(shù)列(fibonacci)f(0)=0f(1)=1f(n)=f(n-1)+f(n-2) (n=2)int f(int n) if (!n) return 0; elseif (n=1) return 1 ; else

12、 return(f(n-1)+f(n-2);2021/8/618梵塔問(wèn)題算法分析：算法分析：用用A A、B B、C C分別表示三根針?lè)謩e表示三根針將將n n個(gè)盤(pán)由個(gè)盤(pán)由A A移到移到C C上的操作步驟為：上的操作步驟為：（1 1）將）將A A上的上的n-1n-1個(gè)盤(pán)借助個(gè)盤(pán)借助C C移到移到B B上上（2 2）把）把A A上剩下的一個(gè)盤(pán)由上剩下的一個(gè)盤(pán)由A A移到移到C C上上（3 3）將）將B B上的上的n-1n-1個(gè)盤(pán)借助個(gè)盤(pán)借助A A移到移到C C上上這樣處理后這樣處理后, ,問(wèn)題的規(guī)模減少問(wèn)題的規(guī)模減少1 1。當(dāng)。當(dāng)n=1n=1的的時(shí)候，就可以直接處理了。時(shí)候，就可以直接處理了。202

13、1/8/619窮舉演算n = 3A B CA B CA B CA B C( 1 )( 2 ) A TO C( 3 ) A TO B(4) C TO B2021/8/620窮舉演算(續(xù)） A B C( 5 ) A TO C A B CA B CA B C( 6 ) B TO A (7 ) B TO C (8 ) A TO C 2021/8/621梵塔問(wèn)題:子程序/* 程序HANOI.C: 梵塔問(wèn)題-*/#include #define N 3void move(int from, int to) printf(From %c to %cn, from, to);void hanoi(int n,

14、 int p1, int p2, int p3) if(n=1) move(p1, p3); else hanoi(n-1, p1, p3, p2); move(p1, p3); hanoi(n-1, p2, p1, p3); /* 測(cè)試用主函數(shù) */ main() hanoi(N, A, B, C);2021/8/622當(dāng)n=64時(shí)，移動(dòng)次數(shù)=？花費(fèi)時(shí)間=？ h(n)=2h(n-1)+1 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 = 2n-1+22+2+1=2n-1需要移動(dòng)盤(pán)子的次數(shù)為： 264-1

15、=184467440737095516152021/8/623假定每秒移動(dòng)一次，一年有31536000秒，則僧侶們一刻不停地來(lái)回搬動(dòng)，也需要花費(fèi)大約5849億年的時(shí)間。假定計(jì)算機(jī)以每秒1000萬(wàn)個(gè)盤(pán)子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時(shí)間。這樣的問(wèn)題也稱(chēng)為難解問(wèn)題，雖然理論上可以解決，但是在n值比較大的情況下，計(jì)算時(shí)間太大。對(duì)于此類(lèi)問(wèn)題，人類(lèi)也一直在尋找是否有更快的計(jì)算算法。2021/8/6242.3 算法復(fù)雜性中的難解性問(wèn)題、P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題 算法復(fù)雜性包括算法的空間以及時(shí)間兩方面的復(fù)雜性問(wèn)題，梵天塔問(wèn)題主要講的是算法的時(shí)間復(fù)雜性。2021/8/625 關(guān)于梵天塔問(wèn)題算法的時(shí)間

16、復(fù)雜度，可以用一個(gè)指數(shù)函數(shù)O(2n)來(lái)表示，顯然，當(dāng)n很大（如10000）時(shí)，計(jì)算機(jī)是無(wú)法處理的。相反，當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式，如O(n2)時(shí)，則可以處理。因此，一個(gè)問(wèn)題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式（如指數(shù)函數(shù)）時(shí)，算法的執(zhí)行時(shí)間將隨n的增加而急劇增長(zhǎng)，以致即使是中等規(guī)模的問(wèn)題也不能求解出來(lái)，于是在計(jì)算復(fù)雜性中，將這一類(lèi)問(wèn)題稱(chēng)為難解性問(wèn)題。人工智能領(lǐng)域中的狀態(tài)圖搜索問(wèn)題（解空間的表示或狀態(tài)空間搜索問(wèn)題）就是一類(lèi)典型的難解性問(wèn)題。2021/8/626 在計(jì)算復(fù)雜性理論中，將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題稱(chēng)為P類(lèi)問(wèn)題，而將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問(wèn)題稱(chēng)為NP類(lèi)問(wèn)題。由于P

17、類(lèi)問(wèn)題采用的是確定性算法，NP類(lèi)問(wèn)題采用的是非確定性算法，而確定性算法是非確定性算法的一種特例，因此，可以斷定PNP。2021/8/6272.4 證比求易算法 為了更好地理解計(jì)算復(fù)雜性的有關(guān)概念，我國(guó)學(xué)者洪加威曾經(jīng)講了一個(gè)被人稱(chēng)為“證比求易算法”的童話(huà)，用來(lái)幫助讀者理解計(jì)算復(fù)雜性的有關(guān)概念，大致內(nèi)容如下。 從前，有一個(gè)酷愛(ài)數(shù)學(xué)的年輕國(guó)王艾述向鄰國(guó)一位聰明美麗的公主秋碧貞楠求婚。公主出了這樣一道題：求出48 770 428 433 377 171的一個(gè)真因子。若國(guó)王能在一天之內(nèi)求出答案，公主便接受他的求婚。2021/8/628 國(guó)王回去后立即開(kāi)始逐個(gè)數(shù)地進(jìn)行計(jì)算，他從早到晚，共算了三萬(wàn)多個(gè)數(shù)，最

18、終還是沒(méi)有結(jié)果。國(guó)王向公主求情，公主將答案相告：223 092 827是它的一個(gè)真因子。國(guó)王很快就驗(yàn)證了這個(gè)數(shù)確能除盡48 770 428 433 377 171。公主說(shuō)：“我再給你一次機(jī)會(huì)，如果還求不出，將來(lái)你只好做我的證婚人了?！?021/8/629 國(guó)王立即回國(guó)，并向時(shí)任宰相的大數(shù)學(xué)家孔喚石求教，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位，則最小的一個(gè)真因子不會(huì)超過(guò)9位，他給國(guó)王出了一個(gè)主意：按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)號(hào)發(fā)下去，等公主給出數(shù)目后，立即將它們通報(bào)全國(guó)，讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù)，除盡了立即上報(bào)，賞金萬(wàn)兩。2021/8/630順序算法和并行算法國(guó)王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時(shí)間方面，后面由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺(jué)上，我們認(rèn)為順序算法解決不了的問(wèn)題完全可以用并行算法來(lái)解決，甚至?xí)?，并行?jì)算機(jī)系統(tǒng)求解問(wèn)題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問(wèn)題，其實(shí)