1、算法設(shè)計(jì)與分析第13講完全性汪小林信息科學(xué)技術(shù)學(xué)院1主要內(nèi)容7.1 P類與NP類7.1.1 易解的問題與難解的問題7.1.2 判定問題7.1.3 NP類7.2 多項(xiàng)式時(shí)間變換與NP完全性7.2.1 多項(xiàng)式時(shí)間變換7.2.2 NP完全性7.2.3 Cook-Levin定理第一個(gè)NP完全問題7.3 幾個(gè)NP完全問題 最大可滿足性與三元可滿足性、頂點(diǎn)覆蓋,團(tuán)與集、哈密頓回路與貨郎問題、恰好覆蓋、子集和, 背包, 裝箱與雙機(jī)調(diào)度7.1 P類與NP類7.1.1 易解的問題與難解的問題評(píng)價(jià)算法好壞的重要標(biāo)準(zhǔn)運(yùn)行時(shí)間O(nlogn)O(n2)快速排序算法Dijkstra算法O(n2n)最大團(tuán)問題的回溯法用一

2、臺(tái)每秒10億次的超大型計(jì)算機(jī)計(jì)算快速排序算法給10萬(wàn)個(gè)數(shù)據(jù)排序, 運(yùn)算量約為105log21051.7106, 僅需1.7106/109=1.710-3秒.什么是好算法?Dijkstra算法求解1萬(wàn)個(gè)頂點(diǎn)的圖的單源最短路徑問題,運(yùn)算量約為(104)2=108, 約需108/109=0.1秒.回溯法解100個(gè)頂點(diǎn)的圖的最大團(tuán)問題, 運(yùn)算量為10021001.81032, 需要1.81032/109=1.81021秒=5.71015年, 即5千7百萬(wàn)億年!再?gòu)牧硗庖粋€(gè)角度來(lái)看1分鐘能解多大的問題. 1分鐘60秒,這臺(tái)計(jì)算機(jī)可做61010次運(yùn)算, 用快速排序算法可給2109(即, 20億)個(gè)數(shù)據(jù)排序

3、, 用Dijkstra算法可解2.4105個(gè)頂點(diǎn)的圖的單源最短路徑問題. 而用回溯法一天只能解41個(gè)頂點(diǎn)的圖的最大團(tuán)問題.算法的時(shí)間復(fù)雜度函數(shù) f 和 g 是多項(xiàng)式相關(guān)的: 如果存在多項(xiàng)式 p 和 q 使得, 對(duì)任意的nN, f(n)p(q(n) 和g(n)q(f(n).nlogn與n2, n2+2n+5與n10都是多項(xiàng)式相關(guān)的,logn與n, n5與2n不是多項(xiàng)式相關(guān)的.問題P 的實(shí)例I的規(guī)模:I 的二進(jìn)制編碼的長(zhǎng)度, 記作|I|.定義7.1 如果存在函數(shù) f:NN使得, 對(duì)任意的規(guī)模為n的實(shí)例I, 算法 A對(duì)I的運(yùn)算在 f(n)步內(nèi)停止, 則稱算法A的時(shí)間復(fù)雜度為f(n).多項(xiàng)式時(shí)間算法:

4、 以多項(xiàng)式為時(shí)間復(fù)雜度. 易解的問題: 有多項(xiàng)式時(shí)間算法.難解的問題: 不存在多項(xiàng)式時(shí)間算法.例如幾點(diǎn)說明1.當(dāng)采用合理的編碼時(shí), 輸入的規(guī)模都是多項(xiàng)式相關(guān)的.“合理的”是指在編碼中不故意使用許多冗余的字符.例如, 設(shè)實(shí)例I是一個(gè)無(wú)向簡(jiǎn)單圖G=,V=a.b,c,d, E=(a,b),(a,d),(b,c),(b,d),(c,d).若用鄰接矩陣表示, 則編碼e1=0101/1011/0101/1110/, 長(zhǎng)度為20.若用關(guān)聯(lián)矩陣表示, 則編碼e2=11000/10110/00101/01011/, 長(zhǎng)度為24.設(shè)G有n個(gè)頂點(diǎn)m條邊, 則用鄰接矩陣時(shí)|I|=n(n+1), 矩陣時(shí)|I|=n(m+

5、1). 兩者是多項(xiàng)式相關(guān)的.用關(guān)聯(lián)幾點(diǎn)說明2. 自然數(shù)應(yīng)采用二 (k2)進(jìn)制編碼, 不能采用一進(jìn)制編碼.n的二進(jìn)制編碼有l(wèi)og2(n+1)位, 一進(jìn)制編碼有n位, 兩者不是多項(xiàng)式相關(guān)的.3. 時(shí)間復(fù)雜度常表成計(jì)算對(duì)象的某些自然參數(shù)的函數(shù), 如圖的頂點(diǎn)數(shù)或頂點(diǎn)數(shù)與邊數(shù)的函數(shù).實(shí)例的二進(jìn)制編碼的長(zhǎng)度與這些自然參數(shù)通常都是多項(xiàng) 式相關(guān)的.4. 關(guān)于操作指令集的兩點(diǎn)說明. 運(yùn)行時(shí)間通常是計(jì)算執(zhí)行的操作指令數(shù), 這就要求執(zhí)行的指令數(shù)與實(shí)際的運(yùn)行時(shí)間是多項(xiàng)式相關(guān)的.幾點(diǎn)說明4.1 要求每一條指令的執(zhí)行時(shí)間是固定的常數(shù). 例如, 2個(gè)不超過計(jì)算機(jī)字長(zhǎng)的二進(jìn)制數(shù)的四則運(yùn)算是一條合理的指令. 而2個(gè)任意長(zhǎng)度的二

6、進(jìn)制數(shù)的四則運(yùn)算不能作為合理的指令. 當(dāng)超過計(jì)算機(jī)字長(zhǎng)時(shí), 必須進(jìn)行分段處理.4.2 算法的計(jì)算步數(shù)與采用的操作指令集有關(guān). 這就要求任何兩個(gè)“合理的”操作指令集, 其中一個(gè)指令集中的每一條指令都可以用另一個(gè)指令集中的指令模擬, 且模擬所用的指令條數(shù)不超過某個(gè)固定的常數(shù).可以規(guī)定一個(gè)基本操作指令集, 如它由位邏輯運(yùn)算與、或、非組成, 然后認(rèn)為任何可以用這個(gè)基本操作指令集中常數(shù)條指令實(shí)現(xiàn)的操作都是合理的指令, 由有限種合理的指令的操作指令集是合理的操作指令集.幾點(diǎn)說明在上述約定下, 算法是否是多項(xiàng)式時(shí)間的與采用的編碼和操作指令集無(wú)關(guān), 從而一個(gè)問題是易解的、還是難解的也與采用的編碼和操作指令集無(wú)

7、關(guān).設(shè)有編碼s1,s2和操作指令集 D1,D2. 實(shí)例 I 的這兩種編碼的長(zhǎng)度分別為|I|1和|I|2. 存在多項(xiàng)式 p和 q, 使得 |I|1p(|I|2) 和 |I|2q(|I|1). 又存在常數(shù) k1和 k2, 使得D1(D2)中的每一條指令都可以用 D2(D1)中的不超過 k1 (k2)條指令模擬.設(shè)算法 A在采用編碼s1和操作指令集 D1時(shí)存在多項(xiàng)式 f 使得, 對(duì)任意的實(shí)例I, 算法在 f(|I|1)步內(nèi)停機(jī). 不妨設(shè) f 是單調(diào)遞增的. 若采用操作指令集D2, 算法至多運(yùn)行 k1 f(|I|1) k1 f(p(|I|2)步. 故 A在采用編碼 s2 和操作指令集 D2 時(shí)也是多項(xiàng)

8、式時(shí)間的. 反之亦然.易解的問題與難解的問題易解的問題. 如排序、最小生成樹、單源最短路徑等已證明的難解問題. 一類是不可計(jì)算的, 即根本不存在求解的算法, 如希爾伯特第十問題丟番圖方程是否有整數(shù)解.另一類是有算法, 但至少需要指數(shù)時(shí)間, 或指數(shù)空間, 甚的時(shí)間或更大的空間. 如帶冪運(yùn)算的正則表達(dá)式的至全體性, 即任給字母表 A上的帶冪運(yùn)算的正則表達(dá)式R, 問:R=A*?這個(gè)問題至少需要指數(shù)空間.既沒有找到多項(xiàng)式時(shí)間算法、又沒能證明是難解的問題. 如哈密頓回路問題、貨郎問題、背包問題等7.1.2 判定問題只有兩個(gè)是, 否.判定問題:判定問題 P = , 其中DP 是實(shí)例集合, YP DP 是為

9、“Yes”的實(shí)例.所有哈密頓回路(HC): 任給無(wú)向圖G, 問G有哈密頓回路嗎?貨郎問題(TSP): 任給n個(gè)城市, 城市i與城市j之間的正整數(shù)距離 d(i,j), ij, 1i, jn, 以及正整數(shù)D, 問有一條每一個(gè)城市恰好經(jīng)過一次最后回到出發(fā)點(diǎn)且長(zhǎng)度不超過D的巡回路線嗎? 即, 存在1,2,n的排列s 使得n-1 d (s (i),s (i + 1) + d (s (n),s (1) D ?i =1組合優(yōu)化問題與判定問題0-1背包: 任給n件物品和一個(gè)背包, 物品i的重量為wi, 價(jià)值為vi, 1in, 以及背包的重量限制B和價(jià)值目標(biāo)K, 其中wi, vi, B, K均為正整數(shù), 問能在

10、背包中裝入總價(jià)值不少于K且總重量不超過B的物品嗎?即, 存在子集T1,2,n使得wi Bvi K ?且iTiT搜索問題, 組合優(yōu)化問題與判定問題的對(duì)應(yīng).如果搜索問題, 組合優(yōu)化問題有多項(xiàng)式時(shí)間算法, 則對(duì)應(yīng)的判定問題也有多項(xiàng)式時(shí)間算法; 通常反之亦真.組合優(yōu)化問題與判定問題組合優(yōu)化問題P*由3部分組成:(1) 實(shí)例集DP*,;(2) IDP*, 有一個(gè)有窮非空集S(I), 其元素稱作I的可行解.(3) sS(I), 有一個(gè)正整數(shù)c(s), 稱作s的值.如果s*S(I), 對(duì)所有的sS(I), 當(dāng)P*是最小(大)化問題時(shí),c(s*)c(s)(c(s*)c(s)則稱s*是I的最優(yōu)解, c(s*)是

11、I的最優(yōu)值, 記作OPT(I).P*對(duì)應(yīng)的判定問題P =定義如下: DP=(I,K) | IDP*,KZ*, 其中Z*是非負(fù)整數(shù)集合. 當(dāng)P*是最小化問題時(shí), YP=(I,K) | OPT(I)K;當(dāng)P*是最大化問題時(shí), YP=(I,K) | OPT(I)K.7.1.3NP類定義7.2 所有多項(xiàng)式時(shí)間可解的判定問題組成的問題類稱作P類.定義7.3 設(shè)判定問題P =, 如果存在兩個(gè)輸入變量的多項(xiàng)式時(shí)間算法 A和多項(xiàng)式 p, 對(duì)每一個(gè)實(shí)例 ID, IY 當(dāng)且僅當(dāng)存在 t, |t| p(|I|), 且 A對(duì)輸入 I 和 t 輸出“Yes”, 則稱P 是多項(xiàng)式時(shí)間可驗(yàn)證的,A是P 的多項(xiàng)式時(shí)間驗(yàn)證算法

12、, 而當(dāng)IY時(shí), 稱 t是IY的證據(jù).由所有多項(xiàng)式時(shí)間可驗(yàn)證的判定問題組成的問題類稱作NP類.例如,HC, TSP, 0-1背包NP非確定型多項(xiàng)式時(shí)間算法非確定型多項(xiàng)式時(shí)間算法:對(duì)給定的實(shí)例 I, 首先“猜想”一個(gè) t,|t| p(|I|), 然后檢查t 是否是證明 IY 的證據(jù), 猜想和檢查可以在多項(xiàng)式時(shí)間內(nèi)完成, 并且當(dāng)且僅當(dāng)t.IY 時(shí)能夠正確地猜想到一個(gè)證據(jù)定理7.1 PNP.問題: P=NP?7.2 多項(xiàng)式時(shí)間變換與NP完全性7.2.1 多項(xiàng)式時(shí)間變換如何比較兩個(gè)問題的難度?定義7.4 設(shè)判定問題P1=, P2=. 如果函數(shù)f:D1 D2滿足條件:(1) f 是多項(xiàng)式時(shí)間可計(jì)算的,(

13、2) 對(duì)所有的ID1, IY1f(I)Y2,則稱 f 是P1到P2的多項(xiàng)式時(shí)間變換.如果存在P1到P2的多項(xiàng)式時(shí)間變換, 則稱P1可多項(xiàng)式時(shí)間變換到P2, 記作P1pP2.例例7.1HCpTSP.證 對(duì)HC的每一個(gè)實(shí)例I: 無(wú)向圖G=, TSP對(duì)應(yīng)的實(shí)例f(I)為: 城市集V, 任意兩個(gè)不同的城市u和v之間的距離d (u, v) = 1,若(u, v) E,否則,2,以及界限D(zhuǎn)=|V|.例最小生成樹: 任給連通的無(wú)向賦權(quán)圖G=以及正整數(shù)B, 其中權(quán)W:EZ+, 問不超過B的生成樹嗎?最大生成樹: 任給連通的無(wú)向賦權(quán)圖G=以及正整數(shù)D, 其中權(quán)W:EZ+, 問G不小于D的生成樹嗎?例7.2 最大

14、生成樹p最小生成樹.證 任給最大生成樹的實(shí)例I:連通的無(wú)向賦權(quán)圖G=和正整數(shù)D, 最小生成樹的對(duì)應(yīng)實(shí)例f(I): 圖G=和正整數(shù)B=(n-1)M-D, 其中n=|V|, M=maxW(e) | eE+1, W (e)=M-W(e). 如果存在G的生成樹T, 使得, 則W (e) DeTW (e) = (n - 1)M - W (e) (n - 1)M - D = B.eTeT反之亦然.p的性質(zhì)定理7.2p具有傳遞性. 即, 設(shè)P1pP2, P2pP3, 則P1pP3. 證 設(shè)Pi=, i=1,2,3, f和g是P1到P2和P2到P3的多項(xiàng)式時(shí)間變換.對(duì)每一個(gè)ID1, 令h(I)=g(f(I).

15、計(jì)算f和g的時(shí)間上界分別為多項(xiàng)式p和q, 不妨設(shè)p和q是單調(diào)遞增的. 計(jì)算h的步數(shù)不超過p(|I|)+ q(|f(I)|). 輸出作為合理的指令, 一步只能輸出長(zhǎng)度不超過固定值k的字符串, 因而|f(I)|kp(|I|). 于是, p(|I|)+ q(|f(I)|) p(|I|)+q(kp(|I|), 得證h 是多項(xiàng)式時(shí)間可計(jì)算的.又, 對(duì)每一個(gè)ID1,IY1 f(I)Y2 h(I) =g(f(I)Y3,得證h是P1到P3的多項(xiàng)式時(shí)間變換.p的性質(zhì)定理7.3 設(shè)P1pP2, 則P2P 蘊(yùn)涵 P1P.證 設(shè)P1=, P2=, f是P1到P2的多項(xiàng)式時(shí)間變換, A是計(jì)算f的多項(xiàng)式時(shí)間算法. 又設(shè)B

16、是P2的多項(xiàng)式時(shí)間算法. 如下構(gòu)造P1的算法C: 對(duì)每一個(gè)ID1, 首先應(yīng)用A得到f(I), 然后對(duì)f(I)應(yīng)用B, C輸出“Yes”當(dāng)且僅當(dāng)B輸出“Yes”.推論7.4設(shè)P1pP2, 則P1是難解的蘊(yùn)涵P2是難解的. 由例7.2及最小生成樹P, 得知最大生成樹P.由例7.1, 如果TSPP, 則HCP. 反過來(lái), 如果HC是難解的,則TSP也是難解的.7.2.2 NP完全性定義7.5 如果對(duì)所有的PNP, P p P, 則稱P 是NP難的.如果P 是NP難的且PNP, 則稱P 是NP完全的.NP完全問題是NP中最難的問題.定理7.5 如果存在NP難的問題PP, 則P=NP.推論7.6 假設(shè)P

17、NP, 那么, 如果P 是NP難的, 則PP.定理7.7 如果存在NP難的問題P 使得 P p P, 則P 是NP 難的.推論7.8 如果PNP并且存在NP完全問題P 使得 P p P,則P 是NP完全的.證明NP完全性的“捷徑”為了證明P 是NP完全的, 只需要做兩件事:(1) 證明PNP;(2) 找到一個(gè)已知的NP完全問題P , 并證明P p P.7.2.3 Cook-Levin定理合式公式是由變?cè)?邏輯運(yùn)算符以及圓括號(hào)按照一定的規(guī)則組成的表達(dá)式. 變?cè)退姆Q作文字. 有限個(gè)文字的析取稱作簡(jiǎn)單析取式. 有限個(gè)簡(jiǎn)單析取式的合取稱作合取范式.給定每一個(gè)變?cè)恼婕僦捣Q作一個(gè)賦值. 如果賦值t使

18、得合式公式F為真, 則稱t是F的成真賦值. 如果F存在成真賦值, 則稱F是可滿足的.F1=( x1 x2)( x1 x2 x3) x2是一個(gè)合取范式.例如令t(x1)=1, t(x2)=0, t(x3)=1是F1的成真賦值,F1是可滿足的.F2=( x1 x2 x3)( x1 x2 x3) x2 x3不是可滿足的.Cook-Levin定理可滿足性(SAT): 任給一個(gè)合取范式F, 問F是可滿足的嗎?定理7.9 (Cook-Levin定理) SAT是NP完全的.定理7.10P=NP的充分必要條件是存在NP完全問題PP.7.3 幾個(gè)NP完全問題SAT恰好覆蓋3SAT最大可滿足性子集和VC有向HCH

19、C雙機(jī)調(diào)度背包集裝箱團(tuán)7.3.1 最大可滿足性與三元可滿足性最大可滿足性(MAX-SAT): 任給關(guān)于變?cè)獂1, x2, xn的簡(jiǎn)單析取式C1,C2,Cm及正整數(shù)K, 問存在關(guān)于變?cè)獂1, x2, xn的賦值使得C1,C2,Cm中至少有K個(gè)為真嗎?設(shè)判定問題P =, P =, 如果DD, Y = DY, 則P 是P 的特殊情況, 稱作P 的子問題.例如“給定一個(gè)平面圖G, 問G是哈密頓圖嗎?”是HC的子問題.SAT是MAX-SAT的子問題:取K=m.MAX-SAT: 如果已知P 的某個(gè)子問題P 是NP難的, 則P 也是NP限比特殊情況容易. 容易把P 多項(xiàng)式時(shí)難的一般情況間變換到P : 只需把

20、P 的實(shí)例I看作P特殊情況的實(shí)例, 即可得到P 對(duì)應(yīng)的實(shí)例.定理7.11MAX-SAT是NP完全的.證 MAX-SAT的非多項(xiàng)式時(shí)間算法: 猜想一個(gè)賦值, 檢查是否有K個(gè)簡(jiǎn)單析取式滿足.要證SATpMAX-SAT. 任給SAT的實(shí)例I: 關(guān)于變?cè)獂1, x2,xn的合取范式F=C1C2Cm, 其中C1,C2,Cm是簡(jiǎn)單析取式, 對(duì)應(yīng)的MAX-SAT的實(shí)例f(I): 簡(jiǎn)單析取式C1,C2,Cm和正整數(shù)K=m.3SAT3元合取范式: 每一個(gè)簡(jiǎn)單析取式恰好有3個(gè)文字的合取范式. 三元可滿足性(3SAT): 任給一個(gè)3元合取范式F, 問F是可滿足的嗎?定理7.123SAT是NP完全的.顯然 3SATN

21、P.證要證 SAT p3SAT. 任給一個(gè)合取范式F, 要構(gòu)造對(duì)應(yīng)的 3元合取范式F = f(F), 使得F是可滿足的當(dāng)且僅當(dāng)F 是可滿足的.設(shè)F =C1C2Cm , 對(duì)應(yīng)的F =F1F2 Fm,Fj 是 對(duì)應(yīng)Cj 的合取范式, 并且Cj是可滿足的當(dāng)且僅當(dāng) Fj是可滿足的.證明(1) Cj=z1. 引入兩個(gè)新變?cè)獃j1, yj2, 令Fj =(z1 yj1 yj2)(z1 yj1 yj2)(z1 yj1 yj2)(z1 yj1 yj2).(2) Cj=z1z2. 引入一個(gè)新變?cè)獃j, 令Fj = (z1 z2 yj)(z1 z2 yj).(3) Cj=z1z2z3. 令 Fj = Cj.(4)

22、 Cj=z1z2zk, k4. 引入k-3個(gè)新變?cè)獃j1, yj2,yj(k-3), 令Fj =(z1 z2 yj1)( yj1 z3 yj2) ( yj2 z4 yj3)( yj(k-4) zk-2 yj(k-3) ( yj(k-3) zk-1 zk). 設(shè)賦值 t 滿足Cj, 則存在i使得 t(zi)=1. 當(dāng)i=1或2時(shí), 令t(yjs)=0 (1sk-3); 當(dāng)i=k-1或k時(shí), 令t(yjs)=1 (1sk-3); 當(dāng)3ik-2時(shí), 令t(yjs)=1(1si-2), t(yjs)=0(i-1sk-3). 則有,t(Fj )=1.證明反之, 設(shè)t(Fj)=1. 若t(yj1)=0,

23、則 t(z1 z2)=1; 若t(yj(k-3)=1, 則 t(zk-1zk)=1; 否則必有s(1sk-4)使得 t(yjs)=1且 t(yj(s+1)=0, 從而t(zs+2)=1. 總之, 都有t(Cj)=1.Fj 中簡(jiǎn)單析取式的個(gè)數(shù)不超過Cj中文字個(gè)數(shù)的4倍, 每個(gè)簡(jiǎn)單析取式有3個(gè)文字, 因此可以在|F|的多項(xiàng)式時(shí)間內(nèi)構(gòu)造出F.局部替換法 要證P1pP2. 當(dāng)P2是P1的子問題或兩者的結(jié)構(gòu)相似時(shí), 往往可以把P1的實(shí)例的每一個(gè)子結(jié)構(gòu)替換成對(duì)應(yīng)的P2實(shí)例的子結(jié)構(gòu).7.3.2 頂點(diǎn)覆蓋、團(tuán)與設(shè)無(wú)向圖G=, V V. V 是G的一個(gè)頂點(diǎn)覆蓋: G的每一條邊都至少有一個(gè)頂點(diǎn)在V 中.團(tuán): 對(duì)任

24、意的u,vV 且uv, 都有(u,v)E.集: 對(duì)任意的u,vV , 都有(u,v)E.集引理7.13 對(duì)任意的無(wú)向圖G=和子集V V, 下述命題是等價(jià)的:(1) V 是G的頂點(diǎn)覆蓋,(2) V-V 是G的集,(3) V-V 是補(bǔ)圖 Gc=的團(tuán).頂點(diǎn)覆蓋、團(tuán)與集頂點(diǎn)覆蓋(VC): 任給一個(gè)無(wú)向圖G=和非負(fù)整數(shù)K|V|,問G有頂點(diǎn)數(shù)不超過K的頂點(diǎn)覆蓋嗎?團(tuán): 任給一個(gè)無(wú)向圖G=和非負(fù)整數(shù)J|V|, 問G有頂點(diǎn)數(shù)不小于J的團(tuán)嗎?集: 任給一個(gè)無(wú)向圖G=和非負(fù)整數(shù)J|V|, 問G有頂點(diǎn)數(shù)不小于J的集嗎?根據(jù)引理7.13, 很容易把這3個(gè)問題中的一個(gè)問題多項(xiàng)式時(shí)間變換到另一個(gè)問題.頂點(diǎn)覆蓋定理7.14

25、 頂點(diǎn)覆蓋是NP完全的.證: VC的非確定型多項(xiàng)式時(shí)間算法: 任意猜想一個(gè)子集VV, |V |K, 檢查V 是否是一個(gè)頂點(diǎn)覆蓋.要證3SATpVC. 任給變?cè)獂1, x2, xn的3元合取范式F=C1C2Cm, 其中Cj=zj1 zj2 zj3, zjk是某個(gè)xi或xi.如下構(gòu)造VC的實(shí)例f(F):G=和K=n+2m, 其中V=V1V2,E=E1E2E3 ,V1= xi,xf| 1iniE1=( xi,xf )| 1ini證明V2=zjk, j| k=1,2,3, 1jm,E2=(zj1, j,zj2, j), (zj2, j,zj3, j), (zj3, j,zj1, j)| 1jm.E3=

26、(zjk, j, zjk )| k=1,2,3, 1jm這里設(shè)Cj=zj1 zj2 zj3, 當(dāng)zjk=xi時(shí), zjk =xi; 當(dāng)zjk= xi時(shí), zjk =xf .i例如, 對(duì)應(yīng)F=(x1x2x3)(x1x2x3)的f(F):K=7, 圖G如下x1xfxxfxxf12233x2, 2xf , 12xf , 33x1, 1x3, 1x1, 2證明要證F是可滿足的G恰好有K個(gè)頂點(diǎn)的頂點(diǎn)覆蓋.任何頂點(diǎn)覆蓋V 在xi和xf中至少取一個(gè), 在z ,j、z,j和ij1j2zj3 ,j中至少取2個(gè),故V 至少有n+2m個(gè)頂點(diǎn). 而K=n+2m, 故任何頂點(diǎn)數(shù)不超過K的頂點(diǎn)覆蓋V 恰好包含K個(gè)頂點(diǎn),

27、且在xi和 xf 中取一個(gè), 這恰好對(duì)應(yīng)對(duì)x 的賦值, 取x 對(duì)應(yīng)t(x )=1,取xfiiiii對(duì)應(yīng)t(xi)=0; 每個(gè)三角形的頂點(diǎn)zj1,j、zj2,j和zj3,j中取2個(gè).設(shè)t是F的成真賦值, 對(duì)每一個(gè)i(1in), 若t(xi)=1, 則取xi; 若t(xi)=0, 則取xfi . 這n個(gè)頂點(diǎn)覆蓋E1. 對(duì)每一個(gè)j(1jm), 由于t(Cj)=1, Cj至少有一個(gè)文字zjk的值為1. 于是, 從對(duì)應(yīng)的三角形的頂點(diǎn)zjk,j引出的邊(zjk,j, zjk )已被覆蓋. 取該三角形的另外2個(gè)頂點(diǎn), 這就覆蓋了這個(gè)三角形的3條邊和引出的另外2條邊. 這樣取到的n+2m個(gè)頂點(diǎn)是G的一個(gè)頂點(diǎn)覆

28、蓋.證明反之, 設(shè)V V是G的一個(gè)頂點(diǎn)覆蓋且| V |K=n+2m. 根據(jù)前面的分析, 每一對(duì)xi和 xf 中恰好有一個(gè)屬于V, 每一個(gè)三角形恰i好有2個(gè)頂點(diǎn)屬于V. 對(duì)每一個(gè)i(1in), 若xiV, 則令t(xi)=1;若 xf V, 則令t(x )=0. 對(duì)每一個(gè)j(1jm), 設(shè)z ,jV, 為了覆iijk蓋邊(zjk,j, zjk ), 必有 zjkV. 由于t(zjk)=1, 從而t(Cj)=1. 因此, t是F的成真賦值, 得證F是可滿足的.G有2n+3m個(gè)頂點(diǎn)和n+6m條邊, 顯然能在多項(xiàng)式時(shí)間內(nèi)構(gòu)造G和K,定理7.15集和團(tuán)是NP完全的.構(gòu)件設(shè)計(jì)法構(gòu)件設(shè)計(jì)法 定理7.14證明

29、中設(shè)計(jì)了2種“構(gòu)件” 變?cè)獦?gòu)件和簡(jiǎn)單析取式構(gòu)件. 變?cè)獦?gòu)件是一對(duì)頂點(diǎn)xi, xf及連接它們i的邊; 簡(jiǎn)單析取式構(gòu)件是三角形. 用這些構(gòu)件及構(gòu)件之間的連G, 每個(gè)構(gòu)件各有其功能, 通過這種方式到達(dá)用VC的實(shí)接例表達(dá)3SAT的實(shí)例的目的.7.3.3 哈密頓回路與貨郎問題有向哈密頓回路: 任給有向圖D, 問:D中有哈密頓回路嗎? 定理7.16 有向HC是NP完全的.證 要證3SATp有向HC. 任給變?cè)獂1, x2, xn的3元合取范式F=C1C2Cm, 其中Cj=zj1 zj2 zj3, 每個(gè)zjk是某個(gè)xi或xi.采用構(gòu)件設(shè)計(jì)法構(gòu)造有向圖D. 表示變?cè)獂i的構(gòu)件是一條由一串水平的頂點(diǎn)組成的鏈Li

30、, 相鄰的兩個(gè)頂點(diǎn)之間有一對(duì)方向相反的有向邊. 只有兩種可能的方式通過Li上的所有頂點(diǎn)從左到右或者從右到左通過Li上的所有頂點(diǎn), 這恰好對(duì)應(yīng)xi的值為1或者為0. 表示簡(jiǎn)單析取式Cj的構(gòu)件是一個(gè)頂點(diǎn)cj.添加s0, s1, xn, 并通過它們把L1, L2, Ln連接起來(lái).證明關(guān)鍵是兩種構(gòu)件之間的連接: 鏈Li有3m+1的頂點(diǎn), 依次為di0, ai1, bi1, di1, ai2, bi2, di2, , aim, bim, dim. 對(duì)每一個(gè)Cj=zj1 zj2 zj3, 如果zjk=xi, 則添加和; 如果zjk=xi, 則添加 和.例如 C2=x1x3x4對(duì)應(yīng)的連接證明設(shè)F是可滿足的,

31、 t是F的成真賦值. 要根據(jù)t構(gòu)造一條從s0到sn, 最后回到s0的哈密頓回路, 先暫時(shí)不考慮所有的cj.依次對(duì)i=1,2,n進(jìn)行, 若t(xi)=1, 則從si-1到di0, 從左到右經(jīng)過Li的所有頂點(diǎn)到達(dá)dim, 再到si; 若t(xi)=0, 則從si-1到dim, 從右到左經(jīng)過Li 的所有頂點(diǎn)到達(dá)di0, 再到si. 最后, 從sn回到s0. 現(xiàn)在要將所有cj這條回路. 設(shè)Cj=zj1 zj2 zj3, 由于t(Cj)=1, 必有k(1k3)使得t(zjk)=1. 若zjk =xi, 則通路從左到右經(jīng)過Li, 且有有向邊和. 于是, 可以把cj插在aij與bij之間; 若zjk = x

32、i,則通路從右到左經(jīng)過Li, 且有有向邊和. 于是, 可以把cj插在bij與aij之間. 這就得到D中的一條哈密頓回路.證明反之, 設(shè)D有一條哈密頓回路P, P必須從sn到s0. 不妨設(shè)P從s0 開始到sn, 最后回到s0結(jié)束. 我們稱上面構(gòu)造的那種哈密頓回路是正常的, 即正常的回路從左到右或者從右到左通過每一條Li, 每一個(gè)cj插在某個(gè)aij和bij或者bij和aij之間. 如果P是正常的, 容易根據(jù)P規(guī)定F的一個(gè)成真賦值t: 若P從左到右通過Li,則令t(xi)=1; 若P從右到左通過Li, 則令t(xi)=0. 根據(jù)cj方式, 不難證明必有t(Cj)=1.Li的要證P一定是正常的. 假設(shè)

33、不然, 破壞正常性的惟一可能是P從某條鏈Ls上的頂點(diǎn)u到cj后沒有回到同一條鏈中的頂點(diǎn), 而是到另一條鏈Lt(st)中的頂點(diǎn). 若u=asj, 由于bsj只與asj、 cj及dsj證明相鄰, P已經(jīng)過asj和cHC與TSP定理7.17HC是NP完全的.證 要證有向HC p HC. 任給一個(gè)有向圖D=, 要構(gòu)造無(wú)向圖G=使D有哈密頓回路當(dāng)且僅當(dāng)G有哈密頓回路.把D的每一個(gè)頂點(diǎn)v替換成3個(gè)頂點(diǎn)vin, vmid和vout, 用邊連接vin和vmid, vmid和vout. D的每條有向邊在G中換成( uout, vin).V = vin, vmid, vout | vV ,E =( uout, v

34、in) | E(vin,vmid),( vmid,vout) | vV .即定理17.18TSP是NP完全的.7.3.4 恰好覆蓋恰好覆蓋: 給定有窮集A=a1, a2, an和A的子集的集合W=S1, S2, S m, 問: 存在子集UW使得U中的子集都是不相交的且它們的并集等于A? 稱W這樣的子集U是A的恰好覆蓋. 例如, 設(shè)A=1,2,3,4,5, S1=1,2, S2=1,3,4, S3=2,4, S4=2,5,則 S2, S4是A的恰好覆蓋. 若把S4改為S4=3,5, 則不存在A的恰好覆蓋.定理7.19 恰好覆蓋是NP完全的.證明證 要證可滿足性p恰好覆蓋. 任給變?cè)獂1, x2,

35、 xn的合取范式F=C1C2Cm, 其中 Cj= z j1 z j 2 L, z js. 取jA=x1, x2, xn,C1,C2,Cm pjt | 1tsj, 1jm,其中pjt代表Cj中的文字zjt.W包含下述子集:TT = x , p | z =x , 1ts , 1jm,1in,iijtjtijTF = x , p | z =x , 1ts , 1jm,1in,iijtjtijCjt =Cj, pjt, 1tsj, 1jm. pjt , 1tsj, 1jm.要證F是可滿足的當(dāng)且僅當(dāng)W含有A的恰好覆蓋. 設(shè)UW是A的恰好覆蓋, 對(duì)每一個(gè)i, 若 TTi U, 則令t(xi)=1;若TF

36、U, 則令it(xi)=0. 對(duì)每一個(gè)j, 必有一個(gè)Cjt=Cj, pjtU.zjt=xi或xi . 若TTU, 則pjtTT, 從而z =x . 有t(x )=1, 故t滿足C .iijtiij證明若TFiU, 則pjtTFi , 從而zjt =xi. 有t(xi)=0, 故t也滿足Cj. 得證t是F的成真賦值.反之, 設(shè)t是F的成真賦值. 對(duì)每一個(gè)i, 若t(xi)=1, 則U包含TTi; 若t(xi)=0, 則U包含TFi . 對(duì)每一個(gè)j, 由于t滿足Cj, Cj必有一個(gè)文字zjt使得t(zjt)=1, 從而U中現(xiàn)有的子集不包含pjt. 于是, 可以把Cjt加入U(xiǎn). 至此, U覆蓋了所有

37、的xi和Cj, 以及部分pjt. 最后, 把那些尚未被覆蓋的pjt的恰好覆蓋.的單元子集pjt加入U(xiǎn), 即可得到A由于F中的文字?jǐn)?shù)不超過mn, 故|A|n+m+mn, W中的子集數(shù)不超過2n+2mn, 每個(gè)子集的大小不超過n+1.而且構(gòu)造很簡(jiǎn)單, 顯然可以在多項(xiàng)式時(shí)間內(nèi)完成.7.3.5 子集和,背包,裝箱與雙機(jī)調(diào)度子集和: 給定正整數(shù)集合X=x1, x2, xn及正整數(shù)N, 問存在X的子集T, 使得T中的元和等于N嗎?裝箱: 給定n件物品, 物品j的重量為正整數(shù)wj, 1jn, 以及箱子數(shù)K. 規(guī)定每只箱子裝入物品的總重量不超過正整數(shù)B, 問能用K只箱子裝入所有的物品嗎?雙機(jī)調(diào)度: 有2臺(tái)和n項(xiàng)作業(yè)J1, J2, Jn, 這2臺(tái)完全相同, 每一項(xiàng)作業(yè)可以在任一臺(tái)上進(jìn)行, 沒有先后順序,作業(yè)Ji的處理時(shí)間為ti, 1in, 截止時(shí)間為D, 所有ti和D都是正整數(shù), 問能把n項(xiàng)作業(yè)分