計(jì)算機(jī)算法設(shè)計(jì)與實(shí)現(xiàn)王曉東主編第三版PPT第9章NP完全性理論與近似算法

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

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

3、出一個(gè)整數(shù)y后停機(jī)，那么就說程序P計(jì)算了函數(shù)f(xf(x1 1，x x2 2，x xn n)=y )=y 解釋二：把解釋二：把RAMRAM程序當(dāng)作一個(gè)語言接受器。程序當(dāng)作一個(gè)語言接受器。將字符串S=a1a2an放在輸入帶上。在輸入帶的第一個(gè)方格中放入符號a1，第二個(gè)方格中放入符號a2，第n個(gè)方格中放入符號an。然后在第n+1個(gè)方格中放入0，作為輸入串的結(jié)束標(biāo)志符。如果一個(gè)RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出帶的第一格輸出一個(gè)1并停機(jī)，就說程序P接受字符串S。 69.1.1 隨機(jī)存取機(jī)RAM3、 RAMRAM程序的耗費(fèi)標(biāo)準(zhǔn)程序的耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn)在均勻耗

4、費(fèi)標(biāo)準(zhǔn)下，每條RAM指令需要一個(gè)單位時(shí)間；每個(gè)寄存器占用一個(gè)單位空間。以后除特別注明，RAM程序的復(fù)雜性將按照均勻耗費(fèi)標(biāo)準(zhǔn)衡量。 標(biāo)準(zhǔn)二：對數(shù)耗費(fèi)標(biāo)準(zhǔn)標(biāo)準(zhǔn)二：對數(shù)耗費(fèi)標(biāo)準(zhǔn)對數(shù)耗費(fèi)標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費(fèi)與以二進(jìn)制表示的指令的操作數(shù)長度成比例。在RAM計(jì)算模型下，假定一個(gè)寄存器可存放一個(gè)任意大小的整數(shù)。因此若設(shè)l(i)是整數(shù)i所占的二進(jìn)制位數(shù)，則 001|log)(iiiil79.1.2 隨機(jī)存取存儲程序機(jī)RASP1、RASPRASP的結(jié)構(gòu)的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據(jù)2個(gè)連續(xù)的寄存器。第一個(gè)寄存器存放操作

5、碼的編碼，第二個(gè)寄存器存放地址。RASP指令用整數(shù)進(jìn)行編碼。 2、RASPRASP程序程序的復(fù)雜性的復(fù)雜性不管是在均勻耗費(fèi)標(biāo)準(zhǔn)下，還是在對數(shù)耗費(fèi)標(biāo)準(zhǔn)下，RAM程序和RASP程序的復(fù)雜性只差一個(gè)常數(shù)因子。在一個(gè)計(jì)算模型下T(n)時(shí)間內(nèi)完成的輸入-輸出映射可在另一個(gè)計(jì)算模型下模擬，并在kT(n)時(shí)間內(nèi)完成。其中k是一個(gè)常數(shù)因子。空間復(fù)雜性的情況也是類似的。 89.1.3 圖靈機(jī)99.1.3 圖靈機(jī) 根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個(gè)讀寫頭讀到的帶符號，圖靈機(jī)的一個(gè)計(jì)算步可實(shí)現(xiàn)下面3個(gè)操作之一或全部。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (2)清除當(dāng)前讀寫頭下的方格中原有帶符號并寫上新的帶符號。 (

6、3)獨(dú)立地將任何一個(gè)或所有讀寫頭，向左移動(dòng)一個(gè)方格(L)或向右移動(dòng)一個(gè)方格(R)或停在當(dāng)前單元不動(dòng)(S)。 k帶圖靈機(jī)可形式化地描述為一個(gè)7元組(Q，T，I，b，q0，qf)，其中:(1)Q是有限個(gè)狀態(tài)的集合。 (2)T是有限個(gè)帶符號的集合。(3)I是輸入符號的集合，IT。(4)b是唯一的空白符，bT-I。(5)q0是初始狀態(tài)。 (6)qf是終止(或接受)狀態(tài)。(7)是移動(dòng)函數(shù)。它是從QTk的某一子集映射到Q (TL，R，S)k的函數(shù)。 109.1.3 圖靈機(jī)圖靈機(jī)M的時(shí)間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計(jì)算步數(shù)。如果對某個(gè)長度為n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個(gè)n值無定

7、義。 圖靈機(jī)的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的總和。如果某個(gè)讀寫頭無限地向右移動(dòng)而不停機(jī)，S(n)也無定義。 與RAM模型類似，圖靈機(jī)既可作為語言接受器，也可作為計(jì)算函數(shù)的裝置。 119.2 P類與NP類問題n一般地說，將可由多項(xiàng)式時(shí)間算法求解的問題看作是易處理的問題，而將需要超多項(xiàng)式時(shí)間才能求解的問題看作是難處理的問題。n有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項(xiàng)式時(shí)間算法，也沒有人能夠證明這些問題需要超多項(xiàng)式時(shí)間下界。n在圖靈機(jī)計(jì)算模型下，這類問題的計(jì)算復(fù)雜性至今未知。n為了研究這類問題的

8、計(jì)算復(fù)雜性，人們提出了另一個(gè)能力更強(qiáng)的計(jì)算模型，即非確定性圖靈機(jī)計(jì)算模型，簡記為NDTM(Nondeterministic Turing Machine)。n在非確定性圖靈機(jī)計(jì)算模型下，許多問題可以在多項(xiàng)式時(shí)間內(nèi)求解。129.2.1 非確定性圖靈機(jī)非確定性圖靈機(jī)非確定性圖靈機(jī)（ NDTMNDTM ）：一個(gè)k帶的非確定性圖靈機(jī)M是一個(gè)7元組：(Q，T，I，b，q0，qf)。與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動(dòng)函數(shù)具有不確定性具有不確定性，即對于QTk中的每一個(gè)值(q;x1,x2,xk)，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中有唯一的一個(gè)子集子集(q;x1,x2,xk)與之對應(yīng)。可以在

9、(q;x1,x2,xk)中隨意選定一個(gè)值作為它的函數(shù)值。在圖靈機(jī)計(jì)算模型中，移動(dòng)函數(shù)是單值的是單值的，即對于QTk中的每一個(gè)值，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中只有唯一的值與之對應(yīng)，稱這種圖靈機(jī)為確定性圖靈機(jī)確定性圖靈機(jī)，簡記為DTMDTM(Deterministic Turing Machine)。 139.2.2 P類與NP類語言 P類和NP類語言的定義： P=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)多項(xiàng)式時(shí)間內(nèi)被一臺DTMDTM所接受的語言 NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間內(nèi)被一臺NDTMNDTM所接受的語言由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被

10、確定性圖靈機(jī)接受的語言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。故P P NP NP。 149.2.2 P類與NP類語言 NPNP類語言舉例類語言舉例無向圖的團(tuán)問題無向圖的團(tuán)問題。 該問題的輸入是一個(gè)有n個(gè)頂點(diǎn)的無向圖G=(V，E)和一個(gè)整數(shù)k。要求判定圖G是否包含一個(gè)k頂點(diǎn)的完全子完全子圖圖( (團(tuán)團(tuán)) )，即判定是否存在VV，|V|=k，且對于所有的u，vV，有(u，v)E。 若用鄰接矩陣表示圖G，用二進(jìn)制串表示整數(shù)k，則團(tuán)問題的一個(gè)實(shí)例可以用長度為 的二進(jìn)位串表示。因此，團(tuán)問題可表示為語言： CLIQUE=w#v|w，v0，1*，以w為鄰接矩陣的圖G有一個(gè)k頂點(diǎn)的團(tuán)，其中v是k的二進(jìn)制表示

11、。 1log2kn159.2.2 P類與NP類語言 接受該語言CLIQUE的非確定性算法非確定性算法：用非確定性選擇指令選出包含k個(gè)頂點(diǎn)的候選頂點(diǎn)子集V，然后確定性地檢查該子集是否是團(tuán)問題的一個(gè)解。算法分為3個(gè)階段： 算法的第一階段將輸入串w#v分解，并計(jì)算出n= ，以及用v表示的整數(shù)k。若輸入不具有形式w#v或|w|不是一個(gè)平方數(shù)就拒絕該輸入。顯而易見，第一階段可 在時(shí)間內(nèi)完成。| w)(2nO 在算法的第二階段中，非確定性地選擇V的一個(gè)k元子集VV。 算法的第三階段是確定性地檢查V的團(tuán)性質(zhì)。若V是一個(gè)團(tuán)則接受輸入，否則拒絕輸入。這顯然可以在 時(shí)間內(nèi)完成。因此，整個(gè)算法的時(shí)間復(fù)雜性為 。)(

12、4nO)(4nO非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語言CLIQUE，故CLIQUENP。 169.2.3 多項(xiàng)式時(shí)間驗(yàn)證 VP=L|L*，為一有限字符集，存在一個(gè)多項(xiàng)式p和一個(gè)多項(xiàng)式時(shí)間驗(yàn)證算法A(X，Y)使得對任意X*，XL當(dāng)且僅當(dāng)存在Y*，|Y|p(|X|)且A(X，Y)=1。 多項(xiàng)式時(shí)間可驗(yàn)證語言類VP可定義為： 定理定理9-19-1：VP=NP。 例如(哈密頓回路問題哈密頓回路問題)：一個(gè)無向圖G含有哈密頓回路嗎? 無向圖G的哈密頓回路是通過G的每個(gè)頂點(diǎn)恰好一次的簡單回路?？捎谜Z言HAM-CYCLE 定義該問題如下：HAM-CYCLE=G|G含有哈密頓回路 179.3 NP完全問題nPNP

13、。n直觀上看，P類問題是確定性計(jì)算模型下的易解問題類，而NP類問題是非確定性計(jì)算模型下的易驗(yàn)證問題類。n大多數(shù)的計(jì)算機(jī)科學(xué)家認(rèn)為NP類中包含了不屬于P類的語言，即PNP。nNP完全問題有一種令人驚奇的性質(zhì)，即如果一個(gè)NP完全問題能在多項(xiàng)式時(shí)間內(nèi)得到解決，那么NP中的每一個(gè)問題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP。n目前還沒有一個(gè)NP完全問題有多項(xiàng)式時(shí)間算法。189.3.1 多項(xiàng)式時(shí)間變換 定義：定義：語言L是NP完全的當(dāng)且僅當(dāng) (1)LNP； (2)對于所有LNP有L p L。 如果有一個(gè)語言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語言是NPNP難難的。所有NP完全語言構(gòu)成的語言類

14、稱為NPNP完全完全語言類語言類，記為NPCNPC。 設(shè) ， 是2個(gè)語言。所謂語言 能在多項(xiàng)式時(shí)間內(nèi)變換為語言 (簡記為 p )是指存在映身f: ，且f滿足： (1)有一個(gè)計(jì)算f的多項(xiàng)式時(shí)間確定性圖靈機(jī)； (2)對于所有x ，x ，當(dāng)且僅當(dāng)f(x) 。 *11L*22L1L2L1L2L*2*11L2L*1199.3.1 多項(xiàng)式時(shí)間變換 定理定理9-29-2：設(shè)L是NP完全的，則 (1)LP當(dāng)且僅當(dāng)PNP； (2)若Lp ，且 NP，則 是NP完全的。 1L1L1L定理的定理的(2)(2)可用來可用來證明問題的證明問題的NPNP完全完全性。但前提是：要性。但前提是：要有第一個(gè)有第一個(gè)NPNP完全

15、問完全問題題L L。209. 3.2 一些典型的NP完全問題部分NP完全問題樹21 迄今為止，所有的NP完全問題都還沒有多項(xiàng)式時(shí)間算法。對于這類問題，通常可采取以下幾種解題策略。(1)只對問題的特殊實(shí)例求解(2)用動(dòng)態(tài)規(guī)劃法或分支限界法求解 (3)用概率算法求解 (4)只求近似解(5)用啟發(fā)式方法求解 9.4 NP完全問題的近似算法229.4.1 近似算法的性能 若一個(gè)最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個(gè)近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比近似算法的性能比定義為= 。在通常情況下，該性能比是問題輸入規(guī)模n的一個(gè)函數(shù)(n)，即 (n)。cccc*,*maxc

16、ccc*,*max該近似算法的相對誤差近似算法的相對誤差定義為= 。若對問題的輸入規(guī)模n，有一函數(shù)(n)使得 (n)，則稱(n)為該近似算法的相對誤差界近似算法的相對誤差界。近似算法的性能比(n)與相對誤差界(n)之間顯然有如下關(guān)系：(n)(n)(n)-1(n)-1。 *ccc *ccc 239.4.2 頂點(diǎn)覆蓋問題的近似算法 問題描述：無向圖G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集V的一個(gè)子集VV，使得若(u,v)是G的一條邊，則vV或uV。頂點(diǎn)覆蓋V的大小是它所包含的頂點(diǎn)個(gè)數(shù)|V|。 VertexSet approxVertexCoverapproxVertexCover ( Graph g

17、) cset=； e1=g.e； while (e1 != ) 從e1中任取一條邊(u,v)； cset=csetu,v； 從e1中刪去與u和v相關(guān)聯(lián)的所有邊； return c CsetCset用來存儲頂點(diǎn)用來存儲頂點(diǎn)覆蓋中的各頂點(diǎn)。初覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集始為空，不斷從邊集e1e1中選取一邊中選取一邊( (u,v)u,v)，將邊的端點(diǎn)加入將邊的端點(diǎn)加入csetcset中，并將中，并將e1e1中已被中已被u u和和v v覆蓋的邊刪去，覆蓋的邊刪去，直至直至csetcset已覆蓋所有已覆蓋所有邊。即邊。即e1e1為空。為空。 249.4.2 頂點(diǎn)覆蓋問題的近似算法 圖圖( (a)

18、a)(e)(e)說明說明了算法的運(yùn)行過程了算法的運(yùn)行過程及結(jié)果。及結(jié)果。( (e)e)表示表示算法產(chǎn)生的近似最算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋優(yōu)頂點(diǎn)覆蓋csetcset，它由頂點(diǎn)它由頂點(diǎn)b,c,d,e,f,gb,c,d,e,f,g所組所組成。成。( (f)f)是圖是圖G G的一的一個(gè)最小頂點(diǎn)覆蓋，個(gè)最小頂點(diǎn)覆蓋，它只含有它只含有3 3個(gè)頂點(diǎn)：個(gè)頂點(diǎn)：b,db,d和和e e。 算法approxVertexCoverapproxVertexCover的性能比為2。 259.4.3 旅行售貨員問題近似算法 問題描述：給定一個(gè)完全無向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出

19、G的最小費(fèi)用哈密頓回路。 比如，費(fèi)用函數(shù)c往往具有三角不等式性質(zhì)三角不等式性質(zhì)，即對任意的3個(gè)頂點(diǎn)u,v,wV，有：c(u,w)c(u,v)+c(v,w)。當(dāng)圖G中的頂點(diǎn)就是平面上的點(diǎn)，任意2頂點(diǎn)間的費(fèi)用就是這2點(diǎn)間的歐氏距離時(shí)，費(fèi)用函數(shù)c就具有三角不等式性質(zhì)。 旅行售貨員問題的一些特殊性質(zhì)特殊性質(zhì)：261 滿足三角不等式的旅行售貨員問題滿足三角不等式的旅行售貨員問題 對于給定的無向圖G，可以利用找圖圖G G的最小生成樹的最小生成樹的算法設(shè)計(jì)找近似最優(yōu)的旅行售貨員回路的算法。 void approxTSPapproxTSP (Graph g) (1)選擇g的任一頂點(diǎn)r； (2)用Prim算法找

20、出帶權(quán)圖g的一棵以r為根的最小生成樹T； (3)前序遍歷樹T得到的頂點(diǎn)表L； (4)將r加到表L的末尾，按表L中頂點(diǎn)次序組成回路H，作為計(jì)算結(jié)果返回； 當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)，算法找出的旅行售貨員回路的費(fèi)用不會超過最優(yōu)旅行售貨員回路費(fèi)用的2倍。 27( (b)b)表示找到的最小生成表示找到的最小生成樹樹T T；( (c)c)表示對表示對T T作前序作前序遍歷的次序；遍歷的次序；(d)(d)表示表示L L產(chǎn)產(chǎn)生的哈密頓回路生的哈密頓回路H H；(e)(e)是是G G的一個(gè)最小費(fèi)用旅的一個(gè)最小費(fèi)用旅行售貨員回路。行售貨員回路。 282 一般一般的的旅行售貨員問題旅行售貨員問題 在費(fèi)用函數(shù)不一定

21、滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項(xiàng)式時(shí)間近似算法，除非P=NPP=NP。換句話說，若PNP，則對任意常數(shù)1，不存在性能比為的解旅行售貨員問題的多項(xiàng)式時(shí)間近似算法。 299.4.4 集合覆蓋問題的近似算法 問題描述：給定一個(gè)完全無向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。 集合覆蓋問題的一個(gè)實(shí)例X,F由一個(gè)有限集X及X的一個(gè)子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬于F中的一個(gè)子集，即X= 。對于F中的一個(gè)子集CF，若C中的X的子集覆蓋了X，即X= ，則稱C覆蓋了X。集合覆蓋問題就是

22、要找出F中覆蓋X的最小子集C*，使得 |C*|=min|C|CF且C覆蓋X FSSCSS309.4.4 集合覆蓋問題的近似算法集合覆蓋問題舉例：用用1212個(gè)黑點(diǎn)表示集個(gè)黑點(diǎn)表示集合合X X。F=S1,S2,S3,S4,SF=S1,S2,S3,S4,S5,S6,5,S6,，如圖所示。如圖所示。容易看出，對于這容易看出，對于這個(gè)例子，最小集合個(gè)例子，最小集合覆蓋為：覆蓋為：C=S3,S4,S5,C=S3,S4,S5,。 319.4.4 集合覆蓋問題的近似算法集合覆蓋問題近似算法貪心算法 算法的循環(huán)體最多算法的循環(huán)體最多執(zhí)行執(zhí)行min|X|min|X|，|F|F|次。次。而循環(huán)體內(nèi)的計(jì)算顯然而循環(huán)

23、體內(nèi)的計(jì)算顯然可在可在O(|X|F|)O(|X|F|)時(shí)間內(nèi)完時(shí)間內(nèi)完成。因此，算法的計(jì)算成。因此，算法的計(jì)算時(shí)間為時(shí)間為O(|X|F|min|X|O(|X|F|min|X|，|F|)|F|)。由此即知，該算由此即知，該算法是一個(gè)多項(xiàng)式時(shí)間算法是一個(gè)多項(xiàng)式時(shí)間算法。法。 Set greedySetCovergreedySetCover (X,F) U=X； C=； while (U !=) 選擇F中使|SU|最大的子集S； U=U-S； C=CS； return C； 329.4.5 子集和問題的近似算法 問題描述：設(shè)子集和問題的一個(gè)實(shí)例為S,t。其中，S=x1，x2，xn是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問題判定是否存在S的一個(gè)子集S1，使得 。txSx 1331 子集和問題的指數(shù)時(shí)間算法int exactSubsetSumexactSubsetSum (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