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