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

2、，僅回答Yes或No(判定問題),如何判定給定問題是否在NP中？,給定圖G=(V, E)，問圖G中是否存在V的一個大小不超過k的子集V，使得E中的任意一條邊e, e至少有一個端點被包含在V中。,點覆蓋,給定V的任意一個子集V1, 如果可在多項式時間內(nèi)判定V1是否為點覆蓋問題的解，則說明點覆蓋問題在NP 中。,NP完全理論,第5頁,給定完全圖G=(V, E)，其中每條邊賦有一定的權(quán)值，并給定參數(shù)K，問G中是否存在一條權(quán)值小于等于K且包括圖中所有點的圈。,旅行商問題,給定G中的任意一個圈S, 可在多項式時間內(nèi)判定S是否為旅行商問題的解。,NP完全理論,第6頁,多項式規(guī)約,Q1 x,Q2 r(x),

3、多項式時間,Yes,Yes,Yes,Yes,NP完全理論,第7頁,NP-難,NP中的任意問題,Q,多項式規(guī)約,問題Q 是NP-難的,NP完全理論,第8頁,NP-完全,NP-難 + 在NP中,Q,問題Q 是NP-完全的,NP完全理論,第9頁,可滿足性問題(Satisfiability),NP中的任意問題,可滿足性問題,多項式規(guī)約,可滿足性問題是NP-難的,NP完全理論,給定一個合取范式，是否存在對F中變量的一個賦值使得F為真?,可滿足性問題,可滿足性問題在NP中,可滿足性問題NP-完全,第10頁,怎樣證明某個問題是NP難的？,Q1 x,Q2 r(x),多項式時間,Yes,Yes,Yes,Yes,

4、NP完全理論,第11頁,關(guān)系圖: P, NP, NP-難, NP-完全,NP完全理論,第12頁,哪些問題是NP-難的,但不是屬于NP?,NP完全理論,判斷任意一個給定程序是否會在有限的時間之內(nèi)結(jié)束運行。,停機問題(HaltingProblem),哪些問題屬于NP,介于P與NP-完全之間?,給定圖G和H，判斷G和H是否同構(gòu)？,圖同構(gòu)問題(Graph isomorphism),給定整數(shù)N和M，判斷N是否有一個比M小的因子?,整數(shù)分解(Integer factorization),第13頁,參數(shù)復(fù)雜性(Parameterized Complexity),點覆蓋,獨立集,輸入,圖G, 整數(shù)k,圖G,

5、整數(shù)k,問題,是否可用k條點覆蓋G中的所有邊?,是否存在k個相互獨立的點(兩兩之間沒邊)?,復(fù)雜性,NP-完全,NP-完全,枚舉,O(nk),O(nk),O(2kn2),參數(shù)計算,不存在O(no(k)的算法,第14頁,參數(shù)復(fù)雜性(Parameterized Complexity),如果參數(shù)化問題Q可在O(f(k)nc)時間內(nèi)被求解,其中c為常數(shù),則稱Q是固定參數(shù)可解的。,固定參數(shù)可解(Fixed Parameter Tractable, FPT),基本思想,傳統(tǒng)精確算法,指數(shù)底與n有關(guān),參數(shù)算法,指數(shù)僅與k有關(guān),n僅在多項式部分出現(xiàn),第15頁,參數(shù)復(fù)雜性(Parameterized Compl

6、exity),參數(shù)計算理論對問題的難解性重新進行了劃分：,NP難解問題,固定參數(shù)可解,O(f(k)nc),不存在O(f(k)nc)算法,固定參數(shù)不可解,尋找k大小的點覆蓋,尋找長度為k的簡單路徑,尋找k個不相交的三角形,刪除k個點使給定圖無圈,最大團 獨立集 支配集 ,第16頁,參數(shù)復(fù)雜性(Parameterized Complexity),固定參數(shù)不可解,W框架，W1, W2.,Q1 (x, k),Q2 (x, k),固定參數(shù)可解規(guī)約,Q1 Yes,Q2 Yes,Q2 Yes,Q1 Yes,固定參數(shù)可解規(guī)約,O(f(k)nc),最大團W1 獨立集 W1 支配集 W2,第17頁,參數(shù)復(fù)雜性(P

7、arameterized Complexity),Q1 (x, k),Q2 (x, k),固定參數(shù)可解規(guī)約,Q1 W1,Q2 W1,O(f(k)nc),W難度的證明,第18頁,參數(shù)復(fù)雜性(Parameterized Complexity),NP-完全理論與參數(shù)計算理論的關(guān)系：,各領(lǐng)域中可計算問題,易解問題(P),難 解 問 題,難 解 問 題,固定參數(shù)可解,固定參數(shù)不可解,O(f(k)nc),W1, W2.,第19頁,分支界定(Branch-and-Bound),給定圖G(V, E)和正整數(shù)k，問V是否存在一個大小不超過k的子集V，使得E中的任意一條邊至少有一個端點在V中。,點覆蓋問題(Ver

8、tex Cover),e=(x1, y1),x1,y1,e=(x2, y2),x2,y2,. . .,樹中葉子的數(shù)量2k,k,第20頁,分支界定,用T(k)表示在點覆蓋集分支搜索樹的大小=算法的運行時間,T(k) T(k-1)+T(k-1),T(k) 2k,T(k) T(k-1)+T(k-2),分支遞歸式的求解,1. 給出特征方程,xk=xk-1+xk-2,x2-x-1=0,2. 解特征方程,x1=(1+squrt(5)/2,x2=(1-squrt(5)/2,3. 基于方程根得分支復(fù)雜度,T(k) x1k,第21頁,彩色編碼(Color-Coding),給定圖G=(V, E)，正整數(shù)k，點s,

9、 t，尋找G中一條從s到t且含有k個中間點的簡單路徑，或返回G中不存在這樣的簡單路徑。,k-(s, t)-路徑問題,s,t,引入k種顏色1,2, k，將Vs, t中的點隨機著色，使得從s到t簡單路徑上的k個中間點被著上了不同的顏色,第22頁,彩色編碼(Color-Coding),s,t,k=5,k個中間點被正確著色的概率（每個點被著了不同的顏色）,k個中間點總共的著色情況：,k個中間點被正確著色的情況：,kk,k!,k!/kk(k/2)k/kk=e-k.,第23頁,彩色編碼(Color-Coding),對于每次隨機著色，k個中間點被正確著色的概率:,e-k,為了保證成功的高概率，重復(fù)著色過程e

10、k次,重復(fù)ek次著色過程，k個中間點仍沒有被正確著色的概率：,(1-e-k)ek=e-10.38.,為了進一步降低錯誤的概率，可重復(fù)100ek次,錯誤的概率為：1/e100.,第24頁,彩色編碼(Color-Coding),s,t,假設(shè)G中從s到t含有k個中間結(jié)點的簡單路徑已被正確著色,怎樣基于著色找到該路徑？,Vs, t的點,C1,C2,C3,Ck,第25頁,彩色編碼(Color-Coding),Vs, t的點,C1,C2,C3,Ck,s,t,1,2,3,k,第i個點在哪個顏色筐中？(1 i k),枚舉,枚舉第1個點、第2個點、第k個點對應(yīng)的所有可能顏色,k!,第26頁,彩色編碼(Color

11、-Coding),2,1,3,k,s,t,第27頁,彩色編碼(Color-Coding),2,1,3,k,s,t,怎樣求解？,深度優(yōu)先(Breath First Search),廣度優(yōu)先(Depth First Search),第28頁,彩色編碼(Color-Coding),算法的時間復(fù)雜度：,1. 基于著色對路徑的求解：k!,2. 著色的次數(shù)：ek,3. 總的時間復(fù)雜度：ek k! |E|,如何改進？,第29頁,彩色編碼(Color-Coding),假設(shè)G中從s到t含有k個中間結(jié)點的簡單路徑已被正確著色,怎樣基于著色找到該路徑？,s,t,s,t,最優(yōu)子結(jié)構(gòu),s,第i個點,如何基于第i個點得到

12、第i+1個點,第30頁,彩色編碼(Color-Coding),動態(tài)規(guī)劃 對于圖中的任一點v，需要記錄從s出發(fā)到達v的彩色路徑的可能顏色集。,s,t,v1,v1點記錄的信息：,藍,紫, 綠, 藍, 黃, 綠,v2,v2點記錄的信息：,藍,紫, 綠, 黃, 紅, 藍, 黃, 紅,第31頁,彩色編碼(Color-Coding),假設(shè)用Qi=C1, C2, Ch表示v點記錄的從s出發(fā)到達v且長度為i的所有彩色路徑對應(yīng)的顏色集合。,h的取值范圍：1 h (k choose i).,如何基于得到從s出發(fā)經(jīng)過頂點v的長度為i+1的彩色路徑。,for v的每一個鄰居u do for j=1 to h if u

13、的顏色沒有被包含在Cj 中 then Cj=Cj u的顏色; if Qi+1中沒有一個集合用到的顏色與Cj相同 then Qi+1= Qi+1 Cj;,第32頁,彩色編碼(Color-Coding),算法的時間復(fù)雜度：,1. 基于著色對路徑的求解：|E|2k,2. 著色的次數(shù)：ek,3. 總的時間復(fù)雜度：ek 2k|E|=(2e)k|E|,第33頁,核心化(Kernelization),Q1 (x, k),Q2 (x, k),多項式時間,|x|=n, |x|=f(k),k=k,Q1 Yes,Q2 Yes,第34頁,核心化(Kernelization),給定圖G(V, E)和正整數(shù)k，問V是否存在一個大小不超過k的子集V，使得E中的任意一條邊至少有一個端點在V中。,點覆蓋問題(Vertex Cover), 如果圖G中存在0度點u，則刪除點u, 對于G中的一度點v，假設(shè)v的鄰居為u，則可直接把u點放入點覆蓋中，k=k-1。,如果G 中存在度數(shù)大于等于k+1的點v，刪除點v并且k