演算法处理NP完备理论.pptx

2024/4/2演算法 第八章1處理處理NP-完備問題完備問題82024/4/2演算法 第八章8-2解NP-完備問題 n是否一定要找出正確解（判斷問題）或最佳解（最佳化問題）n回溯法（判斷問題）n分支設限法（最佳化問題）n或者我們可以接受只找出近似解n近似演算法 2024/4/2演算法 第八章8-3回溯法與分支設限法 n回溯法與分支設限法是兩種用來有系統地檢視候選解的方法n這種有系統地檢視候選解的方法，不管是在最壞的情況還是在平均的情況下，都能省下大量的執行時間n這些方法通常使得我們得以排除大量的候選解；雖然如此，它們卻還是可以保證當演算法執行結束時，我們能找到所要的正確解或最佳解2024/4/2演算法 第八章8-4回溯法 n回溯法的作法是利用觀察候選解的一小部分，如果從候選解的這一小部分已經足以判定它不可能形成我們最後要的解，就馬上放棄這個候選解 n舉個例子，如果 SAT 問題的給定布林公式中有一個子句是(x1 x2)，則所有可能的真假值指派中只要是 x1=x2=false 的都可以直接予以淘汰而不至於影響到最終解的正確性 2024/4/2演算法 第八章8-5回溯法 2024/4/2演算法 第八章8-6回溯法 n回溯法通常會選擇深度優先，即 w=0,x=0 的頂點繼續分支n因為它已經指派了兩個變數的真假值，可能很快就可以找到解n深度優先通常比廣度優先還省記憶體n過程中產生的可分支頂點數比較少 2024/4/2演算法 第八章8-7回溯法 n利用這個方式，回溯法檢視真假值指派的搜尋空間n一旦確定一個頂點所代表的部分真假值指派已經不可能導致正確解，就不再為該頂點做後續的再分支運算n會繼續做分支運算的頂點（灰色頂點）代表還有可能導致正確的真假值指派 2024/4/2演算法 第八章8-8回溯法 n如果我們將 w=0,x=0 帶入 F，則任何包含字元或的子句立刻為 1，而字元 w 與 x 則因為是 0，因而可以予以刪除 n這麼處理之後，在 w=x=0 的頂點只剩下 2024/4/2演算法 第八章8-9回溯法 n類似地，在 w=0,x=1 的頂點將只剩下n由於任何子句與空子句 F=(0)=做 and 的結果都是 false，因此以 w=0,x=1 為樹根的所有真假值指派至此就已經注定不可能使得整個布林公式為真，也因此不用再分支下去 2024/4/2演算法 第八章8-10回溯法 n回溯法顯示 F 不可能為真 2024/4/2演算法 第八章8-11回溯法 n回溯法顯示 xfalse,yfalse,ztrue 會使得 F 為真 2024/4/2演算法 第八章8-12回溯法 n從以上的討論可以知道，回溯法必須有一個檢視機制，它觀察子問題並且很快地判斷出這個子問題是以下三種可能的哪一種：n失敗：這個子問題無解。n成功：找到這個子問題的一個解。n不確定。2024/4/2演算法 第八章8-13回溯法 2024/4/2演算法 第八章8-14分支設限法 n分支設限法多了一個界限函數界限函數n利用界限函數，我們可以正確地判斷出一個子問題如果繼續做下去的話，它所導致的最低花費（或者最高獲利）會是多少n如果一個子問題（活點）的界限函數指出這個子問題繼續做下去所導致的最低花費（最高獲利）將高於（低於）我們目前已經找出的一組解，那麼這個子問題就不用再考慮下去，可以直接予以丟棄（列為死點）2024/4/2演算法 第八章8-15分支設限法 2024/4/2演算法 第八章8-16TSP 問題 na bnb a 2024/4/2演算法 第八章8-17TSP 問題 n每一步我們都將部分路徑 a,S,b 延伸一個邊(b,x)，其中x VSn共有VS種可能選擇，每一種選擇將導致形式為 a,S x,x 的子問題 2024/4/2演算法 第八章8-18TSP 問題 nlower_bound(Pi)n lower_bound(a,S,b)？n從 a 連結到 VS 裡某一個頂點的最小邊之花費，加上n從 b 連結到 VS 裡某一個頂點的最小邊之花費，加上nVS 的最小花費生成樹的花費。2024/4/2演算法 第八章8-19TSP 問題 2024/4/2演算法 第八章8-20TSP 問題 2024/4/2演算法 第八章8-21TSP 問題 2024/4/2演算法 第八章8-22TSP 問題 2024/4/2演算法 第八章8-230/1 打包問題 n請注意，pi/wi pi+1/wi+1,i=1,2,.,5 2024/4/2演算法 第八章8-240/1 打包問題n利用貪婪演算法求得 x1=x2=1,x3=5/8,x4=x5=x6=0，它的總價值是6+10+45/8=18.5n這樣子所求得的總價值 18.5 會是我們同一組資料的 0/1 打包問題解之上限n換句話說，我們針對這組資料的 0/1 打包問題所求出的最佳解 Z 必然小於等於 18.5 2024/4/2演算法 第八章8-250/1 打包問題n用演算法 Knapsack2 求出 0/1 打包問題的解之下限nx1=x2=1,x3=x4=x5=x6=0，總價值是6+10=16 n換句話說，我們最後求出的 0/1 打包問題之最佳解Z必然大於等於16 2024/4/2演算法 第八章8-260/1 打包問題n綜合上述的結果，16 Z 18.5n由於 0/1 打包問題的xi值只能是 0 或 1，而且所有 pi 的值都是整數，因此16 Z 18n實際上，這組資料的最佳解是17 2024/4/2演算法 第八章8-270/1 打包問題2024/4/2演算法 第八章8-28近似演算法 nOPT(I)：最佳解的值 n似演算法 A，針對輸入 I 所產生的解是A(I)n定義演算法 A 的近似比為n如果是最大化的問題，只需要將上面的定義倒數過來即可 2024/4/2演算法 第八章8-29頂點涵蓋 n我們要的是 S 最小的頂點涵蓋 2024/4/2演算法 第八章8-30頂點涵蓋 n匹配指的是沒有共同頂點的邊之子集合 S（E）2024/4/2演算法 第八章8-31頂點涵蓋 n如果一個匹配已經使得不可能再有其他的邊加入，那麼我們就稱這個匹配為最大匹配n請注意，最大匹配不是唯一的 2024/4/2演算法 第八章8-32頂點涵蓋四個最大匹配 2024/4/2演算法 第八章8-33頂點涵蓋 n由於產生每一個最大匹配的時間不超過O(n3)n因此我們實際上可以產生多個（例如，n個）最大匹配，然後再從中選擇最符合我們需要的n我們希望最大匹配的邊數越少越好我們希望最大匹配的邊數越少越好 2024/4/2演算法 第八章8-34頂點涵蓋 n一個圖 G 的任何一組頂點涵蓋至少必須跟 G 裡的任何一組匹配裡的邊數一樣大n換句話說，令最大匹配裡的邊數為 M，則 OPT M n頂點涵蓋有 2M 個頂點n前面又證明 OPT Mn因此，A 2 2024/4/2演算法 第八章8-35頂點涵蓋 2024/4/2演算法 第八章8-36頂點涵蓋 n(a)與(d)的近似比是 A=4/3=1.33n(b)與(c)的近似比是 A=6/3=2 2024/4/2演算法 第八章8-37頂點涵蓋 n步驟步驟 1：找出一個最大匹配 M E；n步驟步驟 2：return S=M 裡所有邊的所有端點；2024/4/2演算法 第八章8-38TSP 問題 n假設點與點之間的距離滿足三角不等式n步驟步驟 1：找出 G 的最小花費生成樹MST；n步驟步驟 2：建立對應於 MST 的往返雙向邊MST；n步驟步驟 3：在往返雙向邊 MST上建立一個拜訪所有頂點的迴路；n步驟步驟 4：利用捷徑以產生最後的近似TSP迴路；2024/4/2演算法 第八章8-39TSP 問題 2024/4/2演算法 第八章8-40TSP 問題 1-3-2-3-7-8-9-8-7-6-10-6-5-4-5-6-7-3-1 2024/4/2演算法 第八章8-41TSP 問題 捷徑！2024/4/2演算法 第八章8-42TSP 問題 n沒去掉重複頂點的迴路長度是 2MSTn因此，近似TSP迴路之長度 2MSTn但是，最佳化的 TSP 迴路之長度 OPT MSTn因為去掉最佳化的 TSP 迴路之任何一邊將形成一棵生成樹，這棵生成樹的總花費當然大於等於最小花費生成樹的總花費n綜合以上，近似TSP迴路之長度 2MST 2OPTn換句話說，A=2 2024/4/2演算法 第八章8-43TSP 問題 n另一個 A=1.5 的近似演算法n步驟步驟 1：找出 G 的最小花費生成樹 MST；n步驟步驟 2：找出 MST 裡奇數級數頂點的最小加權匹配 M；n步驟步驟 3：在 MST+M 上找出尤拉迴路；n步驟步驟 4：利用捷徑以產生近似 TSP 迴路；2024/4/2演算法 第八章8-44TSP 問題 2024/4/2演算法 第八章8-45TSP 問題 2024/4/2演算法 第八章8-46TSP 問題