演算法-处理NP完备理论.ppt

《演算法-处理NP完备理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、處理NP-完備問題89/18/20211演算法＿第八章解NP-完備問題是否一定要找出正確解（判斷問題）或最佳解（最佳化問題）回溯法（判斷問題）分支設限法（最佳化問題）或者我們可以接受只找出近似解近似演算法9/18/20212演算法＿第八章回溯法與分支設限法回溯法與分支設限法是兩種用來有系統地檢視候選解的方法這種有系統地檢視候選解的方法，不管是在最壞的情況還是在平均的情況下，都能省下大量的執行時間這些方法通常使得我們得以排除大量的候選解；雖然如此，它們卻還是可以保證當演算法執行結束時，我們能找到所要的正確解或最佳解9/18/20213演算法＿第八章回溯法回溯法的作法是利

2、用觀察候選解的一小部分，如果從候選解的這一小部分已經足以判定它不可能形成我們最後要的解，就馬上放棄這個候選解舉個例子，如果SAT問題的給定布林公式中有一個子句是(x1x2)，則所有可能的真假值指派中只要是x1=x2=false的都可以直接予以淘汰而不至於影響到最終解的正確性9/18/20214演算法＿第八章回溯法9/18/20215演算法＿第八章回溯法回溯法通常會選擇深度優先，即w=0,x=0的頂點繼續分支因為它已經指派了兩個變數的真假值，可能很快就可以找到解深度優先通常比廣度優先還省記憶體過程中產生的可分支頂點數比較少9/18/20216演算法＿第八章回溯法利用這

3、個方式，回溯法檢視真假值指派的搜尋空間一旦確定一個頂點所代表的部分真假值指派已經不可能導致正確解，就不再為該頂點做後續的再分支運算會繼續做分支運算的頂點（灰色頂點）代表還有可能導致正確的真假值指派9/18/20217演算法＿第八章回溯法如果我們將w=0,x=0帶入F，則任何包含字元或的子句立刻為1，而字元w與x則因為是0，因而可以予以刪除這麼處理之後，在w=x=0的頂點只剩下9/18/20218演算法＿第八章回溯法類似地，在w=0,x=1的頂點將只剩下由於任何子句與空子句F=(0)=做and的結果都是false，因此以w=0,x=1為樹根的所有真假值指派至此就已經注

4、定不可能使得整個布林公式為真，也因此不用再分支下去9/18/20219演算法＿第八章回溯法回溯法顯示F不可能為真9/18/202110演算法＿第八章回溯法回溯法顯示xfalse,yfalse,ztrue會使得F為真9/18/202111演算法＿第八章回溯法從以上的討論可以知道，回溯法必須有一個檢視機制，它觀察子問題並且很快地判斷出這個子問題是以下三種可能的哪一種：失敗：這個子問題無解。成功：找到這個子問題的一個解。不確定。9/18/202112演算法＿第八章回溯法9/18/202113演算法＿第八章分支設限法分支設限法多了一個界限函數利用界限函數，我們可以正確地

5、判斷出一個子問題如果繼續做下去的話，它所導致的最低花費（或者最高獲利）會是多少如果一個子問題（活點）的界限函數指出這個子問題繼續做下去所導致的最低花費（最高獲利）將高於（低於）我們目前已經找出的一組解，那麼這個子問題就不用再考慮下去，可以直接予以丟棄（列為死點）9/18/202114演算法＿第八章分支設限法9/18/202115演算法＿第八章TSP問題abba9/18/202116演算法＿第八章TSP問題每一步我們都將部分路徑[a,S,b]延伸一個邊(b,x)，其中xVS共有VS種可能選擇，每一種選擇將導致形式為[a,S{x},x]的子問題9/18/202

6、117演算法＿第八章TSP問題lower_bound(Pi)lower_bound([a,S,b])？從a連結到VS裡某一個頂點的最小邊之花費，加上從b連結到VS裡某一個頂點的最小邊之花費，加上VS的最小花費生成樹的花費。9/18/202118演算法＿第八章TSP問題9/18/202119演算法＿第八章TSP問題9/18/202120演算法＿第八章TSP問題9/18/202121演算法＿第八章TSP問題9/18/202122演算法＿第八章0/1打包問題請注意，pi/wipi+1/wi+1,i=1,2,..,59/18/202123演算法＿第八章0/1打包問題利

7、用貪婪演算法求得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.59/18/202124演算法＿第八章0/1打包問題用演算法Knapsack2求出0/1打包問題的解之下限x1=x2=1,x3=x4=x5=x6=0，總價值是6+10=16換句話說，我們最後求出的0/1打包問題之最佳解Z必然大於等於169/18/202125演算法＿第八章0/1打包問題綜合上述的結果