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

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

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

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

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

5、結(jié)構(gòu),計(jì)算復(fù)雜性問題,2. RAM程序 一個(gè)RAM程序定義了從輸入帶到輸出帶的一個(gè)映射?？梢詫?duì)這種映射關(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,計(jì)算復(fù)雜性問題,解釋二：把RAM程序當(dāng)作一個(gè)語言接受器將字符串S

6、=a1a2…an放在輸入帶上。在輸入帶的第一個(gè)方格中放入符號(hào)a1，第二個(gè)方格中放入符號(hào)a2，…，第n個(gè)方格中放入符號(hào)an。然后在第n+1個(gè)方格中放入0，作為輸入串的結(jié)束標(biāo)志符。 如果一個(gè)RAM程序P讀了字符串S及結(jié)束標(biāo)志符0后，在輸出帶的第一格輸出一個(gè)1并停機(jī)，就說程序P接受字符串S。,計(jì)算復(fù)雜性問題,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è)單位空間

7、。 RAM程序的復(fù)雜性一般按照均勻耗費(fèi)標(biāo)準(zhǔn)衡量。,計(jì)算復(fù)雜性問題,標(biāo)準(zhǔn)二：對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)對(duì)數(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ù)，則,計(jì)算復(fù)雜性問題,□隨機(jī)存取機(jī)RASP1. RASP的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲(chǔ)在寄存器中的。每條RA

8、SP指令占據(jù)2個(gè)連續(xù)的寄存器。第一個(gè)寄存器存放操作碼的編碼，第二個(gè)寄存器存放地址。RASP指令用整數(shù)進(jìn)行編碼。,計(jì)算復(fù)雜性問題,2. RASP程序的復(fù)雜性不管是在均勻耗費(fèi)標(biāo)準(zhǔn)下，還是在對(duì)數(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ù)雜性的情況也是類似的。,計(jì)算復(fù)雜性問題,□ 圖靈機(jī)1、

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

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

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

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

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

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

15、否則， 。,,,,計(jì)算復(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)。,,計(jì)算復(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 )=,,,,,,計(jì)算復(fù)雜性問題,對(duì)于 ，設(shè)n=2，圖靈機(jī)的工作過程如下：,,,,,,,,,,,,,計(jì)算復(fù)雜性,,,,,,,,,,,,,,,,計(jì)算復(fù)雜性問題,,,,,,,,,,,,,計(jì)算復(fù)雜性問題,□ K帶圖靈機(jī)結(jié)構(gòu) 有K個(gè)工作帶，每個(gè)工作帶有一個(gè)讀

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

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

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

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

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

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

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

24、求解為圖G著色，使相鄰兩個(gè)頂點(diǎn)不會(huì)有相同顏色時(shí)所需最少顏色數(shù)num。令圖G的頂點(diǎn)個(gè)數(shù)為n，彩色數(shù)是num，假定存在一個(gè)圖G著色判定問題的多項(xiàng)式時(shí)間算法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)化問題 對(duì)算法coloring調(diào)用O(log n) 次，就能找出為圖著色的最優(yōu)彩色數(shù)。 根據(jù)假定，coloring是多項(xiàng)式時(shí)間算法; 所以，這個(gè)算法也是一個(gè)多項(xiàng)式時(shí)間算法。,P類與NP類問題,□ P類問題確定性算法 若A是問題∏的一個(gè)算法。如果在處理問題∏的實(shí)例時(shí)，在算法的整個(gè)執(zhí)行過程中，每一步只有一個(gè)確定的選擇，就說算法A是確定性的算法。 含義：算法執(zhí)行的每一個(gè)步驟，都有

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、 ′或v∈V ′，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。 其次，通過CLIQUE∝pVERTEX-COVER來證明頂點(diǎn)覆蓋問題是NP難的。,NP完全問題,□ 子集和問題（SUBSET-SUM）問題描述 給定整數(shù)集合S和一個(gè)整數(shù)t，判定是否存在S的一個(gè)子集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}是一個(gè)解。,NP完全問題,證明思路 首先，對(duì)于子集和問題的一個(gè)實(shí)例，給定一個(gè)“證書” S′ ，要驗(yàn)證t= 是否成立，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。因此，SUBSET-SUM∈NP； 其次，證明 VERTEX-COVER∝pSUBSET-SUM。,NP完全問題,□ 圖的著色問題（COLORING）問題描述 給定一個(gè)無向圖G=(V，E)和一個(gè)正整數(shù)k，用k種顏色

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

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

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

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

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

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