算法課件六分支定界

11概述2分支限界法3應用舉例21.概述搜尋法在動態(tài)產(chǎn)生問題的解空間，并搜尋問題的可行解或最優(yōu)解。在生成的結點中，拋棄那些不滿足約束條件（或者說不行能導出最優(yōu)可行解）的結點。搜尋方式深度優(yōu)先搜尋廣度優(yōu)先搜尋31.概述方法1：深度優(yōu)先搜尋通常深度優(yōu)先搜尋法不全部保留結點，擴展完的結點從數(shù)據(jù)存儲結構棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲的結點數(shù)就是解空間樹的深度，因此它占用空間較少。所以，當搜尋樹的結點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜尋不失為一種有效的求解方法。41.概述方法2：廣度優(yōu)先搜尋廣度優(yōu)先搜尋算法，一般需存儲產(chǎn)生的全部結點，占用的存儲空間要比深度優(yōu)先搜尋大得多，因此，程序設計中，必需考慮溢出和節(jié)約內(nèi)存空間的問題。但廣度優(yōu)先搜尋法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜尋快。52.分支限界法接受廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結點，并運用剪枝函數(shù)的方法稱為分支限界法。所謂“分支”是接受廣度優(yōu)先的策略，依次生成擴展結點的全部分支（即：兒子結點）。所謂“限界”是在結點擴展過程中，計算結點的上界（或下界），邊搜尋邊減掉搜尋樹的某些分支，從而提高搜尋效率6分支限界算法思想對E-節(jié)點的擴充方式：引入活節(jié)點表【思想】每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達的全部新節(jié)點。在生成的節(jié)點中，拋棄那些不行能導出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結束。7不同的活結點表形成不同的分枝限界法：FIFO分支限界法（隊列式分支限界法）：活結點表是先進先出隊列LIFO分支限界法:活結點表是堆棧最小耗費或最大收益法分支限界法（優(yōu)先隊列式分支限界法）:活結點表是優(yōu)先權隊列，LC分支限界法將選取具有最高優(yōu)先級的活結點出隊列，成為新的擴展結點。幾種常見的分支限界法8FIFO分支定界法在解空間樹上的FIFO法，類似從根節(jié)點動身的BFS方法；與BFS的區(qū)分在于：在FIFO分支定界中，不行行的節(jié)點不會被搜尋！9示例1：0/1背包問題解1FIFO分支定界n=3,w=[20,15,15],p=[40,25,25],c=30E-節(jié)點活節(jié)點表ABCBCECEFGEFG解1：[1,0,0],收益40FG解2：[0,1,1],收益50GNULL2035×201535×30151510最大收益-分支定界思想運用一個最大堆：其中的E-節(jié)點依據(jù)每個活節(jié)點收益值的降序，或是依據(jù)活節(jié)點隨意子樹的葉節(jié)點所能獲得的收益估計值的降序從隊列中取出。FIFO分支-限界算法用隊存儲活結點，優(yōu)先隊列式分支限界法用堆存儲活結點，以保證比較優(yōu)良的結點先被擴展。且對于優(yōu)先隊列式分支限界算法，一旦擴展到葉結點就已經(jīng)找到最優(yōu)解，可以停止搜尋。接受廣度優(yōu)先搜尋策略的目的是:盡早發(fā)覺剪枝點。11

個元素的序列當且僅當滿足下述關系時，稱之為堆或堆120-1背包問題解2：最大收益法E-節(jié)點活節(jié)點表ABCBECEC解1：[1,0,0],收益40C解2：[0,1,1],收益50GNULLn=3,w=[20,15,15],p=[40,25,25],c=30FGFG不行行的解：D【1，1，1】,J【1，0，1】202015××3013示例2：旅行商問題FIFO分支定界E-節(jié)點活節(jié)點表BCDEFGCDEEFGHIJKF路徑12341，59G路徑12431，66H路徑13241，25IJK路徑1342，不綻開路徑14231，25路徑1432，不綻開××14示例2解法2：最小耗費法運用最小堆存儲活節(jié)點E-節(jié)點活節(jié)點表BEDCEDJKCDHJKICH路徑13241，25【定界函數(shù)】假如一個節(jié)點的定界值不比當前最優(yōu)旅行更小，則將被刪除而不被綻開！306424141126【注】活節(jié)點表接受堆結構3540552119290-1背包問題解3：最大收益法假設有4個物品，重量分別是（4,7,5,3），價值分別是（40,42,25,12），背包涵量是W=10。單位重量價值分別為：（10,6,5,4）17隊列式分支限界法程序框架設T為狀態(tài)空間樹的根結點；初始化隊列Q；將T入隊；循環(huán)，直到隊列Q空（無解）：結點e出隊；若e是回答結點，則輸出解或求解路徑；否則檢查e的全部子結點x：若x滿足約束條件，則將x入隊；記錄搜尋路徑；18優(yōu)先隊列式分支限界法程序框架設T為狀態(tài)空間樹的根結點；~C(x)為耗費估計函數(shù)；初始化優(yōu)先隊列Q；計算~C(T)，并將T入隊；循環(huán)，直到隊列Q空（無解）： 結點e出隊； 若e是回答結點，則輸出解或求解路徑，求解結束；否則檢查e的全部子結點x：若x滿足約束條件，則計算~C(x)，并將x入隊；記錄搜尋路徑；示例3：裝載問題1.問題描述有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。假如有，找出一種裝載方案。簡潔證明：假如一個給定裝載問題有解，則接受下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上其次艘輪船。問題描述：印刷電路板將布線區(qū)域劃分成n*m個方格陣列。精確的電路布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿直線或直角布線。為了避開線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格示例4：布線問題布線問題適合接受隊列式分支限界法來解決。從起始位置a起先將它作為第一個擴展結點。與該結點相鄰并且可達的方格被加入到活結點隊列中，并且將這些方格標記為1，表示它們到a的距離為1接著從活結點隊列中取出隊首作為下一個擴展結點，并將與當前擴展結點相鄰且未標記過的方格標記為2，并存入活節(jié)點隊列。這個過程一干脆著到算法搜尋到目標方格b或活結點隊列為空時為止（表示沒有通路）最起先，隊列中的活結點為標1的格子，隨后經(jīng)過一個輪次，活結點變?yōu)闃?的格子，以此類推，一旦b方格成為活節(jié)點便表示找到了最優(yōu)方案。為什么這條路徑確定就是最短的呢？這是由于我們這個搜尋過程的特點所確定的，假設存在一條由a至b的更短的路徑，b結點確定會更早地被加入到活結點隊列中并得到處理。問題：FIFO搜尋或LIFO搜尋也可以通過加入“限界”策略加速搜尋，與優(yōu)先隊列式分支限界法——LC-檢索的區(qū)分在哪兒呢？答案：由于FIFO搜尋或LIFO搜尋是盲目地擴展結點，當前最優(yōu)解距真正的最優(yōu)解