第6章_分支限界法

1、智能信息處理研究中心（RCIIP）1第第6 6章章 分支限界法分支限界法馬志強(qiáng)馬志強(qiáng)智能信息處理研究中心（RCIIP）2r分支限界法的算法框架m隊(duì)列式（FIFO）分支限界法m優(yōu)先隊(duì)列式分支限界法堆式分支限界法r應(yīng)用分支限界法解決單源最短路徑問(wèn)題裝載問(wèn)題；0-1背包問(wèn)題；旅行售貨員問(wèn)題批處理作業(yè)調(diào)度問(wèn)題智能信息處理研究中心（RCIIP）3分支限界法的背景分支限界法的背景理查德理查德.卡普卡普在在IBMIBM期間，深入研究了與實(shí)際應(yīng)用有密切聯(lián)系的一系列數(shù)學(xué)問(wèn)題，如期間，深入研究了與實(shí)際應(yīng)用有密切聯(lián)系的一系列數(shù)學(xué)問(wèn)題，如路徑問(wèn)題路徑問(wèn)題、背包問(wèn)題背包問(wèn)題、覆蓋問(wèn)題覆蓋問(wèn)題、匹配問(wèn)題匹配問(wèn)題、分區(qū)問(wèn)題

2、分區(qū)問(wèn)題、調(diào)度問(wèn)題調(diào)度問(wèn)題等，取得了許多出色的成等，取得了許多出色的成果。這些問(wèn)題有一個(gè)共同的特點(diǎn)，即如果用圖來(lái)表示問(wèn)題，那么當(dāng)圖中增加一個(gè)果。這些問(wèn)題有一個(gè)共同的特點(diǎn)，即如果用圖來(lái)表示問(wèn)題，那么當(dāng)圖中增加一個(gè)結(jié)點(diǎn)時(shí)，需要考察的可能的解的數(shù)目就急劇增加，形成所謂結(jié)點(diǎn)時(shí)，需要考察的可能的解的數(shù)目就急劇增加，形成所謂“組合爆炸組合爆炸” (combinatorial explosion)(combinatorial explosion)，使計(jì)算機(jī)的計(jì)算工作量大大增加，到一定程度就，使計(jì)算機(jī)的計(jì)算工作量大大增加，到一定程度就根本無(wú)法實(shí)現(xiàn)。根本無(wú)法實(shí)現(xiàn)。以路徑問(wèn)題中最著名的以路徑問(wèn)題中最著名的旅行商問(wèn)

3、題為例旅行商問(wèn)題為例，在卡普以前，最好的結(jié)果是，在卡普以前，最好的結(jié)果是RandRand公司的公司的丹齊格丹齊格(George Benard Dantzig)(George Benard Dantzig)、福格森、福格森(R(RFulkerson)Fulkerson)和約翰遜和約翰遜(S(SJohnson)Johnson)用手工和計(jì)算機(jī)相結(jié)合的辦法，求出了包含用手工和計(jì)算機(jī)相結(jié)合的辦法，求出了包含4949個(gè)城市個(gè)城市的旅行商的最佳路的旅行商的最佳路線。卡普和他的同事海爾特線。卡普和他的同事海爾特(M(MHeld)Held)經(jīng)過(guò)反復(fù)研究，終于提出了一種稱為經(jīng)過(guò)反復(fù)研究，終于提出了一種稱為“分支分

4、支限界法限界法”(branch(branchandandbound method)bound method)的新方法，用這種新方法實(shí)現(xiàn)的算法使的新方法，用這種新方法實(shí)現(xiàn)的算法使旅行推銷員能周游的城市數(shù)達(dá)到旅行推銷員能周游的城市數(shù)達(dá)到6565個(gè)個(gè)，從而打破了由，從而打破了由RandRand公司保持的記錄。公司保持的記錄。 1955 1955年年文學(xué)學(xué)士學(xué)位文學(xué)學(xué)士學(xué)位 19561956年年理科碩士學(xué)位理科碩士學(xué)位 19591959年年應(yīng)用數(shù)學(xué)博士學(xué)位應(yīng)用數(shù)學(xué)博士學(xué)位( (哈佛大學(xué)哈佛大學(xué)) ) Yorktown Heights Yorktown Heights的的IBMIBM沃森研究中心沃森研究

5、中心 1985年獲得年獲得ACM的圖靈獎(jiǎng)的圖靈獎(jiǎng)智能信息處理研究中心（RCIIP）4分支限界法基礎(chǔ)分支限界法基礎(chǔ)r8-Puzzle問(wèn)題m輸入: 具有8個(gè)編號(hào)小方塊的魔方 m輸出: 移動(dòng)序列, 經(jīng)過(guò)這些移動(dòng), 魔方達(dá)目標(biāo)狀態(tài)1284567321 8 45673智能信息處理研究中心（RCIIP）5分支限界法基礎(chǔ)分支限界法基礎(chǔ)r隊(duì)列式（FIFO）分支限界法m廣度優(yōu)先搜索解空間樹218 45673218 45673218 4567321845673218 45673218 4567321845673ABCDEFGA BCDEFG智能信息處理研究中心（RCIIP）6分支限界法基礎(chǔ)分支限界法基礎(chǔ)r優(yōu)先隊(duì)列

6、式分支限界法堆式分支限界m為解空間樹中的每個(gè)節(jié)點(diǎn)指定一個(gè)優(yōu)先級(jí)測(cè)度函數(shù)m每次擴(kuò)展樹中優(yōu)先級(jí)最高的節(jié)點(diǎn)m用最大（最?。┒褋?lái)保存待搜索節(jié)點(diǎn)r8-Puzzle問(wèn)題m測(cè)度函數(shù) f (v) =節(jié)點(diǎn)v中處于錯(cuò)誤位置的方塊數(shù)m每次擴(kuò)展 f (v) 值最小的節(jié)點(diǎn)智能信息處理研究中心（RCIIP）7218456732184567321 8 4567321 8 45673218 4567321845673218 45673218456732184567321 8 45673B(3)C(3)D(4)E(4)F(2)G(4)H(1)I(0)J(2)AAB CDEF GH最小堆最小堆智能信息處理研究中心（RCIIP）8

7、分支限界法基礎(chǔ)分支限界法基礎(chǔ)r思想m廣度優(yōu)先廣度優(yōu)先或者優(yōu)先級(jí)優(yōu)先優(yōu)先級(jí)優(yōu)先搜索解空間樹r實(shí)現(xiàn)m每個(gè)節(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展節(jié)點(diǎn)m一旦節(jié)點(diǎn)v成為擴(kuò)展節(jié)點(diǎn) 將 v 的所有孩子加入到隊(duì)列或者堆中 接著選取隊(duì)列頂隊(duì)列頂或堆頂堆頂節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn)r效率m耗時(shí)比回溯法少m需要空間比回溯法多智能信息處理研究中心（RCIIP）9 常見的兩種分支限界法常見的兩種分支限界法（1 1）隊(duì)列式分支限界法）隊(duì)列式分支限界法 按照隊(duì)列先進(jìn)先出（按照隊(duì)列先進(jìn)先出（FIFOFIFO）或者后進(jìn)先出（）或者后進(jìn)先出（LIFOLIFO）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。）原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。 （2 2）優(yōu)先隊(duì)列式分支

8、限界法）優(yōu)先隊(duì)列式分支限界法 隊(duì)列式分支限界法隊(duì)列式分支限界法對(duì)結(jié)點(diǎn)的選擇規(guī)則相當(dāng)死板，具對(duì)結(jié)點(diǎn)的選擇規(guī)則相當(dāng)死板，具有一定的有一定的 “ “盲目盲目”性。這種選擇規(guī)則不利于快速檢索到性。這種選擇規(guī)則不利于快速檢索到一個(gè)能夠到達(dá)答案的結(jié)點(diǎn)。一個(gè)能夠到達(dá)答案的結(jié)點(diǎn)。 對(duì)活結(jié)點(diǎn)使用一個(gè)對(duì)活結(jié)點(diǎn)使用一個(gè)“有智能有智能”的的排序函數(shù)排序函數(shù)C()C()來(lái)選取下來(lái)選取下一個(gè)結(jié)點(diǎn)，往往可以加快獲取答案的速度。一個(gè)結(jié)點(diǎn)，往往可以加快獲取答案的速度。 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。常用方法是成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。常用方法是LC(Lea

9、st Cost)LC(Least Cost)方法方法。分支限界法基礎(chǔ)分支限界法基礎(chǔ)智能信息處理研究中心（RCIIP）10r畫出下圖的解題過(guò)程（按優(yōu)先隊(duì)列方式）28316475初始狀態(tài)12384765目標(biāo)狀態(tài)智能信息處理研究中心（RCIIP）11源最短路徑問(wèn)題源最短路徑問(wèn)題r輸入m有向帶權(quán)圖G=(V, E)m圖中頂點(diǎn)sr輸出ms到圖中其它頂點(diǎn)的最短路徑智能信息處理研究中心（RCIIP）12源最短路徑問(wèn)題源最短路徑問(wèn)題r解空間樹智能信息處理研究中心（RCIIP）13源最短路徑問(wèn)題源最短路徑問(wèn)題r優(yōu)先隊(duì)列式分支限界法m優(yōu)先級(jí)測(cè)度：當(dāng)前路徑長(zhǎng)度 （最小堆）vprevdistva-INFb-INFc-I

10、NFd-INFas10ds100cs30ba60bc50dc90db60智能信息處理研究中心（RCIIP）14源最短路徑問(wèn)題源最短路徑問(wèn)題r剪枝策略m節(jié)點(diǎn)b:50控制b:60m將b:60 及其子樹剪去m當(dāng)前擴(kuò)展節(jié)點(diǎn)有兒子v: x 如果x=distv，不擴(kuò)展v 如果xdistv，擴(kuò)展v，將v的孩子加入堆中智能信息處理研究中心（RCIIP）150-1背包問(wèn)題背包問(wèn)題r輸入：m, , 和Cr輸出：m (x1, x2, , xn)，xi0, 1滿足r優(yōu)化目標(biāo)：niiixv1max智能信息處理研究中心（RCIIP）160-1背包問(wèn)題背包問(wèn)題r解空間樹w=16，15，15v=45，25，25背包容量30智

11、能信息處理研究中心（RCIIP）170-1背包問(wèn)題背包問(wèn)題rFIFO隊(duì)列式分支限界法FIFO隊(duì)列A, BD, E, FJ, K, L, M, N節(jié)點(diǎn)C對(duì)應(yīng)：x1=1, x2=1節(jié)點(diǎn)K對(duì)應(yīng)：x1=0, x2=1, x3=1智能信息處理研究中心（RCIIP）180-1背包問(wèn)題背包問(wèn)題r對(duì)于樹中的第i層節(jié)點(diǎn)Vm已經(jīng)完成了對(duì)物品1, i的取舍，剩余物品為i+1, ., nm設(shè)已選擇的物品價(jià)值為p，背包剩余容量為Cr限界函數(shù)bound(V) = p + qm其中q是針對(duì)輸入i+1, ., n和C的一般背包問(wèn)題的最優(yōu)解m可以按價(jià)重比順序依次向背包中裝入物品得到qr以以V為根的子樹中節(jié)點(diǎn)的價(jià)值不會(huì)超過(guò)為根的

12、子樹中節(jié)點(diǎn)的價(jià)值不會(huì)超過(guò)bound(V)物品按價(jià)重比排序?yàn)?, , n智能信息處理研究中心（RCIIP）190-1背包問(wèn)題背包問(wèn)題r優(yōu)先隊(duì)列式分支限界法m優(yōu)先級(jí)測(cè)度：bound(V) 最大堆m直到某個(gè)葉節(jié)點(diǎn)x成為擴(kuò)展節(jié)點(diǎn)結(jié)束 葉節(jié)點(diǎn)x的bound(x)等于拿走物品的總價(jià)值 堆中剩余節(jié)點(diǎn)及其子樹的價(jià)值不會(huì)超過(guò)bound(x)智能信息處理研究中心（RCIIP）200-1背包問(wèn)題背包問(wèn)題r優(yōu)先隊(duì)列式分支限界法m優(yōu)先級(jí)測(cè)度：bound(V) 最大堆w=16，15，15v=45，25，25背包容量30最優(yōu)解：K (0, 1, 1)總價(jià)值：50最大堆A, BD, BB, JE, J, FK, J, L,

13、F智能信息處理研究中心（RCIIP）210-1背包問(wèn)題背包問(wèn)題r隊(duì)列（堆）中的每個(gè)元素m存儲(chǔ)已經(jīng)獲得的部分解 D入隊(duì)列：存儲(chǔ)x1=1, x2=0 K入隊(duì)列：存儲(chǔ)x1=0, x2=1, x3=1m存儲(chǔ)已構(gòu)造的解空間樹 B入隊(duì)列：存儲(chǔ)B的父親為，B是其右孩子 E入隊(duì)列：存儲(chǔ)E的父親為B，E是其左孩子 K入隊(duì)列：存儲(chǔ)K的父親為E，K是其左孩子 K對(duì)應(yīng)的解：x3=1, x2=1, x1=0智能信息處理研究中心（RCIIP）220-1背包問(wèn)題背包問(wèn)題r分支限界法優(yōu)化m限界函數(shù)：bound(v)m當(dāng)前的最優(yōu)值：bestpm如果bound(v)bestp 剪去v及其子樹智能信息處理研究中心（RCIIP）23

14、裝載問(wèn)題裝載問(wèn)題r輸入mn個(gè)集裝箱，其中集裝箱i的重量為wim載重量分別為C1和C2的輪船r輸出m（是否有）合理的裝載方案將所有集裝箱裝上船r等價(jià)于211CCwniiniiixw1maxnixCxwiniii1,1 , 011s.t.特殊的0-1背包問(wèn)題：每種物品的價(jià)值等于重量智能信息處理研究中心（RCIIP）24裝載問(wèn)題裝載問(wèn)題r解空間樹w=16，15，15C1載重量30智能信息處理研究中心（RCIIP）25裝載問(wèn)題裝載問(wèn)題rFIFO隊(duì)列式分支限界法w=16，15，15C1載重量30智能信息處理研究中心（RCIIP）26裝載問(wèn)題裝載問(wèn)題r解空間樹的第i層節(jié)點(diǎn)vm已經(jīng)完成了對(duì)集裝箱1, i的取

15、舍，剩余集裝箱為i+1, ., nm已經(jīng)裝上第一艘船的集裝箱重量和為pm剩余集裝箱的重量和為rm限界函數(shù)bound(v)=p+rr以v為根的子樹中的解的總重量不會(huì)超過(guò)bound(v)智能信息處理研究中心（RCIIP）27裝載問(wèn)題裝載問(wèn)題r優(yōu)先隊(duì)列式分支限界法m優(yōu)先級(jí)測(cè)度：bound(v) 最大堆m直到某個(gè)葉節(jié)點(diǎn)x成為擴(kuò)展節(jié)點(diǎn)結(jié)束 葉節(jié)點(diǎn)x的bound(x)等于拿走物品的總重量 堆中剩余節(jié)點(diǎn)及其子樹的總重量不會(huì)超過(guò)bound(x)智能信息處理研究中心（RCIIP）28裝載問(wèn)題裝載問(wèn)題r優(yōu)先隊(duì)列式分支限界法w=16，15，15C1載重量30最大堆最大堆A, BD, BB, JE, J, FK, J

16、, F, L最優(yōu)解：K (0, 1, 1)總重量：30智能信息處理研究中心（RCIIP）29 旅行售貨員問(wèn)題旅行售貨員問(wèn)題r輸入m完全無(wú)向帶權(quán)圖G=(V, E) |V|=n, |E|=m 對(duì)于E中的某條邊e，其長(zhǎng)度為c(e)r輸出m最短的哈密爾頓回路哈密爾頓回路 經(jīng)過(guò)每個(gè)節(jié)點(diǎn)一次且僅一次的回路NP難問(wèn)題智能信息處理研究中心（RCIIP）30 旅行售貨員問(wèn)題旅行售貨員問(wèn)題 實(shí)例FIFO隊(duì)列式AB1C2F3L4G4M3DH2N4I4O2EJ2P3K3Q2341342306105420C,D,EC,D,EF,G,H,I,J,KF,G,H,I,J,KB BL,M,N,P,QL,M,N,P,Q59596

17、66625252626智能信息處理研究中心（RCIIP）31 旅行售貨員問(wèn)題旅行售貨員問(wèn)題r堆式分支限界法1m優(yōu)先級(jí)測(cè)度：當(dāng)前路徑長(zhǎng)度（最小堆）mbestp：當(dāng)前最優(yōu)值m剪去當(dāng)前代價(jià)大于等于bestp的節(jié)點(diǎn)及其子樹智能信息處理研究中心（RCIIP）32 旅行售貨員問(wèn)題旅行售貨員問(wèn)題 實(shí)例優(yōu)先隊(duì)列式(1)AB1C2DH2N4EJ2K3341342306105420E E,D,C,D,CB B2525J J,K,K,N N,I,C,I,CK K, ,N N,I,C,I,CN N,I,C,I,CI4D D,J,K,J,K,CH H,J,K,I,C,J,K,I,C智能信息處理研究中心（RCIIP）33

18、 旅行售貨員問(wèn)題旅行售貨員問(wèn)題r對(duì)于樹中的第 i 層節(jié)點(diǎn)Wm路徑上已選頂點(diǎn)為v1, v2, , vi 當(dāng)前路徑的長(zhǎng)度為 Pm剩余頂點(diǎn)為vi+1, , vn 連接 vj 的最短出邊的長(zhǎng)度為Minout(vj)rbound(W)=P+m以W為根的子樹中的解的代價(jià)不少于bound(W)nijjv )(Minout智能信息處理研究中心（RCIIP）34 旅行售貨員問(wèn)題旅行售貨員問(wèn)題r堆式分支限界法2m優(yōu)先級(jí)測(cè)度：bound(W) 最小堆m直到某個(gè)葉節(jié)點(diǎn)Y成為擴(kuò)展節(jié)點(diǎn) bound(Y)等于Y的路徑長(zhǎng)度 堆中其它節(jié)點(diǎn)的代價(jià)都大于bound(Y)r優(yōu)化mbestp：當(dāng)前最優(yōu)值m剪去當(dāng)前代價(jià)大于等于bestp

19、的節(jié)點(diǎn)及其子樹智能信息處理研究中心（RCIIP）35 旅行售貨員問(wèn)題旅行售貨員問(wèn)題 實(shí)例優(yōu)先隊(duì)列式(2)AB1C2DH2N4I4EJ2P3K3341342306105420C,D,EC,D,EC,D,J,KC,D,J,KB BC,KC,KC,J,K,H,IC,J,K,H,IC,J,K,IC,J,K,I智能信息處理研究中心（RCIIP）36批處理作業(yè)調(diào)度問(wèn)題（回溯法）r輸入mn個(gè)作業(yè)1, , nm兩臺(tái)機(jī)器（M1和M2） 作業(yè) i 在M1和M2上的處理時(shí)間分別為 ai 和 bi 每個(gè)作業(yè)必須現(xiàn)由M1處理，再由M2處理r輸出m作業(yè)調(diào)度方案使得總等待時(shí)間總等待時(shí)間最小 作業(yè) i在M1和M2上的完成時(shí)間

20、分別為 Ai 和 Bi 總等待時(shí)間為niiB1智能信息處理研究中心（RCIIP）37批處理作業(yè)調(diào)度問(wèn)題（回溯法）r可能的調(diào)度方案m123，132，213， 231，312，321r最佳方案是132（總等待時(shí)間：18）作業(yè)作業(yè)aibiJob 121Job 231Job 323M1M2Job 1Job 1B1=3Job 3Job 3B3=7Job 2Job 2B2=8A1=2A3=4A2=7智能信息處理研究中心（RCIIP）38批處理作業(yè)調(diào)度問(wèn)題（回溯法）r計(jì)算調(diào)度J1, J2, , Jn的等待時(shí)間m計(jì)算BJi 計(jì)算AJi=AJi-1 + aJi 比較AJi和BJi1 BJi較大者 + bJi智能

21、信息處理研究中心（RCIIP）39批處理作業(yè)調(diào)度問(wèn)題（回溯法）r解空間樹m排列樹BC1F2L3G3M2DH1N3I3O1EJ1P2K2Q123191820211919智能信息處理研究中心（RCIIP）40批處理作業(yè)調(diào)度問(wèn)題（回溯法）r回溯法（搜索排列樹）初始時(shí)：xn=（1,2,3,n）void Backtrack(int t) if (tn) 輸出x； else for(i=t; i=n; i+) Swap(xt, xi); if (Bound(t) /如果當(dāng)前的部分解可行 且 可能產(chǎn)生最優(yōu)解 Backtrack(t+1) ； Swap(xt, xi); 時(shí)間復(fù)雜性：O(n!)空間復(fù)雜性：O(

22、n)智能信息處理研究中心（RCIIP）41批處理作業(yè)調(diào)度問(wèn)題（回溯法）r剪枝m限界函數(shù) Bound(t)：bestTixBti1智能信息處理研究中心（RCIIP）42 批處理作業(yè)調(diào)度問(wèn)題批處理作業(yè)調(diào)度問(wèn)題r對(duì)于樹中第 i 層節(jié)點(diǎn)VmV已經(jīng)安排了作業(yè)J1, J2, , Ji 已安排的作業(yè)的等待時(shí)間為m計(jì)算BJi方法 計(jì)算AJi=AJi-1 + aJi 比較AJi和BJi1 BJi較大者 + bJiBJxx1i智能信息處理研究中心（RCIIP）43 批處理作業(yè)調(diào)度問(wèn)題批處理作業(yè)調(diào)度問(wèn)題r對(duì)于樹中第 i 層節(jié)點(diǎn)Vm設(shè)以V為根的子樹中某個(gè)葉節(jié)點(diǎn)W的調(diào)度為 J1, , Ji ，Ji+1 , , Jn 如果從Ji+1開始機(jī)器機(jī)器1沒(méi)有空閑沒(méi)有空閑，則 Ji+1 , , Jn的總等待時(shí)間總等待時(shí)間不少于nixxnixxiJbJaknJAinS111) 1()(111iiiiJbJaJAJB2212iiiiiJbJaJaJAJB.21nniiinJbJaJaJaJAJB