計算復(fù)雜性與智能算法

1、第3章 計算復(fù)雜性與智能算法,第8課 計算復(fù)雜性 第9課 近似算法 第10課 智能型算法 第11課 線性規(guī)劃,第8課 計算復(fù)雜性,? 算法復(fù)雜性問題 ? 圖靈機(jī) ? P類與NP類問題 ? NP完全問題,□ 算法的復(fù)雜性問題? 算法本身能不能解，這個問題應(yīng)該在求解問題前就應(yīng)該首先確定，因為如果一個問題是不可解的，那么對這個問題尋求算法的努力也是徒勞的。問題否可解的相關(guān)內(nèi)容，也就是算法復(fù)雜性理論所涉及到的內(nèi)容。包括P、NP問題

2、的定義以及比較，還有確定型圖靈機(jī)的介紹。這些內(nèi)容不足以構(gòu)成算法復(fù)雜性理論體系，但是了解這些內(nèi)容是復(fù)雜性理論深入學(xué)習(xí)的基礎(chǔ)。,計算復(fù)雜性問題,?可解問題與不可解問題 并不是任何計算問題都能夠利用計算機(jī)來解決。算法復(fù)雜性理論關(guān)心的是哪些問題是可以利用計算機(jī)來解決的，也就是說是“可解的問題”；哪些問題是在計算機(jī)也解決不了的，也就是“不可解的問題”。盡管理論上可解的問題在實際中未必能夠找到實現(xiàn)的算法，但算法復(fù)雜性理論關(guān)心的是如何在理論上證明

3、問題的可解，而不關(guān)心具體如何實現(xiàn)。,計算復(fù)雜性問題,? P問題與NP問題 如果一個判定性問題的復(fù)雜度是該問題的一個實例的規(guī)模n的多項式函數(shù)，則我們說這種可以在多項式時間內(nèi)解決的判定性問題屬于P類問題。P類問題就是所有復(fù)雜度為多項式時間的問題的集合。通俗地稱所有復(fù)雜度為多項式時間的問題為易解的問題類，否則為難解的問題。 這種可以在多項式時間內(nèi)驗證一個解是否正確的問題稱為NP問題,亦稱為易驗證問題類。,計算復(fù)雜性問題,? N

4、P理論的核心問題 如果說P問題是NP問題的一個真子集，那么可以不必花太多時間尋找大規(guī)模輸入NP問題的解，因為這樣的努力都是徒勞的；然而如果能夠證明NP問題是P問題，那么結(jié)果就很不一樣了，它說明了現(xiàn)在許多的指數(shù)復(fù)雜度的問題都有多項式復(fù)雜度的解法，只不過是暫時找不到而已。,計算復(fù)雜性問題,□ 三種常用計算模型.隨機(jī)存取機(jī)RAM模型.隨機(jī)存取存儲程序機(jī)RASP模型.圖靈機(jī)模型,計算復(fù)雜性問題,□隨機(jī)存取機(jī)RAM1. RAM的

5、結(jié)構(gòu),計算復(fù)雜性問題,2. RAM程序 一個RAM程序定義了從輸入帶到輸出帶的一個映射?？梢詫@種映射關(guān)系作2種不同的解釋。解釋一：把RAM程序看成是計算一個函數(shù)若一個RAM程序P總是從輸入帶前n個方格中讀入n個整數(shù)x1，x2，…，xn，并且在輸出帶的第一個方格上輸出一個整數(shù)y后停機(jī)，那么就說程序P計算了函數(shù) f(x1，x2，…，xn)=y,計算復(fù)雜性問題,解釋二：把RAM程序當(dāng)作一個語言接受器將字符串S

6、=a1a2…an放在輸入帶上。在輸入帶的第一個方格中放入符號a1，第二個方格中放入符號a2，…，第n個方格中放入符號an。然后在第n+1個方格中放入0，作為輸入串的結(jié)束標(biāo)志符。 如果一個RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出帶的第一格輸出一個1并停機(jī)，就說程序P接受字符串S。,計算復(fù)雜性問題,3. RAM程序的耗費標(biāo)準(zhǔn)標(biāo)準(zhǔn)一：均勻耗費標(biāo)準(zhǔn)在均勻耗費標(biāo)準(zhǔn)下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間

7、。 RAM程序的復(fù)雜性一般按照均勻耗費標(biāo)準(zhǔn)衡量。,計算復(fù)雜性問題,標(biāo)準(zhǔn)二：對數(shù)耗費標(biāo)準(zhǔn)對數(shù)耗費標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費與以二進(jìn)制表示的指令的操作數(shù)長度成比例。在RAM計算模型下，假定一個寄存器可存放一個任意大小的整數(shù)。因此若設(shè)l(i)是整數(shù)i所占的二進(jìn)制位數(shù)，則,計算復(fù)雜性問題,□隨機(jī)存取機(jī)RASP1. RASP的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RA

8、SP指令占據(jù)2個連續(xù)的寄存器。第一個寄存器存放操作碼的編碼，第二個寄存器存放地址。RASP指令用整數(shù)進(jìn)行編碼。,計算復(fù)雜性問題,2. RASP程序的復(fù)雜性不管是在均勻耗費標(biāo)準(zhǔn)下，還是在對數(shù)耗費標(biāo)準(zhǔn)下，RAM程序和RASP程序的復(fù)雜性只差一個常數(shù)因子。在一個計算模型下T(n)時間內(nèi)完成的輸入-輸出映射可在另一個計算模型下模擬，并在kT(n)時間內(nèi)完成。其中k是一個常數(shù)因子?？臻g復(fù)雜性的情況也是類似的。,計算復(fù)雜性問題,□ 圖靈機(jī)1、

9、圖靈機(jī)的構(gòu)成 圖靈機(jī)由一個控制器和一條無限長的工作帶組成， 工作帶：劃分為許多單元，每個單元可以存放字母表 中的一個符號。 控制器：具有有窮個內(nèi)部狀態(tài)和一個讀寫頭。,計算復(fù)雜性問題,單帶圖靈機(jī)結(jié)構(gòu),,計算復(fù)雜性問題,圖靈機(jī)的工作過程 計算的每一步，控制器處于某個狀態(tài)，讀寫頭掃描工作帶的某一個單元符號；根據(jù)當(dāng)前狀態(tài)、被掃描單元的內(nèi)容，決定下一步的執(zhí)行動作： 把當(dāng)前單元內(nèi)容，改寫成某一個符號；使讀寫頭

10、停止不動、向左或向右移動一個單元；使控制器轉(zhuǎn)移到某一個狀態(tài)等等。,計算復(fù)雜性問題,計算開始時，輸入符號串放在工作帶上，控制器處于初始狀態(tài) ，讀寫頭掃描輸入符號串左端的第一個符號； 如果對于當(dāng)前的狀態(tài)和所掃描的符號，沒有下一步的動作，則圖靈機(jī)就停止計算。,計算復(fù)雜性問題,□ 圖靈機(jī)形式定義 圖靈機(jī) 是一個六元組：S：控制器的非空有限狀態(tài)集合；Г：有限工作帶符號集合，含空白符B；Σ：輸入符號字母表， ；P0

11、 ：初始狀態(tài)， ；Pf ：最終狀態(tài)或接受狀態(tài)， ；δ：轉(zhuǎn)移函數(shù)。,,,,,計算復(fù)雜性問題,轉(zhuǎn)移函數(shù)δ的說明轉(zhuǎn)移函數(shù)的定義域：轉(zhuǎn)移函數(shù)的值域：,,,計算復(fù)雜性問題,{L,P,R }讀寫頭的動作: L: 左移一個單元； P: 停止不動； R: 右移一個單元；轉(zhuǎn)移函數(shù)的含義： 控制器當(dāng)前狀態(tài)為P 、讀寫頭掃描到的符號為x 時，把控制器狀態(tài)修改為P` ；把符號修改為符號x` ；使讀寫頭向右移動一個單元

12、。,,計算復(fù)雜性問題,□ 圖靈機(jī)格局定義 是一個圖靈機(jī)，M 的格局是一個二元組： :是工作帶上的內(nèi)容?！?表示在此格局下讀寫頭的位置；ω1 :表示處于讀寫頭左邊的符號串；ω2 :表示處于讀寫頭右邊的符號串。讀寫頭指向符號串ω2 的第一個符號。,,,計算復(fù)雜性問題,圖靈機(jī)格局初始格局： ，ω1 為空串；可接受格局： ， P 是可接受狀態(tài)，即

13、 。停機(jī)格局： 中，ω2 的第一個符號是x ，轉(zhuǎn)移函數(shù) 沒有定義，則稱б是停機(jī)格局。,,,,,計算復(fù)雜性問題,□ 圖靈機(jī)的計算 是一個有窮、或無窮的格局序列，如果每一個бi+1 都由бi 經(jīng)過一步得到，稱這個序列是一個計算。,,計算復(fù)雜性問題,□ 圖靈機(jī)計算的停機(jī)狀態(tài)1）計算是有窮序列 ，是可接受的停機(jī)格局，稱停機(jī)在接受狀態(tài)。稱圖靈機(jī) M 接受

14、符號串ω ；2）計算是有窮序列 ， 不是可接受的停機(jī)格局，稱停機(jī)在拒絕狀態(tài)。稱圖靈機(jī) M 不接受符號串ω ，或拒絕符號串ω; 3）計算是無窮序列 ，永不停機(jī)。,,計算復(fù)雜性問題,□ 圖靈機(jī)對語言的識別構(gòu)造一個識別語言 的圖靈機(jī)設(shè)計思想： 使讀寫頭來回移動，成對地對輸入符號串的左端和右端作標(biāo)記。 如果全部符號都作了標(biāo)記，則左邊的與右邊的個數(shù)相等， ；

15、否則， 。,,,,計算復(fù)雜性問題,□ 圖靈機(jī)的構(gòu)造S={ P0 ,P1 ,P2,P3 ,P4 ,PN };Г={ a,b,x,B };Σ={ a,b,};Pf={ P4 ,PN }; 其中，P4 為接受狀態(tài)，PN 為拒絕狀態(tài)。,,計算復(fù)雜性問題,轉(zhuǎn)移函數(shù)δ(p0 ,a)= δ(p0 ,b )=δ(p1 ,a)= δ(p1 ,x )=δ(p1 ,B)=

16、 δ(p2 ,b )=δ(p2 ,x)= δ(p2 ,B )=δ(p3,a )= δ(p3,x )=δ(p3,B )=,,,,,,計算復(fù)雜性問題,對于 ，設(shè)n=2，圖靈機(jī)的工作過程如下：,,,,,,,,,,,,,計算復(fù)雜性,,,,,,,,,,,,,,,,計算復(fù)雜性問題,,,,,,,,,,,,,計算復(fù)雜性問題,□ K帶圖靈機(jī)結(jié)構(gòu) 有K個工作帶，每個工作帶有一個讀

17、寫頭，都可以獨立地移動。,計算復(fù)雜性問題,□ K帶圖靈機(jī)形式定義轉(zhuǎn)移函數(shù)δ的形式：K帶圖靈機(jī)格局若x是輸入符號串，則初始格局表示為,,,,計算復(fù)雜性問題,□ 確定的圖靈機(jī)和非確定的圖靈機(jī)確定性圖靈機(jī) 若圖靈機(jī)的轉(zhuǎn)移函數(shù)δ是單值的，則稱該圖靈機(jī)為確定性圖靈機(jī)，記為 DTM，圖靈機(jī)每一步的動作都是確定的。非確定的圖靈機(jī) 若圖靈機(jī)的轉(zhuǎn)移函數(shù)δ是多值的，則稱該圖靈機(jī)為非確定性圖靈機(jī)，記為 NDTM。,計算復(fù)雜性問

18、題,□ 圖靈機(jī)的執(zhí)行時間圖靈機(jī)的計算的長度 設(shè) 是一個格局序列，它是圖靈機(jī)對輸入的一個計算。如果бt 是一個可接受的停機(jī)格局，則稱這個計算是可接受的計算，t 稱為這個計算的長度。,,計算復(fù)雜性問題,圖靈機(jī)的執(zhí)行時間 圖靈機(jī)M 對輸入x進(jìn)行計算的執(zhí)行時間，記為TM(x) ，它定義為：(1) 如果M 對輸入x有一個可接受的計算，則TM(x)是最短的可接受計算的長度；(2) 如果M 對輸入 x沒有一個

19、可接受的計算，則 TM(x) =∞。,計算復(fù)雜性問題,□ 圖靈機(jī)的時間復(fù)雜性 圖靈機(jī)M的時間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數(shù)。如果對某個長度為n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個n值無定義。,計算復(fù)雜性問題,□ 圖靈機(jī)的空間復(fù)雜性 圖靈機(jī)的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機(jī)，S(n)也無定義。,計算復(fù)雜性問題,

20、□ 圖靈機(jī)模型與RAM模型的關(guān)系 圖靈機(jī)模型與RAM模型的關(guān)系是指同一問題在這兩種不同計算模型下的復(fù)雜性之間的關(guān)系。 對于問題P的任何長度為n的輸入，設(shè)求解問題P的算法A在k帶圖靈機(jī)模型TM下的時間復(fù)雜性為T(n)，那么，算法A在RAM模型下的時間復(fù)雜性為O(T2(n))。,計算復(fù)雜性問題,對于問題P的任何長度為n的輸入，設(shè)求解問題P的算法A在RAM模型下，不含有乘法和除法指令，且按對數(shù)耗費標(biāo)準(zhǔn)其時間復(fù)雜性為T(n)，

21、那么，算法A在k帶圖靈機(jī)模型TM下的時間復(fù)雜性為O(T2(n))。 通過問題變換的技巧，可以將不同問題的計算復(fù)雜性聯(lián)系在一起。這樣就可以將一個問題的計算復(fù)雜性歸結(jié)為另一個問題的計算復(fù)雜性。,計算復(fù)雜性問題,□ 易解的問題和難解的問題存在多項式時間算法的問題，稱為易解的問題。指數(shù)時間算法或排列時間算法的問題，稱為難解的問題。,P類與NP類問題,□ 難解問題的計算相關(guān)性計算相關(guān)： 某類問題可以歸約為另一類問題。

22、計算相關(guān)問題 若它們之一可用多項式時間求解，則其它同類問題也可用多項式時間求解；若它們之一肯定不存在多項式時間算法，則同類的其它問題，也肯定不會找到多項式時間算法。,P類與NP類問題,□ P類和NP類語言的定義 P={L|L是一個能在多項式時間內(nèi)被一臺DTM所接受的語言} NP={L|L是一個能在多項式時間內(nèi)被一臺NDTM所接受的語言},P類與NP類問題,□判定問題和優(yōu)化問題判定問題:只牽涉到兩種情況：YE

23、S 或 NO，可以容易地表達(dá)為語言的識別問題，方便在圖靈機(jī)上進(jìn)行求解。例如：排序問題的判定問題。給定一個整數(shù)數(shù)組，是否可以按非降順序排序；圖著色的判定問題。給定無向圖 ，是否可用K種顏色為N中的每一個頂點分配一種顏色，使得不會有兩個相鄰頂點具有同一種顏色。,P類與NP類問題,□ 優(yōu)化問題優(yōu)化問題牽涉到極值問題。例：圖著色的優(yōu)化問題。 為圖G著色，使相鄰兩個頂點不會有相同顏色時所需要的最少顏色數(shù)目。,P類與NP類問題,例：

24、求解為圖G著色，使相鄰兩個頂點不會有相同顏色時所需最少顏色數(shù)num。令圖G的頂點個數(shù)為n，彩色數(shù)是num，假定存在一個圖G著色判定問題的多項式時間算法coloring： BOOL coloring(GRAPH G,int n,int num)則可用下面的方法，利用算法coloring來解圖著色的優(yōu)化問題。,P類與NP類問題,void chromatic_number(GRAPH G,int n,int &num){

25、int high,low;high = n;low = 1;while (low<=high) {,P類與NP類問題,num = (low + high) / 2; if (coloring(G,n,num)) low = mid + 1; else high = mid –1; } num = high;},P類與NP類問

26、題,□判定問題轉(zhuǎn)換為優(yōu)化問題 對算法coloring調(diào)用O(log n) 次，就能找出為圖著色的最優(yōu)彩色數(shù)。 根據(jù)假定，coloring是多項式時間算法; 所以，這個算法也是一個多項式時間算法。,P類與NP類問題,□ P類問題確定性算法 若A是問題∏的一個算法。如果在處理問題∏的實例時，在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，就說算法A是確定性的算法。 含義：算法執(zhí)行的每一個步驟，都有

27、確定的選擇。重新用同一輸入實例運行該算法，所得到的結(jié)果嚴(yán)格一致。,P類與NP類問題,□ P類判定問題 如果對某個判定問題∏，存在著一個非負(fù)整數(shù)K，對輸入規(guī)模為n的實例，能夠以O(shè)(nk) 的時間運行一個確定性的算法，得到 YES 或NO 的答案，則該判定問題∏是一個P類判定問題。 特性：P類判定問題是由具有多項式時間的確定性算法來解的判定問題。,P類與NP類問題,例如： 最短路徑判定問題 給定有向賦權(quán)圖G（權(quán)為正

28、整數(shù)）、正整數(shù)K、及兩個頂點s,t ，是否存在著一條由s到t、長度至多為K的路徑?？膳判虻呐卸▎栴} 給定n個元素的數(shù)組，是否可以按非降順序排序。,P類與NP類問題,□ P類判定問題的補(bǔ) 改變判定問題的提法，“是否不可以”、“是否不存在”的判定問題。例：可排序判定問題的補(bǔ) 給定n個元素的數(shù)組，是否不可以按非降順序排序。 最短路徑判定問題的補(bǔ) 給定有向賦權(quán)圖G（權(quán)為正整數(shù)）、正整數(shù)K、及兩個頂點s

29、、t ，是否不存在著一條由s到t、長度至多為K的路徑。,P類與NP類問題,□ P類問題的封閉性 令C是一類問題，如果對C中的任何問題∏∈C ，∏的補(bǔ)也在C中，則稱C類問題在補(bǔ)集下封閉。 P類問題的封閉性: P類問題在補(bǔ)集下是封閉的。,P類與NP類問題,,□歸約的定義 令∏和∏′是兩個判定問題，如果存在一個確定性算法A ，可以用多項式的時間，把問題∏′的實例I′轉(zhuǎn)換為問題∏的實例I，使得的答案為yes ，當(dāng)且僅

30、當(dāng)I的答案是yes 。就說，∏′以多項式時間歸約于∏，記為∏′∝p ∏ 。,P類與NP類問題,,□ P類問題的歸約性 ∏和∏′是兩個判定問題， 如果, ∏∈P ，并且， ∏′∝p ∏，則∏′∈P。,P類與NP類問題,□ NP類問題非確定性算法 問題∏的非確定性算法的分為兩個階段：推測階段和驗證階段。推測階段 對規(guī)模為n的輸入實例x，以多項式時間O(ni)產(chǎn)生輸出y，而不管y的正確性。,P類與NP類問題,驗證階

31、段 以多項式時間O(nj) 的確定性算法驗證兩件事情： 1）檢查上一階段的輸出y是否具有正確的形式。如果y不具正確的形式，算法就以答案no結(jié)束； 2）如果y具有正確的形式，則繼續(xù)檢查 是否是問題的輸入實例x 的解。如果它確實是問題實例x的解，則以答案yes結(jié)束，否則，以答案no結(jié)束。,P類與NP類問題,□ 旅行售貨商的判定問題 給定n個城市、正常數(shù)k、及城市之間的費用矩陣C ，判定是否存在一條經(jīng)過所有城市一次

32、且僅一次、最后返回初始出發(fā)城市、且費用小于常數(shù)k的回路。 令A(yù)是求旅行售貨商判定問題的算法。 A用非確定性的方法，在多項式時間內(nèi)推測存在著一條回路，假定它是問題的解;,P類與NP類問題,A用確定性的算法，在多項式時間內(nèi)檢查：該回路是否是哈密爾屯回路，如果答案為yes ，則繼續(xù)檢查該回路的費用是否小于常數(shù)C ，如果答案仍為yes ，則算法A輸出yes ，否則輸出no 。 因此，A是求解旅行售貨商判定問題的非確定性算法

33、。,P類與NP類問題,□ 非確定性算法的運行時間 非確定性算法的運行時間，是推測階段和驗證階段運行時間的和。 若推測階段的運行時間為O(ni) ， 驗證階段的運行時間為O(nj) ， 則對某個非負(fù)整數(shù)k，非確定性算法的運行時間為O(ni)+O(nj)=O(nk) 。,P類與NP類問題,□ NP類判定問題 如果對某個判定問題∏，存在著一個非負(fù)整數(shù)k，對輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一

34、個非確定性的算法，得到y(tǒng)es或no的答案，則該判定問題∏是一個NP類判定問題。,P類與NP類問題,□ 旅行售貨商問題 若算法A可在推測階段用多項式時間推測出一條回路，并假定它是問題的解；在驗證階段用多項式時間的確定性算法，檢查所推測的回路是否恰好每個城市經(jīng)過一次，如果是，再進(jìn)一步判斷這條回路的長度是否小于或等于L，如果是，答案為yes，否則，答案為no。 根據(jù)定義，旅行售貨商判定問題是NP類判定問題。,P類與NP類問題,

35、□ P類問題和NP類問題的差別 P類問題可以用多項式時間的確定性算法來進(jìn)行判定或求解； NP類問題可以用多項式時間的確定性算法來檢查和驗證它的解。 ∏∈P ，必然有∏∈NP ，所以，P ? NP。 猜測 P≠NP。該不等式是否成立、至今還沒有得到證明。,P類與NP類問題,,□ NP完全問題概念NP難題 令∏是一個判定問題，如果對NP 中的每一個問題∏′∈NP ，有 ∏′∝p ∏ ，就說判定問

36、題 ∏是一個 NP難題。,NP完全問題,NP完全問題 令∏是一個判定問題，如果：(1) ∏∈NP ，并且：(2) 對NP中的所有問題∏′∈NP ，都有∏′∝p ∏ ；則稱判定問題∏是NP 完全的。NP難題和NP完全問題的差別 ∏是NP完全問題， ∏′是NP難題，則∏必定在NP類中，而∏′不一定在NP 類中。,NP完全問題,□ NP完全問題的特性 令 ∏和∏′是 NP中的兩個問題，使得∏′∝p∏ 。如

37、果∏′是NP完全的，則 ∏也是∏完全的。NP 完全問題的證明證明下面兩件事情：(1) ∏∈NP ，并且： (2) 存在一個NP完全問題∏′，使得 ；∏′∝p ∏。,NP完全問題,□ NP完全問題舉例 已知哈密爾頓回路問題是一個NP完全問題，證明旅行售貨商問題也是一個NP完全問題。哈密爾頓回路問題 給定無向圖G ，是否存在一條回路，使得圖中每個頂點在回路中出現(xiàn)一次且僅一次。,NP完全問題,旅行售貨商問題

38、給定n個城市和最短距離l，是否存在從某個城市出發(fā)、經(jīng)過每個城市一次且僅一次、最后回到出發(fā)城市、且距離小于或等于l 的路線。證明旅行售貨商問題∏是NP問題。證明哈密爾頓回路問題∏′ 可用多項式時間歸約為旅行售貨商問題，即 ∏′∝p ∏ 。,NP完全問題,令G=(V,E) 是哈密爾頓回路問題的任一實例，|V|=n 。 構(gòu)造賦權(quán)圖 ，使得 V=V′ , E′= {(u,v)|u,v∈V}。對E′中的每

39、一條邊u,v 賦予如下的長度：,NP完全問題,,,令l=n 。 可以由一個算法在多項式時間里完成這個構(gòu)造。 因此，哈密爾頓回路問題可以用多項式時間歸約為旅行售貨商問題。(3) 證明G中包含一條哈密爾頓回路，當(dāng)且僅當(dāng)G ’ 中存在一條經(jīng)過各個頂點一次，且全長不超過 l=n的路徑。,NP完全問題,1. G中包含一條哈密爾頓回路，設(shè)這條回路是v1,v2…vn,v1 。 則該回路也是G ’ 中一條經(jīng)過各個頂點一次且僅一

40、次的回路，根據(jù)定義的公式，這條回路長度為n，因此，這條路徑滿足旅行售貨商問題。,NP完全問題,2. G′中存在一條滿足旅行售貨商問題的路徑，則這條路徑經(jīng)過G中各個頂點一次且僅一次，最后回到起始出發(fā)頂點的回路，因此它是一條哈密爾頓回路。 綜上所述，哈密爾頓回路問題∏′可用多項式時間歸約為旅行售貨商問題成立，即 ∏′∝p ∏ 。 所以旅行售貨商問題也是一個NP完全問題。,NP完全問題,□ 可滿足性問題合取范式 由若干個析

41、取子句的合取構(gòu)成的布爾表達(dá)式 f。例：合取范式的可滿足性 對合取范式f的相應(yīng)布爾變量賦值，使f的真值為真，就說布爾表達(dá)式f是可滿足的。,NP完全問題,,□ 可滿足性問題定義判定問題：可滿足性問題（SAT）輸入：布爾表達(dá)式合取范式f（CNF）問題：對布爾表達(dá)式f中的布爾變量賦值,是 否可使f的真值為真□ Cook定理 可滿足性問題是NP 完全的。,NP完全問題,□ Cook定理的意義 Cook

42、定理給出了第一個NP完全問題，使得對任何問題∏ ，只要能夠證明 ∏∈NP ，并且 SAT∝p ∏ ，那么， ∏就是NP完全的。,NP完全問題,□ 三元可滿足性問題三元合取范式 在合取范式中，每個析取子句恰好由三個文字組成，稱為三元合取范式。三元合取范式的可滿足性問題是NP完全問題判定問題：3_SAT輸入：三元合取范式f問題：對布爾表達(dá)式f中的布爾變量賦值,是否可使f的真值為真,NP完全問題,□ 典型的NP完全問題,NP

43、完全問題,部分NP完全問題樹,□ 旅行售貨商問題（TSP）問題描述 給定一個無向完全圖G=(V，E)及定義在V?V上的一個費用函數(shù)c和一個整數(shù)k，判定G是否存在經(jīng)過V中各頂點恰好一次的回路，使得該回路的費用不超過k。,NP完全問題,□哈密爾頓回路問題（HAM-CYCLE）問題描述 給定無向圖G=(V，E)，判定其是否含有一哈密頓回路。證明思路 首先，已知哈密頓回路問題是一個NP類問題。 其次，通過

44、證明3-SAT∝pHAM-CYCLE，得出：HAM-CYCLE∈NPC。,NP完全問題,□ 團(tuán)集問題（CLIQUE）問題描述 給定一個無向圖G=(V，E)和一個正整數(shù)k，判定圖G是否包含一個k團(tuán)，即是否存在，V′?V，|V ′|=k，且對任意u，w∈V ’有(u，w)∈E。證明思路 已經(jīng)知道CLIQUE∈NP。通過3-SAT∝pCLIQUE來證明CLIQUE是NP難問題，從而證明團(tuán)問題是NP完全問題。,NP完全問題

45、,□ 頂點覆蓋問題（VERTEX-COVER）問題描述 給定一個無向圖G=(V，E)和一個正整數(shù)k，判定是否存在V ′?V，|V ′|=k，使得對于任意(u，v)∈E有u∈V′或v∈V′。如果存在這樣的V′，就稱V′為圖G的一個大小為k頂點覆蓋。,NP完全問題,證明思路 首先，VERTEX-COVER∈NP。因為對于給定的圖G和正整數(shù)k以及一個實例V′，驗證|V ′|=k，然后對每條邊(u，v)∈E，檢查是否有u∈V

46、 ′或v∈V ′，顯然可在多項式時間內(nèi)完成。 其次，通過CLIQUE∝pVERTEX-COVER來證明頂點覆蓋問題是NP難的。,NP完全問題,□ 子集和問題（SUBSET-SUM）問題描述 給定整數(shù)集合S和一個整數(shù)t，判定是否存在S的一個子集S ′?S，使得S ′中整數(shù)的和為t。例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，則子集S ′={1，16，64，2

47、56，1040，1093，1284}是一個解。,NP完全問題,證明思路 首先，對于子集和問題的一個實例，給定一個“證書” S′ ，要驗證t= 是否成立，顯然可在多項式時間內(nèi)完成。因此，SUBSET-SUM∈NP； 其次，證明 VERTEX-COVER∝pSUBSET-SUM。,NP完全問題,□ 圖的著色問題（COLORING）問題描述 給定一個無向圖G=(V，E)和一個正整數(shù)k，用k種顏色

48、為G中的每一個頂點分配一種顏色，使得不會有兩個相鄰頂點具有同一種顏色。歸結(jié)為：判定問題：COLORING輸入：無向圖G＝(V,E),正整數(shù)k≥1問題：是否可用k種顏色為圖G著色,NP完全問題,證明：圖著色問題是NP完全問題（1）圖的著色問題是NP問題 假定，圖G有n個頂點，可以在線性時間內(nèi)，用k種顏色為G中的每一個頂點著色，并假定它就是問題的解； 可以在多項式時間內(nèi)驗證該著色是否就是問題的解。 因此，圖的

49、著色問題是NP問題。,NP完全問題,（2）可用多項式時間把3_SAT問題歸約為COLORING問題。 設(shè) 是3_SAT的一個實例，它具有m個三元析取子句ci，1≤i≤m ，和n個布爾變量x1,x2,…xn ，且n≥4 。1）把3_SAT問題變換為COLORING問題構(gòu)造圖G＝(V,E)，使得頂點集V為：其中，yi是新增加的輔助變元。,NP完全問題,,,對所有的 1≤i,j≤n，1≤k≤m ，使

50、邊集E為： 顯然，可以在多項式時間內(nèi)完成圖G的構(gòu)造。,NP完全問題,,,2）三元合取范式f可滿足，當(dāng)且僅當(dāng)圖G 可著色。必要性：①考察邊集 ，對所有的 1≤i≤n， yi構(gòu)成圖G的一個完全子圖，則yi和yj不能為同一種顏色。 若令頂點yi的顏色為i，則由yi構(gòu)成的完全子圖可著色。,NP完全問題,,,②考察邊集 及邊集 , yi和xj 、yi和 不能為同一種顏

51、色。 若令頂點xi 的顏色為i 或n+1，則由xi和yi構(gòu)成的導(dǎo)出子圖可著色; 同理，若令頂點 的顏色為i或n+1，則由 和yi構(gòu)成的導(dǎo)出子圖可著色。,NP完全問題,,,,,③考察邊集 ， xi和 不能為同一種顏色，若令xi 和 中，一個頂點的顏色為i，另一個頂點的顏色為n+1，則由 xi 、 和yi 構(gòu)成的導(dǎo)出子圖可著色。,NP完全問題,④考察邊集 和邊集

52、 ，每個ck，1≤k≤m，都包含三個命題變元、或命題變元的否定，而n≥4，因此，每個 ck至少與一對頂點xi 、及 相連接，從而，每個頂點ck 的顏色都不能為n+1。,NP完全問題,,,如果三元合取范式f 可滿足，則它的每個三元析取子句 都可滿足。令 ck為：其中，u為x或 ，1≤k≤m ，1≤r,s,t≤n，因為ck為真，在ur、us、ut中，必定有一個為真，假定ur為真。令ck的顏色為r，可使與邊集

53、 、 相關(guān)聯(lián)的頂點可著色，從而圖G 可著色。,NP完全問題,,,,,充分性 若圖G可著色，則與邊集 、 相關(guān)聯(lián)的頂點可著色。 對所有的k ，1≤k≤m，存在著r ， 1≤r≤n ，使得ck的顏色值就是ur的顏色值 r。 只要ur的真值為真，ck的真值就為真，而三元合取范式f也為真。,NP完全問題,而ur可能是xr 或 ，對所有的r，xr 和