【學(xué)習課件】第9章NP完全性理論與近似算法計算機算法設(shè)計與分析（第3版）教學(xué)

1、 第9章 NP完全性理論與近似算法1編輯ppt學(xué)習要點理解RAM，RASP和圖靈機計算模型理解非確定性圖靈機的概念理解P類與NP類語言的概念 理解NP完全問題的概念理解近似算法的性能比及多項式時間近似格式的概念通過范例學(xué)習NP完全問題的近似算法（1）頂點覆蓋問題；（2）旅行售貨員問題；（3）集合覆蓋問題；（4）子集和問題。2編輯ppt9.1計算模型在進行問題的計算復(fù)雜性分析之前，首先必須建立求解問題所用的計算模型，包括定義該計算模型中所用的基本運算。建立計算模型的目的是為了使問題的計算復(fù)雜性分析有一個共同的客觀尺度。3個基本計算模型：隨機存取機RAM(Random Access Machine

2、)；隨機存取存儲程序機RASP(Random Access Stored Program Machine)圖靈機(Turing Machine)。這3個計算模型在計算能力上是等價的，但在計算速度上是不同的。3編輯ppt9.1.1 隨機存取機RAM1、RAM的結(jié)構(gòu)4編輯ppt9.1.1 隨機存取機RAM2、RAM程序 一個RAM程序定義了從輸入帶到輸出帶的一個映射?？梢詫@種映射關(guān)系作2種不同的解釋。解釋一：把RAM程序看成是計算一個函數(shù)若一個RAM程序P總是從輸入帶前n個方格中讀入n個整數(shù)x1，x2，xn，并且在輸出帶的第一個方格上輸出一個整數(shù)y后停機，那么就說程序P計算了函數(shù)f(x1，x2，

3、xn)=y 解釋二：把RAM程序當作一個語言接受器。將字符串S=a1a2an放在輸入帶上。在輸入帶的第一個方格中放入符號a1，第二個方格中放入符號a2，第n個方格中放入符號an。然后在第n+1個方格中放入0，作為輸入串的結(jié)束標志符。如果一個RAM程序P讀了字符串S及結(jié)束標志符0后，在輸出帶的第一格輸出一個1并停機，就說程序P接受字符串S。 5編輯ppt9.1.1 隨機存取機RAM3、 RAM程序的耗費標準標準一：均勻耗費標準在均勻耗費標準下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間。以后除特別注明，RAM程序的復(fù)雜性將按照均勻耗費標準衡量。 標準二：對數(shù)耗費標準對數(shù)耗費標準是

4、基于這樣的假定，即執(zhí)行一條指令的耗費與以二進制表示的指令的操作數(shù)長度成比例。在RAM計算模型下，假定一個寄存器可存放一個任意大小的整數(shù)。因此若設(shè)l(i)是整數(shù)i所占的二進制位數(shù)，則 6編輯ppt9.1.2 隨機存取存儲程序機RASP1、RASP的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據(jù)2個連續(xù)的寄存器。第一個寄存器存放操作碼的編碼，第二個寄存器存放地址。RASP指令用整數(shù)進行編碼。 2、RASP程序的復(fù)雜性不管是在均勻耗費標準下，還是在對數(shù)耗費標準下，RAM程序和RASP程序的復(fù)雜性只差一個常數(shù)因子。在一個計算模型下T(n)時間內(nèi)完成

5、的輸入-輸出映射可在另一個計算模型下模擬，并在kT(n)時間內(nèi)完成。其中k是一個常數(shù)因子?？臻g復(fù)雜性的情況也是類似的。 7編輯ppt9.1.3 圖靈機8編輯ppt9.1.3 圖靈機 根據(jù)有限狀態(tài)控制器的當前狀態(tài)及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現(xiàn)下面3個操作之一或全部。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (2)清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。 (3)獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當前單元不動(S)。 k帶圖靈機可形式化地描述為一個7元組(Q，T，I，b，q0，qf)，其中:(1)Q是有限個狀態(tài)的集合。 (2

6、)T是有限個帶符號的集合。(3)I是輸入符號的集合，IT。(4)b是唯一的空白符，bT-I。(5)q0是初始狀態(tài)。 (6)qf是終止(或接受)狀態(tài)。(7)是移動函數(shù)。它是從QTk的某一子集映射到Q (TL，R，S)k的函數(shù)。 9編輯ppt9.1.3 圖靈機圖靈機M的時間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數(shù)。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。 圖靈機的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。 與RAM模型類似，圖靈機既可作為語言接受器，也可作為計

7、算函數(shù)的裝置。 10編輯ppt9.2P類與NP類問題一般地說，將可由多項式時間算法求解的問題看作是易處理的問題，而將需要超多項式時間才能求解的問題看作是難處理的問題。有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項式時間算法，也沒有人能夠證明這些問題需要超多項式時間下界。在圖靈機計算模型下，這類問題的計算復(fù)雜性至今未知。為了研究這類問題的計算復(fù)雜性，人們提出了另一個能力更強的計算模型，即非確定性圖靈機計算模型，簡記為NDTM(Nondeterministic Turing Machine)。在非確定性圖靈機計算模型下，許多問題可以在多項式時間

8、內(nèi)求解。11編輯ppt9.2.1 非確定性圖靈機非確定性圖靈機（ NDTM ）：一個k帶的非確定性圖靈機M是一個7元組：(Q，T，I，b，q0，qf)。與確定性圖靈機不同的是非確定性圖靈機允許移動函數(shù)具有不確定性，即對于QTk中的每一個值(q;x1,x2,xk)，當它屬于的定義域時，Q(TL，R，S)k中有唯一的一個子集(q;x1,x2,xk)與之對應(yīng)?？梢栽?q;x1,x2,xk)中隨意選定一個值作為它的函數(shù)值。在圖靈機計算模型中，移動函數(shù)是單值的，即對于QTk中的每一個值，當它屬于的定義域時，Q(TL，R，S)k中只有唯一的值與之對應(yīng)，稱這種圖靈機為確定性圖靈機，簡記為DTM(Determ

9、inistic Turing Machine)。 12編輯ppt9.2.2 P類與NP類語言 P類和NP類語言的定義： P=L|L是一個能在多項式時間內(nèi)被一臺DTM所接受的語言 NP=L|L是一個能在多項式時間內(nèi)被一臺NDTM所接受的語言由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內(nèi)被確定性圖靈機接受的語言也可在多項式時間內(nèi)被非確定性圖靈機接受。故P NP。 13編輯ppt9.2.2 P類與NP類語言 NP類語言舉例無向圖的團問題。 該問題的輸入是一個有n個頂點的無向圖G=(V，E)和一個整數(shù)k。要求判定圖G是否包含一個k頂點的完全子圖(團)，即判定是否存在VV，|V|

10、=k，且對于所有的u，vV，有(u，v)E。 若用鄰接矩陣表示圖G，用二進制串表示整數(shù)k，則團問題的一個實例可以用長度為 的二進位串表示。因此，團問題可表示為語言： CLIQUE=w#v|w，v0，1*，以w為鄰接矩陣的圖G有一個k頂點的團，其中v是k的二進制表示。 14編輯ppt9.2.2 P類與NP類語言 接受該語言CLIQUE的非確定性算法：用非確定性選擇指令選出包含k個頂點的候選頂點子集V，然后確定性地檢查該子集是否是團問題的一個解。算法分為3個階段： 算法的第一階段將輸入串w#v分解，并計算出n= ，以及用v表示的整數(shù)k。若輸入不具有形式w#v或|w|不是一個平方數(shù)就拒絕該輸入。顯而

11、易見，第一階段可 在時間內(nèi)完成。 在算法的第二階段中，非確定性地選擇V的一個k元子集VV。 算法的第三階段是確定性地檢查V的團性質(zhì)。若V是一個團則接受輸入，否則拒絕輸入。這顯然可以在 時間內(nèi)完成。因此，整個算法的時間復(fù)雜性為 。非確定性算法在多項式時間內(nèi)接受語言CLIQUE，故CLIQUENP。 15編輯ppt9.2.3 多項式時間驗證 VP=L|L*，為一有限字符集，存在一個多項式p和一個多項式時間驗證算法A(X，Y)使得對任意X*，XL當且僅當存在Y*，|Y|p(|X|)且A(X，Y)=1。 多項式時間可驗證語言類VP可定義為： 定理9-1：VP=NP。 例如(哈密頓回路問題)：一個無向圖

12、G含有哈密頓回路嗎? 無向圖G的哈密頓回路是通過G的每個頂點恰好一次的簡單回路?？捎谜Z言HAM-CYCLE 定義該問題如下：HAM-CYCLE=G|G含有哈密頓回路 16編輯ppt9.3NP完全問題PNP。直觀上看，P類問題是確定性計算模型下的易解問題類，而NP類問題是非確定性計算模型下的易驗證問題類。大多數(shù)的計算機科學(xué)家認為NP類中包含了不屬于P類的語言，即PNP。NP完全問題有一種令人驚奇的性質(zhì)，即如果一個NP完全問題能在多項式時間內(nèi)得到解決，那么NP中的每一個問題都可以在多項式時間內(nèi)求解，即P=NP。目前還沒有一個NP完全問題有多項式時間算法。17編輯ppt9.3.1 多項式時間變換 定

13、義：語言L是NP完全的當且僅當 (1)LNP； (2)對于所有LNP有L p L。 如果有一個語言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語言是NP難的。所有NP完全語言構(gòu)成的語言類稱為NP完全語言類，記為NPC。 設(shè) ， 是2個語言。所謂語言 能在多項式時間內(nèi)變換為語言 (簡記為 p )是指存在映身f: ，且f滿足： (1)有一個計算f的多項式時間確定性圖靈機； (2)對于所有x ，x ，當且僅當f(x) 。 18編輯ppt9.3.1 多項式時間變換 定理9-2：設(shè)L是NP完全的，則 (1)LP當且僅當PNP； (2)若Lp ，且 NP，則 是NP完全的。 定理的(2)可用來證明

14、問題的NP完全性。但前提是：要有第一個NP完全問題L。19編輯ppt9. 3.2 一些典型的NP完全問題部分NP完全問題樹20編輯ppt 迄今為止，所有的NP完全問題都還沒有多項式時間算法。對于這類問題，通?？刹扇∫韵聨追N解題策略。(1)只對問題的特殊實例求解(2)用動態(tài)規(guī)劃法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用啟發(fā)式方法求解 9.4 NP完全問題的近似算法21編輯ppt9.4.1 近似算法的性能 若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標函數(shù)值為c，則將該近似算法的性能比定義為= 。在通常情況下，該性能比是問題輸入規(guī)模n的一

15、個函數(shù)(n)，即 (n)。該近似算法的相對誤差定義為= 。若對問題的輸入規(guī)模n，有一函數(shù)(n)使得 (n)，則稱(n)為該近似算法的相對誤差界。近似算法的性能比(n)與相對誤差界(n)之間顯然有如下關(guān)系：(n)(n)-1。 22編輯ppt9.4.2 頂點覆蓋問題的近似算法 問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集VV，使得若(u,v)是G的一條邊，則vV或uV。頂點覆蓋V的大小是它所包含的頂點個數(shù)|V|。 VertexSet approxVertexCover ( Graph g ) cset=； e1=g.e； while (e1 != ) 從e1中任取一條邊(u,v

16、)； cset=csetu,v； 從e1中刪去與u和v相關(guān)聯(lián)的所有邊； return c Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。 23編輯ppt9.4.2 頂點覆蓋問題的近似算法 圖(a)(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。 算法approxVertexCover的性能比為2。 24編輯ppt9.4.3 旅行售貨

17、員問題近似算法 問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。 比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,wV，有：c(u,w)c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。 旅行售貨員問題的一些特殊性質(zhì)：25編輯ppt1 滿足三角不等式的旅行售貨員問題 對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。 void approxTSP (Graph g) (1)選擇g

18、的任一頂點r； (2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹T； (3)前序遍歷樹T得到的頂點表L； (4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結(jié)果返回； 當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。 26編輯ppt(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。 27編輯ppt2 一般的旅行售貨員問題 在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項式時間近似算法，除非P=NP。換句話說

19、，若PNP，則對任意常數(shù)1，不存在性能比為的解旅行售貨員問題的多項式時間近似算法。 28編輯ppt9.4.4 集合覆蓋問題的近似算法 問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。 集合覆蓋問題的一個實例X,F由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬于F中的一個子集，即X= 。對于F中的一個子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得 |C*|=min|C|CF且C覆蓋X 29編輯ppt9.4.4 集

20、合覆蓋問題的近似算法集合覆蓋問題舉例：用12個黑點表示集合X。F=S1,S2,S3,S4,S5,S6,，如圖所示。容易看出，對于這個例子，最小集合覆蓋為：C=S3,S4,S5,。 30編輯ppt9.4.4 集合覆蓋問題的近似算法集合覆蓋問題近似算法貪心算法 算法的循環(huán)體最多執(zhí)行min|X|，|F|次。而循環(huán)體內(nèi)的計算顯然可在O(|X|F|)時間內(nèi)完成。因此，算法的計算時間為O(|X|F|min|X|，|F|)。由此即知，該算法是一個多項式時間算法。 Set greedySetCover (X,F) U=X； C=； while (U !=) 選擇F中使|SU|最大的子集S； U=U-S； C=CS； return C； 31編輯ppt9.4.5 子集和問題的近似算法 問題描述：設(shè)子集和問題的一個實例為S,t。其中，S=x1，x2，xn是一個正整數(shù)的集合，t是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得 。32編輯ppt1 子集和問題的指數(shù)時間算法int exactSubsetSum (S,t) int n=|S|； L0=0； for (int i=1；i=n；i+) Li=mergeLists(Li-1,Li-1+Si)； 刪去Li中超過t的元素； return max(Ln