演算法处理NP完备理论

2026/5/26演算法＿第八章1

處理NP-完備問題82026/5/26演算法＿第八章8-2解NP-完備問題是否一定要找出正確解（判斷問題）或最佳解（最佳化問題）回溯法（判斷問題）分支設限法（最佳化問題）或者我們可以接受只找出近似解近似演算法2026/5/26演算法＿第八章8-3回溯法與分支設限法回溯法與分支設限法是兩種用來有系統地檢視候選解的方法這種有系統地檢視候選解的方法，不管是在最壞的情況還是在平均的情況下，都能省下大量的執行時間這些方法通常使得我們得以排除大量的候選解；雖然如此，它們卻還是可以保證當演算法執行結束時，我們能找到所要的正確解或最佳解2026/5/26演算法＿第八章8-4回溯法回溯法的作法是利用觀察候選解的一小部分，如果從候選解的這一小部分已經足以判定它不可能形成我們最後要的解，就馬上放棄這個候選解舉個例子，如果SAT問題的給定布林公式中有一個子句是(x1

x2)，則所有可能的真假值指派中只要是x1=x2=false的都可以直接予以淘汰而不至於影響到最終解的正確性2026/5/26演算法＿第八章8-5回溯法2026/5/26演算法＿第八章8-6回溯法回溯法通常會選擇深度優先，即w=0,x=0的頂點繼續分支因為它已經指派了兩個變數的真假值，可能很快就可以找到解深度優先通常比廣度優先還省記憶體過程中產生的可分支頂點數比較少2026/5/26演算法＿第八章8-7回溯法利用這個方式，回溯法檢視真假值指派的搜尋空間一旦確定一個頂點所代表的部分真假值指派已經不可能導致正確解，就不再為該頂點做後續的再分支運算會繼續做分支運算的頂點（灰色頂點）代表還有可能導致正確的真假值指派2026/5/26演算法＿第八章8-8回溯法如果我們將w=0,x=0帶入F，則任何包含字元或的子句立刻為1，而字元w與x則因為是0，因而可以予以刪除這麼處理之後，在w=x=0的頂點只剩下2026/5/26演算法＿第八章8-9回溯法類似地，在w=0,x=1的頂點將只剩下由於任何子句與空子句F=(0)=

做

and的結果都是false，因此以w=0,x=1為樹根的所有真假值指派至此就已經注定不可能使得整個布林公式為真，也因此不用再分支下去2026/5/26演算法＿第八章8-10回溯法回溯法顯示F不可能為真2026/5/26演算法＿第八章8-11回溯法回溯法顯示x

false,y

false,z

true會使得F為真2026/5/26演算法＿第八章8-12回溯法從以上的討論可以知道，回溯法必須有一個檢視機制，它觀察子問題並且很快地判斷出這個子問題是以下三種可能的哪一種：失敗：這個子問題無解。成功：找到這個子問題的一個解。不確定。2026/5/26演算法＿第八章8-13回溯法2026/5/26演算法＿第八章8-14分支設限法分支設限法多了一個界限函數利用界限函數，我們可以正確地判斷出一個子問題如果繼續做下去的話，它所導致的最低花費（或者最高獲利）會是多少如果一個子問題（活點）的界限函數指出這個子問題繼續做下去所導致的最低花費（最高獲利）將高於（低於）我們目前已經找出的一組解，那麼這個子問題就不用再考慮下去，可以直接予以丟棄（列為死點）2026/5/26演算法＿第八章8-15分支設限法2026/5/26演算法＿第八章8-16TSP問題abba

2026/5/26演算法＿第八章8-17TSP問題每一步我們都將部分路徑[a,S,b]延伸一個邊(b,x)，其中x

V

S共有

V

S

種可能選擇，每一種選擇將導致形式為[a,S

{x},x]的子問題2026/5/26演算法＿第八章8-18TSP問題lower_bound(Pi)lower_bound([a,S,b])？從a連結到V

S裡某一個頂點的最小邊之花費，加上從b連結到V

S裡某一個頂點的最小邊之花費，加上V

S的最小花費生成樹的花費。2026/5/26演算法＿第八章8-19TSP問題2026/5/26演算法＿第八章8-20TSP問題2026/5/26演算法＿第八章8-21TSP問題2026/5/26演算法＿第八章8-22TSP問題2026/5/26演算法＿第八章8-230/1打包問題請注意，pi/wi

pi+1/wi+1,i=1,2,..,52026/5/26演算法＿第八章8-240/1打包問題利用貪婪演算法求得x1=x2=1,x3=5/8,x4=x5=x6=0，它的總價值是6+10+4

5/8=18.5這樣子所求得的總價值18.5會是我們同一組資料的0/1打包問題解之上限換句話說，我們針對這組資料的0/1打包問題所求出的最佳解Z必然小於等於18.52026/5/26演算法＿第八章8-250/1打包問題用演算法Knapsack2求出0/1打包問題的解之下限x1=x2=1,x3=x4=x5=x6=0，總價值是6+10=16換句話說，我們最後求出的0/1打包問題之最佳解Z必然大於等於162026/5/26演算法＿第八章8-260/1打包問題綜合上述的結果，16

Z

18.5由於0/1打包問題的xi值只能是0或1，而且所有pi的值都是整數，因此16

Z

18實際上，這組資料的最佳解是172026/5/26演算法＿第八章8-270/1打包問題2026/5/26演算法＿第八章8-28近似演算法OPT(I)：最佳解的值似演算法A，針對輸入I所產生的解是A(I)定義演算法A的近似比為如果是最大化的問題，只需要將上面的定義倒數過來即可2026/5/26演算法＿第八章8-29頂點涵蓋我們要的是

S

最小的頂點涵蓋2026/5/26演算法＿第八章8-30頂點涵蓋匹配指的是沒有共同頂點的邊之子集合S（

E）2026/5/26演算法＿第八章8-31頂點涵蓋如果一個匹配已經使得不可能再有其他的邊加入，那麼我們就稱這個匹配為最大匹配請注意，最大匹配不是唯一的2026/5/26演算法＿第八章8-32頂點涵蓋－四個最大匹配2026/5/26演算法＿第八章8-33頂點涵蓋由於產生每一個最大匹配的時間不超過O(n3)因此我們實際上可以產生多個（例如，n個）最大匹配，然後再從中選擇最符合我們需要的我們希望最大匹配的邊數越少越好

2026/5/26演算法＿第八章8-34頂點涵蓋一個圖G的任何一組頂點涵蓋至少必須跟G裡的任何一組匹配裡的邊數一樣大換句話說，令最大匹配裡的邊數為

M

，則OPT

M

頂點涵蓋有2

M

個頂點前面又證明OPT

M

因此，

A

22026/5/26演算法＿第八章8-35頂點涵蓋2026/5/26演算法＿第八章8-36頂點涵蓋(a)與(d)的近似比是

A

=4/3=1.33(b)與(c)的近似比是

A

=6/3=22026/5/26演算法＿第八章8-37頂點涵蓋步驟

1：找出一個最大匹配M

E；步驟

2：returnS={M裡所有邊的所有端點}；2026/5/26演算法＿第八章8-38TSP問題假設點與點之間的距離滿足三角不等式步驟

1：找出G的最小花費生成樹MST；步驟

2：建立對應於MST的往返雙向邊MST’；步驟

3：在往返雙向邊MST’上建立一個拜訪所有頂點的迴路；步驟

4：利用捷徑以產生最後的近似TSP迴路；2026/5/26演算法＿第八章8-39TSP問題2026/5/26演算法＿第八章8-40TSP問題1-3-2-3-7-8-9-8-7-6-10-6-5-4-5-6-7-3-12026/5/26演算法＿第八章8-41TSP問題捷徑！2026/5/26演算法＿第八章8-42TSP問題沒去掉重複頂點的迴路長度是

2

MST

因此，近似TSP迴路之長度

2

MST

但是，最佳化的TSP迴路之長度OPT

MST

因為去掉最佳化的TSP迴路之任何一邊將形成一棵生成樹，這棵生成樹的總花費當然大於等於最小花費生成樹的總花費綜合以上，近似TSP迴路之長度

2

MST

2

OPT換句話說，

A=22026/5/26演算法＿第八章8-43TSP問題另一個A