參數(shù)計算簡介（NP-難問題的算法設(shè)計與分析）

1、整理課件整理課件參數(shù)計算簡介參數(shù)計算簡介(NP-難問題的算法設(shè)計與分析難問題的算法設(shè)計與分析)馮啟龍 第第2頁頁提綱提綱 NP完全理論完全理論 參數(shù)計算理論參數(shù)計算理論 分支界定分支界定 彩色編碼彩色編碼 核心化核心化第3頁NP完全理論完全理論多項式可解多項式可解PNP難解難解問題問題 各領(lǐng)域中的各領(lǐng)域中的可計算可計算問題問題最小生成樹最小生成樹最短路徑最短路徑最大流問題最大流問題最大匹配問題最大匹配問題頂點覆蓋頂點覆蓋最大團(tuán)最大團(tuán)獨立集獨立集旅行商問題旅行商問題NP完全理論完全理論多項式可解多項式可解P多項式可解多項式可解PNP難解難解問題問題多項式可解多項式可解PNP難解難解問題問題多項式

2、可解多項式可解PNP難解難解問題問題多項式可解多項式可解P最小生成樹最小生成樹最短路徑最短路徑最大流問題最大流問題最大匹配問題最大匹配問題頂點覆蓋頂點覆蓋最大團(tuán)最大團(tuán)獨立集獨立集旅行商問題旅行商問題最小生成樹最小生成樹最短路徑最短路徑最大流問題最大流問題最大匹配問題最大匹配問題第4頁NP:在多項式時間內(nèi)被驗證，僅回答在多項式時間內(nèi)被驗證，僅回答Yes或或No(判定問題判定問題) 如何判定給定問題是否在如何判定給定問題是否在NP中？中？給定圖給定圖G G=(=(V V, , E E) )，問圖，問圖G G中是否存在中是否存在V V的一個大小不超過的一個大小不超過k k的子集的子集V V，使得，使

3、得E E中的任意一條邊中的任意一條邊e, ee, e至少有一個端點被包含在至少有一個端點被包含在V V中。中。 點覆蓋點覆蓋給定給定V V的任意一個子集的任意一個子集V1, V1, 如果可在如果可在多項式時間內(nèi)多項式時間內(nèi)判定判定V1V1是否為點覆蓋問題的解，則說明點覆蓋問題在是否為點覆蓋問題的解，則說明點覆蓋問題在NP NP 中。中。NP完全理論完全理論第5頁給定完全圖給定完全圖G=(V, E)，其中每條邊賦有一定的權(quán)值，并給定參數(shù)，其中每條邊賦有一定的權(quán)值，并給定參數(shù)K，問問G中是否存在一條權(quán)值小于等于中是否存在一條權(quán)值小于等于K且包括圖中所有點的圈。且包括圖中所有點的圈。 旅行商問題旅行

4、商問題 給定給定G中的任意一個圈中的任意一個圈S, 可在可在多項式時間內(nèi)多項式時間內(nèi)判定判定S是否為是否為旅行商問題的解。旅行商問題的解。NP完全理論完全理論第6頁多項式規(guī)約多項式規(guī)約Q1 xQ2r(x)多項式時間多項式時間YesYesYesYesNP完全理論完全理論第7頁NP-NP-難難NP中的中的任意問題任意問題Q多項式規(guī)約多項式規(guī)約問題問題Q Q 是是NP-NP-難的難的NP完全理論完全理論第8頁NP-NP-完全完全NP-難難 +在在NP中中Q問題問題Q Q 是是NP-NP-完全的完全的NP完全理論完全理論第9頁可滿足性問題可滿足性問題(Satisfiability)NP中的中的任意問題

5、任意問題可滿足可滿足性問題性問題多項式規(guī)約多項式規(guī)約可滿足性問題可滿足性問題是是NP-NP-難的難的NP完全理論完全理論給定一個合取范式，是否存在對給定一個合取范式，是否存在對F中變量的一個賦值使得中變量的一個賦值使得F為真為真? 可滿足性問題可滿足性問題可滿足性問題在可滿足性問題在NP中中可滿足性問題可滿足性問題NP-完全完全第10頁怎樣證明某個問題是怎樣證明某個問題是NP難的？難的？Q1 xQ2r(x)多項式時間多項式時間YesYesYesYesNP完全理論完全理論第11頁關(guān)系圖關(guān)系圖: P, NP, NP-: P, NP, NP-難難, NP-, NP-完全完全NP完全理論完全理論第12

6、頁 哪些問題是哪些問題是NP-難的難的,但不是屬于但不是屬于NP?NP完全理論完全理論判斷任意一個給定程序是否會在有限的時間之內(nèi)結(jié)束運(yùn)行。判斷任意一個給定程序是否會在有限的時間之內(nèi)結(jié)束運(yùn)行。 停機(jī)問題停機(jī)問題(Halting(HaltingProblem)Problem) 哪些問題屬于哪些問題屬于NP,介于介于P與與NP-完全之間完全之間?給定圖給定圖G G和和H H，判斷，判斷G G和和H H是否同構(gòu)？是否同構(gòu)？圖同構(gòu)問題圖同構(gòu)問題(Graph isomorphism)(Graph isomorphism)給定整數(shù)給定整數(shù)N N和和MM，判斷，判斷N N是否有一個比是否有一個比MM小的因子小

7、的因子? ?整數(shù)分解整數(shù)分解(Integer factorization)(Integer factorization)第13頁參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameterized Complexity)點覆蓋點覆蓋獨立集獨立集輸入輸入圖圖G, 整數(shù)整數(shù)k圖圖G, 整數(shù)整數(shù)k問題問題是否可用是否可用k k條點覆條點覆蓋蓋G G中的所有邊中的所有邊? ?是否存在是否存在k k個相互獨立的個相互獨立的點點( (兩兩之間沒邊兩兩之間沒邊)? )?復(fù)雜性復(fù)雜性NP-完全完全NP-完全完全枚舉枚舉O(nk)O(nk)O(2kn2)參數(shù)計算參數(shù)計算不存在不存在O(no(k)的算法的算法第14頁參數(shù)復(fù)雜性參數(shù)復(fù)

8、雜性(Parameterized Complexity)如果參數(shù)化問題如果參數(shù)化問題Q Q可在可在O(f(k)nO(f(k)nc c) )時間內(nèi)被求解時間內(nèi)被求解, ,其中其中c c為常數(shù)為常數(shù), ,則稱則稱Q Q是是固定參數(shù)可解的。固定參數(shù)可解的。 固定參數(shù)可解固定參數(shù)可解(Fixed Parameter Tractable, FPT)(Fixed Parameter Tractable, FPT)基本思想基本思想傳統(tǒng)精確算法傳統(tǒng)精確算法指數(shù)底與指數(shù)底與n有關(guān)有關(guān)參數(shù)算法參數(shù)算法指數(shù)僅與指數(shù)僅與k有關(guān)有關(guān),n僅在多項式部分出現(xiàn)僅在多項式部分出現(xiàn)第15頁參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameter

9、ized Complexity)參數(shù)計算理論對問題的難解性參數(shù)計算理論對問題的難解性重新進(jìn)行了劃分重新進(jìn)行了劃分：NP難解問題難解問題固定參數(shù)可解固定參數(shù)可解O(f(k)nO(f(k)nc c) )不存在不存在O(f(k)nO(f(k)nc c) )算法算法固定參數(shù)不可解固定參數(shù)不可解尋找尋找k大小的點覆蓋大小的點覆蓋尋找長度為尋找長度為k的簡單的簡單路徑路徑尋找尋找k個不相交的三個不相交的三角形角形刪除刪除k個點使給定圖個點使給定圖無圈無圈最大團(tuán)最大團(tuán)獨立集獨立集支配集支配集第16頁參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameterized Complexity)固定參數(shù)不可解固定參數(shù)不可解W框架，框

10、架，W1, W2. Q1 (x, k) Q2(x, k)固定參數(shù)可解固定參數(shù)可解規(guī)約規(guī)約 Q1 Yes Q2 Yes Q2 Yes Q1 Yes固定參數(shù)可解規(guī)約固定參數(shù)可解規(guī)約O(f(k)nO(f(k)nc c) )最大團(tuán)最大團(tuán)W1獨立集獨立集 W1支配集支配集 W2第17頁參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameterized Complexity) Q1 (x, k) Q2(x, k)固定參數(shù)可解固定參數(shù)可解規(guī)約規(guī)約 Q1 W1 Q2 W1O(f(k)nO(f(k)nc c) )W難度的證明難度的證明第18頁參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameterized Complexity)NP-完全理論與

11、參數(shù)計算理論的關(guān)系：完全理論與參數(shù)計算理論的關(guān)系：各領(lǐng)域中可計算問題各領(lǐng)域中可計算問題易解問題易解問題(P)難難解解問問題題難難解解問問題題固定參數(shù)可解固定參數(shù)可解固定參數(shù)不可解固定參數(shù)不可解O(f(k)nO(f(k)nc c) )W1, W2.第19頁分支界定分支界定(Branch-and-Bound)給定圖給定圖G G(V, E)(V, E)和正整數(shù)和正整數(shù)k k，問，問V V是否存在一個大小不超過是否存在一個大小不超過k k的子集的子集VV，使得，使得E E中的任意一條邊至少有一個端點在中的任意一條邊至少有一個端點在VV中。中。點覆蓋問題點覆蓋問題(Vertex Cover)(Verte

12、x Cover)e=(x1, y1)x1y1e=(x2, y2)x2y2.樹中葉子的樹中葉子的數(shù)量數(shù)量2kk 第20頁分支界定分支界定用用T(k)T(k)表示在點覆蓋集分支搜索樹的大表示在點覆蓋集分支搜索樹的大小小= =算法的運(yùn)行時間算法的運(yùn)行時間T(k)T(k) T(k-1)+T(k-1)T(k-1)+T(k-1)T(k)T(k) 2kT(k)T(k) T(k-1)+T(k-2)T(k-1)+T(k-2)分支遞歸式的求解分支遞歸式的求解1. 1. 給出特征方程給出特征方程x xk k=x=xk-1k-1+x+xk-2k-2x x2 2-x-1=0-x-1=02. 2. 解特征方程解特征方程x

13、 x1 1=(1+squrt(5)/2=(1+squrt(5)/2x x2 2=(1-squrt(5)/2=(1-squrt(5)/23. 3. 基于方程根得分支復(fù)雜度基于方程根得分支復(fù)雜度T(k)T(k) x1k 第21頁彩色編碼彩色編碼(Color-Coding)給定圖給定圖G=G=( (V, EV, E) )，正整數(shù)，正整數(shù)k k，點，點s, ts, t，尋找，尋找G G中一條從中一條從s s到到t t且含有且含有k k個中間個中間點的點的簡單路徑簡單路徑，或返回，或返回G G中不存在這樣的簡單路徑。中不存在這樣的簡單路徑。k-(s, t)-k-(s, t)-路徑問題路徑問題s st t

14、引入引入k k種顏色種顏色1,2, k1,2, k，將，將Vs, tVs, t中的點中的點隨機(jī)著色隨機(jī)著色，使得，使得從從s s到到t t簡單路徑上的簡單路徑上的k k個中間點被著上了不同的顏色個中間點被著上了不同的顏色第22頁彩色編碼彩色編碼(Color-Coding)s st tk=5k=5k k個中間點被正確著色的概率（每個點被著了不同的顏色）個中間點被正確著色的概率（每個點被著了不同的顏色）k k個中間點總共的著色情況：個中間點總共的著色情況：k k個中間點被正確著色的情況：個中間點被正確著色的情況：k kk kk! k!k!/kk!/kk k(k/2)(k/2)k k/k/kk k=

15、e=e-k -k. .第23頁彩色編碼彩色編碼(Color-Coding)對于對于每次每次隨機(jī)著色，隨機(jī)著色，k k個中間點被正確著色的概率個中間點被正確著色的概率: :e e-k -k為了保證成功的高概率，重復(fù)著色過程為了保證成功的高概率，重復(fù)著色過程e ek k次次重復(fù)重復(fù)e ek k次著色過程，次著色過程，k k個中間點仍沒有被正確著色的概率：個中間點仍沒有被正確著色的概率：(1-e(1-e-k -k) )e ek k=e=e-1 -10.38.0.38.為了進(jìn)一步降低錯誤的概率，可重復(fù)為了進(jìn)一步降低錯誤的概率，可重復(fù)100e100ek k次次錯誤的概率為：錯誤的概率為：1/e1/e10

16、0100. .第24頁彩色編碼彩色編碼(Color-Coding)s st t假設(shè)假設(shè)G G中從中從s s到到t t含有含有k k個中間結(jié)個中間結(jié)點的簡單路徑已被正確著色點的簡單路徑已被正確著色怎樣基于著色找到該路徑？怎樣基于著色找到該路徑？Vs, tVs, t的點的點C1C1C2C2C3C3CkCk第25頁彩色編碼彩色編碼(Color-Coding)Vs, tVs, t的點的點C1C1C2C2C3C3CkCks st t1 12 23 3k k第第i i個點在哪個顏色筐中？個點在哪個顏色筐中？(1 (1 i i k) k)枚舉枚舉枚舉第枚舉第1 1個點、第個點、第2 2個點、個點、第第k k

17、個點對應(yīng)的所有可能顏色個點對應(yīng)的所有可能顏色k! k!第26頁彩色編碼彩色編碼(Color-Coding)2 21 1 3 3k ks st t第27頁彩色編碼彩色編碼(Color-Coding)2 21 1 3 3k ks st t怎樣求解？怎樣求解？深度優(yōu)先深度優(yōu)先(Breath First Search)(Breath First Search)廣度優(yōu)先廣度優(yōu)先(Depth First Search)(Depth First Search)第28頁彩色編碼彩色編碼(Color-Coding)算法的時間復(fù)雜度：算法的時間復(fù)雜度：1. 1. 基于著色對路徑的求解：基于著色對路徑的求解：k!

18、k!2. 2. 著色的次數(shù)：著色的次數(shù)：e ek k3. 3. 總的時間復(fù)雜度：總的時間復(fù)雜度：e ek k k! |E|k! |E|如何改進(jìn)？如何改進(jìn)？第29頁彩色編碼彩色編碼(Color-Coding)假設(shè)假設(shè)G G中從中從s s到到t t含有含有k k個中間結(jié)個中間結(jié)點的簡單路徑已被正確著色點的簡單路徑已被正確著色怎樣基于著色找到該路徑？怎樣基于著色找到該路徑？s st ts st t最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)s s第第i i個點個點如何基于第如何基于第i i個點得到第個點得到第i+1i+1個點個點第30頁彩色編碼彩色編碼(Color-Coding)動態(tài)規(guī)劃動態(tài)規(guī)劃對于圖中的任一點對于圖中的任

19、一點v v，需要記錄從，需要記錄從s s出發(fā)到達(dá)出發(fā)到達(dá)v v的彩色路徑的的彩色路徑的可能顏色集可能顏色集。s st tv1v1v1v1點記錄的信息：點記錄的信息：藍(lán)藍(lán), ,紫紫, , 綠綠, , 藍(lán)藍(lán), , 黃黃, , 綠綠v2v2v2v2點記錄的信息：點記錄的信息：藍(lán)藍(lán), ,紫紫, , 綠綠, , 黃黃, , 紅紅, , 藍(lán)藍(lán), , 黃黃, , 紅紅第31頁彩色編碼彩色編碼(Color-Coding)假設(shè)用假設(shè)用Qi=C1, C2, ChQi=C1, C2, Ch表示表示v v點記錄的從點記錄的從s s出發(fā)到達(dá)出發(fā)到達(dá)v v且長且長度為度為i i的所有彩色路徑對應(yīng)的顏色集合。的所有彩色路徑

20、對應(yīng)的顏色集合。h h的取值范圍：的取值范圍：1 1 h h (k choose i).(k choose i).如何基于得到從如何基于得到從s s出發(fā)經(jīng)過頂點出發(fā)經(jīng)過頂點v v的的長度為長度為i+1i+1的彩色路徑。的彩色路徑。 for v for v的每一個鄰居的每一個鄰居u dou do for j=1 to h for j=1 to h if u if u的顏色沒有被包含在的顏色沒有被包含在Cj Cj 中中 thenthen Cj=Cj u Cj=Cj u的顏色的顏色; ; if Qi+1 if Qi+1中沒有一個集合用到的顏色與中沒有一個集合用到的顏色與CjCj相同相同 then then Qi+1= Qi+1 Cj; Qi+1= Qi+1 Cj; 第32頁彩色編碼彩色編碼(Color-Coding)算法的時間復(fù)雜度：算法的時間復(fù)雜度：1. 1. 基于著色對路徑的求解：基于著色對路徑的求解：|E|2|E|2k k2. 2. 著色的次數(shù)：著色的次數(shù)：e ek k3. 3. 總的時間復(fù)雜度：總的時間復(fù)雜度：e ek k 2 2k k|E|=(2e)|E|=(2e)k k|E|E|第33頁核心化核心化(Kernelization) Q1 (x, k