演算法-处理NP完备理论PPT课件

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