算法課件(六)分支定界

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

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

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

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

5、費(fèi)或最大收益法分支限界法分支限界法（優(yōu)先隊(duì)列（優(yōu)先隊(duì)列式分支限界法）式分支限界法）: :活結(jié)點(diǎn)表是優(yōu)先權(quán)隊(duì)列，活結(jié)點(diǎn)表是優(yōu)先權(quán)隊(duì)列，LCLC分支限界法將選取具有最高優(yōu)先級(jí)的活結(jié)點(diǎn)出分支限界法將選取具有最高優(yōu)先級(jí)的活結(jié)點(diǎn)出隊(duì)列，成為新的擴(kuò)展結(jié)點(diǎn)。隊(duì)列，成為新的擴(kuò)展結(jié)點(diǎn)。幾種常見(jiàn)的分支限界法幾種常見(jiàn)的分支限界法LOGO9LOGO102035201535301515LOGO11LOGO12 個(gè)元素的序列n,21nkkk 當(dāng)且僅當(dāng)滿足下述關(guān)系時(shí)，稱之為堆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ù)】如果一個(gè)如果一個(gè)節(jié)點(diǎn)的定界值不比當(dāng)前節(jié)點(diǎn)的定界值不比當(dāng)前最優(yōu)旅行更小，則將被最優(yōu)旅行更小，則將被刪除而不被展開(kāi)！刪除而不被展開(kāi)！306424141126【注注】活節(jié)點(diǎn)表采用堆結(jié)構(gòu)活節(jié)點(diǎn)表采用堆結(jié)構(gòu)35 4055211929LOGO16v假設(shè)有4個(gè)物品，重量分別是（4,7,5,3），價(jià)值分別是（40,42,25,12），背包容量是W=10。v單位重量?jī)r(jià)值分別為：（10,6,5,4）LOGO17LOGO18o隊(duì)列式分支限界法程序框架隊(duì)列式分支限界法程序框架o設(shè)T為狀態(tài)空間樹(shù)的根結(jié)點(diǎn)；初始化隊(duì)列Q；o將T入隊(duì)；

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

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

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

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

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