第五講：易解問題與難解問題.

1、 本章首先介紹一個對問題進行抽象的典型實例哥尼斯堡七橋問題。然后，通過“梵天塔”問題和“停機問題”分別介紹學科中的可計算問題和不可計算問題。從“梵天塔”問題再引出算法復雜性中的難解性問題、P類問題和NP類問題，證比求易算法，PNP是否成立的問題。1 哥尼斯堡七橋問題17世紀的東普魯士有一座哥尼斯堡城，城中有一座奈佛夫島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個區(qū)域，全城共有7座橋將4個城區(qū)相連起來。通過這7座橋到各城區(qū)游玩，問題：尋找走遍這7座橋的路徑，要求過每座橋只許走一次，最后又回到原出發(fā)點。問題的抽象1736年，大數(shù)學家列昂納德歐拉（L.Euler）發(fā)表了

2、關于“哥尼斯堡七橋問題”的論文。他抽象出問題最本質的東西，忽視問題非本質的東西（如橋的長度等），從而將哥尼斯堡七橋問題抽象為一個數(shù)學問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。 D C B A 歐拉回路歐拉給出了哥尼斯堡七橋問題 的證明，還用數(shù)學方法給出了三條判定規(guī)則(判定每座橋恰好走過一次,不一定回到原點, 即對歐拉路徑的判定)：如果通奇數(shù)座橋的地方不止兩個，滿足要求的路線是找不到的。如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一出發(fā)，找到所要求的路線。如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路線都能實現(xiàn)。根據(jù)第3點,可以得出,任一連通圖存在歐拉回路的充分必要條件是所有

3、頂點均有偶數(shù)度.哈密爾頓回路問題問題：在某個圖G中，能不能找到這樣的路徑，即從一點出發(fā)不重復地走過所有的結點，最后又回到原出發(fā)點。“哈密爾頓回路問題”與“歐拉回路問題”的不同點“哈密爾頓回路問題”是訪問每個結點一次，而“歐拉回路問題”是訪問每條邊一次。對圖G是否存在“歐拉回路”前面已給出充分必要條件，而對圖G是否存在“哈密爾頓回路”至今仍未找到滿足該問題的充分必要條件。圖論的形成和發(fā)展歐拉的論文為圖論的形成奠定了基礎。圖論已廣泛地應用于計算學科運籌學信息論控制論等學科圖論已成為我們對現(xiàn)實問題進行抽象的一個強有力的數(shù)學工具。圖論在計算學科中的作用越來越大，圖論本身也得到了充分的發(fā)展。2 可計算問

4、題與不可計算問題 計算學科的問題，無非就是計算問題，從大的方面來說，分可計算問題與不可計算問題?？捎嬎銌栴}是存在算法可解的問題，不可計算問題是不存在算法可解的問題。 為便于理解，下面，分別以梵天塔（Hanoi，又譯為漢諾）問題和停機問題來介紹可計算問題與不可計算問題。2.1排序問題隨機給出n個數(shù)，要求對它們進行排序。比如：8，2，7，6，4，12對于排序問題，有多種算法。一種選擇排序算法是：從n個數(shù)中挑出最小的數(shù)，再從n-1個數(shù)中挑出第二小的數(shù).那么，在這些眾多的算法中，如何來比較誰的速度更快？事后分析：機器的運行時間？事前分析：與問題規(guī)模有關的表達式，表示算法中基本操作的執(zhí)行次數(shù)。一種選擇排

5、序算法是：從n個數(shù)中挑出最小的數(shù)，再從n-1個數(shù)中挑出第二小的數(shù).時間復雜性與n有關，大概是n+(n-1)+1=1/2(n(n+1)，忽略常數(shù)項，取最大的指數(shù)，記為O(n2)。最快的算法是快速排序算法，時間復雜度為O(nlogn)。2.2 梵天塔問題相傳印度教的天神梵天在創(chuàng)造地球這一世界時，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個銅座支撐。梵天將64個直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔（如圖2.3所示），即所謂的梵天塔（又稱漢諾塔）。天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，即將整個塔遷移，同時定下3條規(guī)則

6、：每次只能移動一個盤子；盤子只能在三根柱子上來回移動，不能放在他處；在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。12遞歸算法(重點掌握）遞歸是一種特別有用的工具,不僅在數(shù)學中廣泛應用,在日常生活中也常常遇到。以下使用遞歸算法來解決梵塔問題。13遞歸算法在數(shù)學中幾個熟知的數(shù)學定義：在數(shù)學中幾個熟知的數(shù)學定義：1)!1(01!) 1 (nnnnn(2) (2) 若若t1,t2t1,t2是樹，則是樹，則 也是樹也是樹1101) 3(111nCCnmnCnmnmnm14遞歸遞歸算法包括遞歸算法包括遞推遞推和和回歸回歸兩部分：兩部分：遞推遞推就是為了得到問題的解就是為了得到問題的解,將

7、它推到比原問題更簡單的問題求解。將它推到比原問題更簡單的問題求解。例如：例如：n!=f(n),為了計算為了計算f(n),將它推到比原問題更簡單的問題將它推到比原問題更簡單的問題f(n-1),即即f(n)=f(n-1)*n,而計算而計算f(n-1)比計算比計算f(n)簡單簡單,因為因為f(n-1)比比f(n)更加接更加接近已知解近已知解0!=1使用遞推要注意使用遞推要注意（1）遞推應有終止之時）遞推應有終止之時,例如當例如當n=0時時,0!=1為遞推終止條件為遞推終止條件,所謂終止所謂終止條件就是指在此條件下問題的解時明確的條件就是指在此條件下問題的解時明確的,缺少終止條件會使算法失缺少終止條件

8、會使算法失敗。敗。（2）簡單問題表示離遞推終止條件更接近的問題。簡單的問題與原）簡單問題表示離遞推終止條件更接近的問題。簡單的問題與原問題其解的算法是一致的問題其解的算法是一致的,其差別主要反映在參數(shù)上其差別主要反映在參數(shù)上,例如例如,f(n-1)比計比計算算f(n)更簡單更簡單,因為因為f(n-1)比比f(n)參數(shù)少參數(shù)少1。參數(shù)變化使問題遞推到有明。參數(shù)變化使問題遞推到有明確解。確解。15遞歸算法回歸回歸指當簡單問題得到解后指當簡單問題得到解后,回歸到原問題的解上來。例如回歸到原問題的解上來。例如,當計算完當計算完(n-1)!后后,回歸計算回歸計算n*(n-1)!,即得到即得到n!的值。的

9、值。使用回歸要注意使用回歸要注意（1）當回歸到原問題的解時）當回歸到原問題的解時,算法中所涉及的處理對象算法中所涉及的處理對象是關于當前問題的是關于當前問題的,即遞歸算法所涉及的參數(shù)與局部處即遞歸算法所涉及的參數(shù)與局部處理對象是有層次的。當解一問題的時候理對象是有層次的。當解一問題的時候,有它的一套參有它的一套參數(shù)與局部處理對象。當遞推進入一個數(shù)與局部處理對象。當遞推進入一個簡單問題簡單問題的時候。的時候。這套參數(shù)與局部對象便隱藏起來這套參數(shù)與局部對象便隱藏起來,在解簡單問題的時候在解簡單問題的時候又有它自己的一套。當回歸時又有它自己的一套。當回歸時,原問題的一套參數(shù)與局原問題的一套參數(shù)與局部

10、處理對象又活躍起來了。部處理對象又活躍起來了。（2）回歸到原問題已經(jīng)得到問題的解）回歸到原問題已經(jīng)得到問題的解,回歸并不引起其回歸并不引起其他動作。他動作。16遞歸的例子計算n!根據(jù)公式 n!=1 當n=0 =n*(n-1)! 當n!=0函數(shù)參數(shù)為nint f(int n) if (!n) return 1; else return (n*f(n-1); 17遞歸的例子斐波那契數(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 r

11、eturn(f(n-1)+f(n-2);18梵塔問題算法分析：算法分析：用用A A、B B、C C分別表示三根針分別表示三根針將將n n個盤由個盤由A A移到移到C C上的操作步驟為：上的操作步驟為：（1 1）將）將A A上的上的n-1n-1個盤借助個盤借助C C移到移到B B上上（2 2）把）把A A上剩下的一個盤由上剩下的一個盤由A A移到移到C C上上（3 3）將）將B B上的上的n-1n-1個盤借助個盤借助A A移到移到C C上上這樣處理后這樣處理后, ,問題的規(guī)模減少問題的規(guī)模減少1 1。當。當n=1n=1的的時候，就可以直接處理了。時候，就可以直接處理了。19窮舉演算n = 3A

12、B CA B CA B CA B C( 1 )( 2 ) A TO C( 3 ) A TO B(4) C TO B20窮舉演算(續(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 21梵塔問題:子程序/* 程序HANOI.C: 梵塔問題-*/#include #define N 3void move(int from, int to) printf(From %c to %cn, from, to);void hanoi(int n, int p1, int p2, int p3) if(n=1) m

13、ove(p1, p3); else hanoi(n-1, p1, p3, p2); move(p1, p3); hanoi(n-1, p2, p1, p3); /* 測試用主函數(shù) */ main() hanoi(N, A, B, C);當n=64時，移動次數(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需要移動盤子的次數(shù)為： 264-1=18446744073709551615假定每秒移動一次，一年有31536000秒，則

14、僧侶們一刻不停地來回搬動，也需要花費大約5849億年的時間。假定計算機以每秒1000萬個盤子的速度進行搬遷，則需要花費大約58490年的時間。這樣的問題也稱為難解問題，雖然理論上可以解決，但是在n值比較大的情況下，計算時間太大。對于此類問題，人類也一直在尋找是否有更快的計算算法。2.3 算法復雜性中的難解性問題、P類問題和NP類問題 算法復雜性包括算法的空間以及時間兩方面的復雜性問題，梵天塔問題主要講的是算法的時間復雜性。 關于梵天塔問題算法的時間復雜度，可以用一個指數(shù)函數(shù)O(2n)來表示，顯然，當n很大（如10000）時，計算機是無法處理的。相反，當算法的時間復雜度的表示函數(shù)是一個多項式，如

15、O(n2)時，則可以處理。因此，一個問題求解算法的時間復雜度大于多項式（如指數(shù)函數(shù)）時，算法的執(zhí)行時間將隨n的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，于是在計算復雜性中，將這一類問題稱為難解性問題。人工智能領域中的狀態(tài)圖搜索問題（解空間的表示或狀態(tài)空間搜索問題）就是一類典型的難解性問題。 在計算復雜性理論中，將所有可以在多項式時間內(nèi)求解的問題稱為P類問題，而將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題。由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，而確定性算法是非確定性算法的一種特例，因此，可以斷定PNP。2.4 證比求易算法 為了更好地理解計算復雜性的有

16、關概念，我國學者洪加威曾經(jīng)講了一個被人稱為“證比求易算法”的童話，用來幫助讀者理解計算復雜性的有關概念，大致內(nèi)容如下。 從前，有一個酷愛數(shù)學的年輕國王艾述向鄰國一位聰明美麗的公主秋碧貞楠求婚。公主出了這樣一道題：求出48 770 428 433 377 171的一個真因子。若國王能在一天之內(nèi)求出答案，公主便接受他的求婚。 國王回去后立即開始逐個數(shù)地進行計算，他從早到晚，共算了三萬多個數(shù)，最終還是沒有結果。國王向公主求情，公主將答案相告：223 092 827是它的一個真因子。國王很快就驗證了這個數(shù)確能除盡48 770 428 433 377 171。公主說：“我再給你一次機會，如果還求不出，將

17、來你只好做我的證婚人了。” 國王立即回國，并向時任宰相的大數(shù)學家孔喚石求教，大數(shù)學家在仔細地思考后認為這個數(shù)為17位，則最小的一個真因子不會超過9位，他給國王出了一個主意：按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去，等公主給出數(shù)目后，立即將它們通報全國，讓每個老百姓用自己的編號去除這個數(shù)，除盡了立即上報，賞金萬兩。順序算法和并行算法國王最先使用的是一種順序算法，其復雜性表現(xiàn)在時間方面，后面由宰相提出的是一種并行算法，其復雜性表現(xiàn)在空間方面。直覺上，我們認為順序算法解決不了的問題完全可以用并行算法來解決，甚至會想，并行計算機系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解

18、性問題，其實這是一種誤解。當將一個問題分解到多個處理器上解決時，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計算機系統(tǒng)的加速能力。阿達爾定律設f為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比，p為處理器的數(shù)目，Sp為并行計算機系統(tǒng)最大的加速能力，則 設f=1%，p，則Sp=100。串行執(zhí)行操作僅占全部操作1%，解題速度最多也只能提高一百倍。對難解性問題而言，提高計算機系統(tǒng)的速度是遠遠不夠的，而降低算法復雜度的數(shù)量級才是最關鍵的問題。2.5 P NP ？ P類問題存在多項式時間的算法的一類問題；NP類問題非多項式時間算法解的一類問題。像梵塔問題、推銷員旅行問題、（命題表達