算法課件(六)分支定界

1、1分支限界法分支限界法LOGO2v1 1 概述概述v2 2 分支限界法分支限界法v3 3 應用舉例應用舉例LOGO31. 1. 概述概述v搜索法搜索法 在動態(tài)產(chǎn)生問題的解空間，并搜索問題的可行在動態(tài)產(chǎn)生問題的解空間，并搜索問題的可行解或最優(yōu)解。解或最優(yōu)解。 在生成的結(jié)點中，拋棄那些不滿足約束條件在生成的結(jié)點中，拋棄那些不滿足約束條件（或者說不可能導出最優(yōu)可行解）的結(jié)點。（或者說不可能導出最優(yōu)可行解）的結(jié)點。v搜索方式搜索方式 深度優(yōu)先搜索深度優(yōu)先搜索 廣度優(yōu)先搜索廣度優(yōu)先搜索LOGO41. 1. 概述概述v方法方法1 1：深度優(yōu)先搜索：深度優(yōu)先搜索 通常深度優(yōu)先搜索法不全部保留結(jié)點，擴展完通常

2、深度優(yōu)先搜索法不全部保留結(jié)點，擴展完的結(jié)點從數(shù)據(jù)存儲結(jié)構(gòu)棧中彈出刪去，這樣，的結(jié)點從數(shù)據(jù)存儲結(jié)構(gòu)棧中彈出刪去，這樣，一般在數(shù)據(jù)棧中存儲的結(jié)點數(shù)就是解空間樹的一般在數(shù)據(jù)棧中存儲的結(jié)點數(shù)就是解空間樹的深度，因此它占用空間較少。深度，因此它占用空間較少。 所以，當搜索樹的結(jié)點較多，用其它方法易產(chǎn)所以，當搜索樹的結(jié)點較多，用其它方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種有效的求解方法。的求解方法。LOGO51. 1. 概述概述v方法方法2 2：廣度優(yōu)先搜索：廣度優(yōu)先搜索 廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)廣度優(yōu)先搜索算法，一般需存儲產(chǎn)生的所有結(jié)點，占用的

3、存儲空間要比深度優(yōu)先搜索大得多，點，占用的存儲空間要比深度優(yōu)先搜索大得多，因此，程序設計中，必須考慮溢出和節(jié)省內(nèi)存因此，程序設計中，必須考慮溢出和節(jié)省內(nèi)存空間的問題?？臻g的問題。 但廣度優(yōu)先搜索法一般無回溯操作，即入棧和但廣度優(yōu)先搜索法一般無回溯操作，即入棧和出棧的操作，所以運行速度比深度優(yōu)先搜索快。出棧的操作，所以運行速度比深度優(yōu)先搜索快。LOGO62.2. 分支限界法分支限界法采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點，并使用剪采用廣度優(yōu)先產(chǎn)生狀態(tài)空間樹的結(jié)點，并使用剪枝函數(shù)的方法稱為枝函數(shù)的方法稱為分支限界法分支限界法。 所謂所謂“分支分支”是采用廣度優(yōu)先的策略，依次生是采用廣度優(yōu)先的策略，依次生

4、成擴展結(jié)點的所有分支（即：兒子結(jié)點）。成擴展結(jié)點的所有分支（即：兒子結(jié)點）。 所謂所謂“限界限界”是在結(jié)點擴展過程中，計算結(jié)點是在結(jié)點擴展過程中，計算結(jié)點的的上界上界（或（或下界下界），邊搜索邊減掉搜索樹的某），邊搜索邊減掉搜索樹的某些分支，從而提高搜索效率些分支，從而提高搜索效率LOGO7LOGO8不同的活結(jié)點表形成不同的分枝限界法：不同的活結(jié)點表形成不同的分枝限界法： FIFOFIFO分支限界法分支限界法（隊列式分支限界法）：活結(jié)（隊列式分支限界法）：活結(jié)點表是先進先出隊列點表是先進先出隊列 LIFOLIFO分支限界法分支限界法: :活結(jié)點表是堆棧活結(jié)點表是堆棧 最小耗費或最大收益法最小耗

5、費或最大收益法分支限界法分支限界法（優(yōu)先隊列（優(yōu)先隊列式分支限界法）式分支限界法）: :活結(jié)點表是優(yōu)先權(quán)隊列，活結(jié)點表是優(yōu)先權(quán)隊列，LCLC分支限界法將選取具有最高優(yōu)先級的活結(jié)點出分支限界法將選取具有最高優(yōu)先級的活結(jié)點出隊列，成為新的擴展結(jié)點。隊列，成為新的擴展結(jié)點。幾種常見的分支限界法幾種常見的分支限界法LOGO9LOGO102035201535301515LOGO11LOGO12 個元素的序列n,21nkkk 當且僅當滿足下述關(guān)系時，稱之為堆122iiiikkkk 或122iiiikkkk 2, 2 , 1ni堆LOGO13不可行的解：不可行的解：D D【1 1，1 1，1 1】, , J

6、 J【1 1，0 0，1 1】20201530LOGO14LOGO15【定界函數(shù)定界函數(shù)】如果一個如果一個節(jié)點的定界值不比當前節(jié)點的定界值不比當前最優(yōu)旅行更小，則將被最優(yōu)旅行更小，則將被刪除而不被展開！刪除而不被展開！306424141126【注注】活節(jié)點表采用堆結(jié)構(gòu)活節(jié)點表采用堆結(jié)構(gòu)35 4055211929LOGO16v假設有4個物品，重量分別是（4,7,5,3），價值分別是（40,42,25,12），背包容量是W=10。v單位重量價值分別為：（10,6,5,4）LOGO17LOGO18o隊列式分支限界法程序框架隊列式分支限界法程序框架o設T為狀態(tài)空間樹的根結(jié)點；初始化隊列Q；o將T入隊；

7、o循環(huán)，直到隊列Q空（無解）：o 結(jié)點e出隊；o 若e是回答結(jié)點，則o 輸出解或求解路徑；o 否則o 檢查e的所有子結(jié)點x：o 若x滿足約束條件，則 o 將x入隊；o 記錄搜索路徑；LOGO19v優(yōu)先隊列式分支限界法程序框架優(yōu)先隊列式分支限界法程序框架p設T為狀態(tài)空間樹的根結(jié)點；C(x)為耗費估計函數(shù)；初始化優(yōu)先隊列Q；p計算C(T)，并將T入隊；p循環(huán)，直到隊列Q空（無解）：p 結(jié)點e出隊；p 若e是回答結(jié)點，則p 輸出解或求解路徑，求解結(jié)束；p 否則p 檢查e的所有子結(jié)點x：p 若x滿足約束條件，則p 計算C(x)，并將x入隊；p 記錄搜索路徑；LOGO20LOGO21示例3 ：裝載問題1

8、. 問題描述有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且211ccwnii裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 容易證明：如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。 LOGO22 問題描述：印刷電路板將布線區(qū)域劃分成問題描述：印刷電路板將布線區(qū)域劃分成n n* *m m個方格陣列。精確個方格陣列。精確的電路布線問題要求確定連接方格的電路布線問題要求確定連接方格a a的中點到方格的中點到方格b b的中點的最

9、短布的中點的最短布線方案。在布線時，電路只能沿直線或直角布線。為了避免線路相線方案。在布線時，電路只能沿直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格方格LOGO23 布線問題適合采用隊列式分支限界法來解決。布線問題適合采用隊列式分支限界法來解決。 從起始位置從起始位置a a開始將它作為第一個擴展結(jié)點。與該結(jié)點相鄰并且可達開始將它作為第一個擴展結(jié)點。與該結(jié)點相鄰并且可達的方格被加入到活結(jié)點隊列中，并且將這些方格標記為的方格被加入到活結(jié)點隊列中，并且將這些方格標記為1 1，表示它們到，表示它們

10、到a a的的距離為距離為1 1 接著從活結(jié)點隊列中取出隊首作為下一個擴展結(jié)點，并將與當前擴展接著從活結(jié)點隊列中取出隊首作為下一個擴展結(jié)點，并將與當前擴展結(jié)點相鄰且未標記過的方格標記為結(jié)點相鄰且未標記過的方格標記為2 2，并存入活節(jié)點隊列。這個過程一直，并存入活節(jié)點隊列。這個過程一直繼續(xù)到算法搜索到目標方格繼續(xù)到算法搜索到目標方格b b或活結(jié)點隊列為空時為止（表示沒有通路）或活結(jié)點隊列為空時為止（表示沒有通路）LOGO24最開始，隊列中的活結(jié)點為標最開始，隊列中的活結(jié)點為標1 1的格的格子，隨后經(jīng)過一個輪次，活結(jié)點變?yōu)闃俗?，隨后經(jīng)過一個輪次，活結(jié)點變?yōu)闃? 2的格子，以此類推，一旦的格子，以此類

11、推，一旦b b方格成為活節(jié)方格成為活節(jié)點便表示找到了最優(yōu)方案。為什么這條路點便表示找到了最優(yōu)方案。為什么這條路徑一定就是最短的呢？這是由于我們這個徑一定就是最短的呢？這是由于我們這個搜索過程的特點所決定的，假設存在一條搜索過程的特點所決定的，假設存在一條由由a a至至b b的更短的路徑，的更短的路徑，b b結(jié)點一定會更早結(jié)點一定會更早地被加入到活結(jié)點隊列中并得到處理。地被加入到活結(jié)點隊列中并得到處理。 LOGO25問題：問題：FIFO搜索或搜索或LIFO搜索也可以通過加入搜索也可以通過加入“限界限界”策略加速搜索，與優(yōu)先隊列式分支限界法策略加速搜索，與優(yōu)先隊列式分支限界法LC-檢索檢索的區(qū)別在哪兒呢？