演算法處理NP完備理論

2023/9/2演算法＿第八章1

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

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

做

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

false,y

false,z

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

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

V

S共有

V

S

種可能選擇，每一種選擇將導(dǎo)致形式為[a,S

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

S裡某一個(gè)頂點(diǎn)的最小邊之花費(fèi)，加上從b連結(jié)到V

S裡某一個(gè)頂點(diǎn)的最小邊之花費(fèi)，加上V

S的最小花費(fèi)生成樹的花費(fèi)。2023/9/2演算法＿第八章8-19TSP問題2023/9/2演算法＿第八章8-20TSP問題2023/9/2演算法＿第八章8-21TSP問題2023/9/2演算法＿第八章8-22TSP問題2023/9/2演算法＿第八章8-230/1打包問題請(qǐng)注意，pi/wi

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

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

Z

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

Z

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

S

最小的頂點(diǎn)涵蓋2023/9/2演算法＿第八章8-30頂點(diǎn)涵蓋匹配指的是沒有共同頂點(diǎn)的邊之子集合S（

E）2023/9/2演算法＿第八章8-31頂點(diǎn)涵蓋如果一個(gè)匹配已經(jīng)使得不可能再有其他的邊加入，那麼我們就稱這個(gè)匹配為最大匹配請(qǐng)注意，最大匹配不是唯一的2023/9/2演算法＿第八章8-32頂點(diǎn)涵蓋－四個(gè)最大匹配2023/9/2演算法＿第八章8-33頂點(diǎn)涵蓋由於產(chǎn)生每一個(gè)最大匹配的時(shí)間不超過O(n3)因此我們實(shí)際上可以產(chǎn)生多個(gè)（例如，n個(gè)）最大匹配，然後再?gòu)闹羞x擇最符合我們需要的我們希望最大匹配的邊數(shù)越少越好

2023/9/2演算法＿第八章8-34頂點(diǎn)涵蓋一個(gè)圖G的任何一組頂點(diǎn)涵蓋至少必須跟G裡的任何一組匹配裡的邊數(shù)一樣大換句話說，令最大匹配裡的邊數(shù)為

M

，則OPT

M

頂點(diǎn)涵蓋有2

M

個(gè)頂點(diǎn)前面又證明OPT

M

因此，

A

22023/9/2演算法＿第八章8-35頂點(diǎn)涵蓋2023/9/2演算法＿第八章8-36頂點(diǎn)涵蓋(a)與(d)的近似比是

A

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

A

=6/3=22023/9/2演算法＿第八章8-37頂點(diǎn)涵蓋步驟

1：找出一個(gè)最大匹配M

E；步驟

2：returnS={M裡所有邊的所有端點(diǎn)}；2023/9/2演算法＿第八章8-38TSP問題假設(shè)點(diǎn)與點(diǎn)之間的距離滿足三角不等式步驟

1：找出G的最小花費(fèi)生成樹MST；步驟

2：建立對(duì)應(yīng)於MST的往返雙向邊MST’；步驟

3：在往返雙向邊MST’上建立一個(gè)拜訪所有頂點(diǎn)的迴路；步驟

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

2

MST

因此，近似TSP迴路之長(zhǎng)度

2

MST

但是，最佳化的TSP迴路之長(zhǎng)度OPT

MST

因?yàn)槿サ糇罴鸦腡SP迴路之任何一邊將形成一棵生成樹，這棵生成樹的總花費(fèi)當(dāng)然大於等於最小花費(fèi)生成樹的總花費(fèi)綜合以上，近似TSP迴路之長(zhǎng)度

2

MST

2

OPT換句話說，

A=22023/9/2演算法＿第八章8-43TSP問題另一個(gè)A=1.5的近似演算法步驟