第9章NP完全性理論與近似算法,2,學(xué)習(xí)要點(diǎn)理解RAM，RASP和圖靈機(jī)計(jì)算模型理解非確定性圖靈機(jī)的概念理解P類與NP類語言的概念理解NP完全問題的概念理解近似算法的性能比及多項(xiàng)式時(shí)間近似格式的概念通過范例學(xué)習(xí)NP完全問題的近似算法（1）頂點(diǎn)覆蓋問題；（2）旅行售貨員問題；（3）集合覆蓋問題；（4）子集和問題。,3,9.1計(jì)算模型,在進(jìn)行問題的計(jì)算復(fù)雜性分析之前，首先必須建立求解問題所用的計(jì)算模型，包括定義該計(jì)算模型中所用的基本運(yùn)算。建立計(jì)算模型的目的是為了使問題的計(jì)算復(fù)雜性分析有一個(gè)共同的客觀尺度。3個(gè)基本計(jì)算模型：隨機(jī)存取機(jī)RAM(RandomAccessMachine)；隨機(jī)存取存儲程序機(jī)RASP(RandomAccessStoredProgramMachine)圖靈機(jī)(TuringMachine)。這3個(gè)計(jì)算模型在計(jì)算能力上是等價(jià)的，但在計(jì)算速度上是不同的。,4,9.1.1隨機(jī)存取機(jī)RAM,1、RAM的結(jié)構(gòu),5,9.1.1隨機(jī)存取機(jī)RAM,2、RAM程序,一個(gè)RAM程序定義了從輸入帶到輸出帶的一個(gè)映射?？梢詫@種映射關(guān)系作2種不同的解釋。,解釋一：把RAM程序看成是計(jì)算一個(gè)函數(shù)若一個(gè)RAM程序P總是從輸入帶前n個(gè)方格中讀入n個(gè)整數(shù)x1，x2，xn，并且在輸出帶的第一個(gè)方格上輸出一個(gè)整數(shù)y后停機(jī)，那么就說程序P計(jì)算了函數(shù)f(x1，x2，xn)=y,解釋二：把RAM程序當(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。,6,9.1.1隨機(jī)存取機(jī)RAM,3、RAM程序的耗費(fèi)標(biāo)準(zhǔn),標(biāo)準(zhǔn)一：均勻耗費(fèi)標(biāo)準(zhǔn)在均勻耗費(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)對數(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ù)，則,7,9.1.2隨機(jī)存取存儲程序機(jī)RASP,1、RASP的結(jié)構(gòu),RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據(jù)2個(gè)連續(xù)的寄存器。第一個(gè)寄存器存放操作碼的編碼，第二個(gè)寄存器存放地址。RASP指令用整數(shù)進(jìn)行編碼。,2、RASP程序的復(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ù)因子?？臻g復(fù)雜性的情況也是類似的。,8,9.1.3圖靈機(jī),9,9.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)前讀寫頭下的方格中原有帶符號并寫上新的帶符號。(3)獨(dú)立地將任何一個(gè)或所有讀寫頭，向左移動一個(gè)方格(L)或向右移動一個(gè)方格(R)或停在當(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)是移動函數(shù)。它是從QTk的某一子集映射到Q(TL，R，S)k的函數(shù)。,10,9.1.3圖靈機(jī),圖靈機(jī)M的時(shí)間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計(jì)算步數(shù)。如果對某個(gè)長度為n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個(gè)n值無定義。,圖靈機(jī)的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時(shí)，在k條帶上所使用過的方格數(shù)的總和。如果某個(gè)讀寫頭無限地向右移動而不停機(jī)，S(n)也無定義。,與RAM模型類似，圖靈機(jī)既可作為語言接受器，也可作為計(jì)算函數(shù)的裝置。,11,9.2P類與NP類問題,一般地說，將可由多項(xiàng)式時(shí)間算法求解的問題看作是易處理的問題，而將需要超多項(xiàng)式時(shí)間才能求解的問題看作是難處理的問題。有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項(xiàng)式時(shí)間算法，也沒有人能夠證明這些問題需要超多項(xiàng)式時(shí)間下界。在圖靈機(jī)計(jì)算模型下，這類問題的計(jì)算復(fù)雜性至今未知。為了研究這類問題的計(jì)算復(fù)雜性，人們提出了另一個(gè)能力更強(qiáng)的計(jì)算模型，即非確定性圖靈機(jī)計(jì)算模型，簡記為NDTM(NondeterministicTuringMachine)。在非確定性圖靈機(jī)計(jì)算模型下，許多問題可以在多項(xiàng)式時(shí)間內(nèi)求解。,12,9.2.1非確定性圖靈機(jī),非確定性圖靈機(jī)（NDTM）：一個(gè)k帶的非確定性圖靈機(jī)M是一個(gè)7元組：(Q，T，I，b，q0，qf)。與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動函數(shù)具有不確定性，即對于QTk中的每一個(gè)值(q;x1,x2,xk)，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中有唯一的一個(gè)子集(q;x1,x2,xk)與之對應(yīng)。可以在(q;x1,x2,xk)中隨意選定一個(gè)值作為它的函數(shù)值。,在圖靈機(jī)計(jì)算模型中，移動函數(shù)是單值的，即對于QTk中的每一個(gè)值，當(dāng)它屬于的定義域時(shí)，Q(TL，R，S)k中只有唯一的值與之對應(yīng)，稱這種圖靈機(jī)為確定性圖靈機(jī)，簡記為DTM(DeterministicTuringMachine)。,13,9.2.2P類與NP類語言,P類和NP類語言的定義：P=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺DTM所接受的語言NP=L|L是一個(gè)能在多項(xiàng)式時(shí)間內(nèi)被一臺NDTM所接受的語言,由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)接受的語言也可在多項(xiàng)式時(shí)間內(nèi)被非確定性圖靈機(jī)接受。故PNP。,14,9.2.2P類與NP類語言,NP類語言舉例無向圖的團(tuán)問題。該問題的輸入是一個(gè)有n個(gè)頂點(diǎn)的無向圖G=(V，E)和一個(gè)整數(shù)k。要求判定圖G是否包含一個(gè)k頂點(diǎ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)制表示。,15,9.2.2P類與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)完成。,在算法的第二階段中，非確定性地選擇V的一個(gè)k元子集VV。,算法的第三階段是確定性地檢查V的團(tuán)性質(zhì)。若V是一個(gè)團(tuán)則接受輸入，否則拒絕輸入。這顯然可以在時(shí)間內(nèi)完成。因此，整個(gè)算法的時(shí)間復(fù)雜性為。,非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語言CLIQUE，故CLIQUENP。,16,9.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-1：VP=NP。,例如(哈密頓回路問題)：一個(gè)無向圖G含有哈密頓回路嗎?無向圖G的哈密頓回路是通過G的每個(gè)頂點(diǎn)恰好一次的簡單回路。可用語言HAM-CYCLE定義該問題如下：HAM-CYCLE=G|G含有哈密頓回路,17,9.3NP完全問題,PNP。直觀上看，P類問題是確定性計(jì)算模型下的易解問題類，而NP類問題是非確定性計(jì)算模型下的易驗(yàn)證問題類。大多數(shù)的計(jì)算機(jī)科學(xué)家認(rèn)為NP類中包含了不屬于P類的語言，即PNP。NP完全問題有一種令人驚奇的性質(zhì)，即如果一個(gè)NP完全問題能在多項(xiàng)式時(shí)間內(nèi)得到解決，那么NP中的每一個(gè)問題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP。目前還沒有一個(gè)NP完全問題有多項(xiàng)式時(shí)間算法。,18,9.3.1多項(xiàng)式時(shí)間變換,定義：語言L是NP完全的當(dāng)且僅當(dāng)(1)LNP；(2)對于所有LNP有LpL。如果有一個(gè)語言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語言是NP難的。所有NP完全語言構(gòu)成的語言類稱為NP完全語言類，記為NPC。,設(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)。,19,9.3.1多項(xiàng)式時(shí)間變換,定理9-2：設(shè)L是NP完全的，則(1)LP當(dāng)且僅當(dāng)PNP；(2)若Lp，且NP，則是NP完全的。,定理的(2)可用來證明問題的NP完全性。但前提是：要有第一個(gè)NP完全問題L。,20,9.3.2一些典型的NP完全問題,部分NP完全問題樹,21,迄今為止，所有的NP完全問題都還沒有多項(xiàng)式時(shí)間算法。對于這類問題，通常可采取以下幾種解題策略。(1)只對問題的特殊實(shí)例求解(2)用動態(tài)規(guī)劃法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用啟發(fā)式方法求解,9.4NP完全問題的近似算法,22,9.4.1近似算法的性能,若一個(gè)最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個(gè)近似算法求得的近似最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值為c，則將該近似算法的性能比定義為=。在通常情況下，該性能比是問題輸入規(guī)模n的一個(gè)函數(shù)(n)，即(n)。,該近似算法的相對誤差定義為=。若對問題的輸入規(guī)模n，有一函數(shù)(n)使得(n)，則稱(n)為該近似算法的相對誤差界。近似算法的性能比(n)與相對誤差界(n)之間顯然有如下關(guān)系：(n)(n)-1。,23,9.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|。,VertexSetapproxVertexCover(Graphg)cset=；e1=g.e；while(e1!=)從e1中任取一條邊(u,v)；cset=csetu,v；從e1中刪去與u和v相關(guān)聯(lián)的所有邊；returnc,Cset用來存儲頂點(diǎn)覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點(diǎn)加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。,24,9.4.2頂點(diǎn)覆蓋問題的近似算法,圖(a)(e)說明了算法的運(yùn)行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋cset，它由頂點(diǎn)b,c,d,e,f,g所組成。(f)是圖G的一個(gè)最小頂點(diǎn)覆蓋，它只含有3個(gè)頂點(diǎn)：b,d和e。,算法approxVertexCover的性能比為2。,25,9.4.3旅行售貨員問題近似算法,問題描述：給定一個(gè)完全無向圖G=(V,E)，其每一邊(u,v)E有一非負(fù)整數(shù)費(fèi)用c(u,v)。要找出G的最小費(fèi)用哈密頓回路。,比如，費(fèi)用函數(shù)c往往具有三角不等式性質(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ì)：,26,1滿足三角不等式的旅行售貨員問題,對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計(jì)找近似最優(yōu)的旅行售貨員回路的算法。,voidapproxTSP(Graphg)(1)選擇g的任一頂點(diǎn)r；(2)用Prim算法找出帶權(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)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個(gè)最小費(fèi)用旅行售貨員回路。,28,2一般的旅行售貨員問題,在費(fèi)用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多項(xiàng)式時(shí)間近似算法，除非P=NP。換句話說，若PNP，則對任意常數(shù)1，不存在性能比為的解旅行售貨員問題的多項(xiàng)式時(shí)間近似算法。,29,9.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。集合覆蓋問題就是要找出F中覆蓋X的最小子集C*，使得|C*|=min|C|CF且C覆蓋X,30,9.4.4集合覆蓋問題的近似算法,集合覆蓋問題舉例：,用12個(gè)黑點(diǎn)表示集合X。F=S1,S2,S3,S4,S5,S6,，如圖所示。容易看出，對于這個(gè)例子，最小集合覆蓋為：C=S3,S4,S5,。,31,9.4.4集合覆蓋問題的近似算法,集合覆蓋問題近似算法貪心算法,算法的循環(huán)體最多執(zhí)行min|X|，|F|次。而循環(huán)體內(nèi)的計(jì)算顯然可在O(|X|F|)時(shí)間內(nèi)完成。因此，算法的計(jì)算時(shí)間為O(|X|F|min|X|，|F|)。由此即知，該算法是一個(gè)多項(xiàng)式時(shí)間算法。,SetgreedySetCover(X,F)U=X；C=；while(U!=)選擇F中使|SU|最大的子集S；U=U-S；C=CS；returnC；,32,9.4.5子集和問題的近似算法,問題描述：設(shè)子集和問題的一個(gè)實(shí)例為S,t。其中，S=x1，x2，xn是一個(gè)正整數(shù)的集合，t是一個(gè)正整數(shù)。子集和問題判定是否存在S的一個(gè)子集S1，使得。,33,1子集和問題的指數(shù)時(shí)間算法,intexactSubsetSum(S,t)intn=|S|；L0=0；for(inti=1；i=n；i+)Li=mergeLists(Li-1,Li-1+Si)；刪去Li中超過t的元素；returnmax(Ln)；,算法以集合S=x1，x