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

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

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

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

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

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

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

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

8、雜性(Parameterized Complexity)如果參數(shù)化問(wèn)題如果參數(shù)化問(wèn)題Q Q可在可在O(f(k)nO(f(k)nc c) )時(shí)間內(nèi)被求解時(shí)間內(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àng)式部分出現(xiàn)僅在多項(xiàng)式部分出現(xiàn)第15頁(yè)參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameter

9、ized Complexity)參數(shù)計(jì)算理論對(duì)問(wèn)題的難解性參數(shù)計(jì)算理論對(duì)問(wèn)題的難解性重新進(jìn)行了劃分重新進(jìn)行了劃分：NP難解問(wèn)題難解問(wèn)題固定參數(shù)可解固定參數(shù)可解O(f(k)nO(f(k)nc c) )不存在不存在O(f(k)nO(f(k)nc c) )算法算法固定參數(shù)不可解固定參數(shù)不可解尋找尋找k大小的點(diǎn)覆蓋大小的點(diǎn)覆蓋尋找長(zhǎng)度為尋找長(zhǎng)度為k的簡(jiǎn)單的簡(jiǎn)單路徑路徑尋找尋找k個(gè)不相交的三個(gè)不相交的三角形角形刪除刪除k個(gè)點(diǎn)使給定圖個(gè)點(diǎn)使給定圖無(wú)圈無(wú)圈最大團(tuán)最大團(tuán)獨(dú)立集獨(dú)立集支配集支配集第16頁(yè)參數(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獨(dú)立集獨(dú)立集 W1支配集支配集 W2第17頁(yè)參數(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頁(yè)參數(shù)復(fù)雜性參數(shù)復(fù)雜性(Parameterized Complexity)NP-完全理論與

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

12、x Cover)e=(x1, y1)x1y1e=(x2, y2)x2y2.樹(shù)中葉子的樹(shù)中葉子的數(shù)量數(shù)量2kk 第20頁(yè)分支界定分支界定用用T(k)T(k)表示在點(diǎn)覆蓋集分支搜索樹(shù)的大表示在點(diǎn)覆蓋集分支搜索樹(shù)的大小小= =算法的運(yùn)行時(shí)間算法的運(yùn)行時(shí)間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頁(yè)彩色編碼彩色編碼(Color-Coding)給定圖給定圖G=G=( (V, EV, E) )，正整數(shù)，正整數(shù)k k，點(diǎn)，點(diǎn)s, ts, t，尋找，尋找G G中一條從中一條從s s到到t t且含有且含有k k個(gè)中間個(gè)中間點(diǎn)的點(diǎn)的簡(jiǎn)單路徑簡(jiǎn)單路徑，或返回，或返回G G中不存在這樣的簡(jiǎn)單路徑。中不存在這樣的簡(jiǎn)單路徑。k-(s, t)-k-(s, t)-路徑問(wèn)題路徑問(wèn)題s st t

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

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

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

17、個(gè)點(diǎn)對(duì)應(yīng)的所有可能顏色個(gè)點(diǎn)對(duì)應(yīng)的所有可能顏色k! k!第26頁(yè)彩色編碼彩色編碼(Color-Coding)2 21 1 3 3k ks st t第27頁(yè)彩色編碼彩色編碼(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頁(yè)彩色編碼彩色編碼(Color-Coding)算法的時(shí)間復(fù)雜度：算法的時(shí)間復(fù)雜度：1. 1. 基于著色對(duì)路徑的求解：基于著色對(duì)路徑的求解：k!

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

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

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