第6章 分支限界法2

1、1第六章 分支限界法2第六章 分支限界法 本章主要知識點本章主要知識點v 6.1 分支限界法的基本思想 6.3 裝載問題v 6.5 01背包問題 6.7 旅行售貨員問題v 6.9 批處理作業(yè)調(diào)度36.1分支限界法的基本思想1、分支限界法的概念、分支限界法的概念 一種在問題的解空間樹上搜索問題解的算法什么是解空間？什么是解空間樹？解空間樹：樹上的每一個結(jié)點定義了一個“問題狀態(tài)”，從根到每一個結(jié)點的所有路徑定義了這個問題的“狀態(tài)空間”。從根到葉結(jié)點的每一條路徑定義了解空間中的一個多元組。解空間：將問題的解表示成一個多元組(x1, x2, , xn)的形式，滿足問題顯約束的所有多元組定義為關(guān)于輸入(

2、x1, x2, , xn)的解空間。 46.1分支限界法的基本思想2 2、比較分支限界法與回溯法、比較分支限界法與回溯法求解目標：找出解空間樹中滿足約束條件的所有解 搜索方式：以深度優(yōu)先的方式搜索解空間樹分支限界法求解目標：找出滿足約束條件的一個解，或是在滿足約 束條件的解中找出在某種意義下的最優(yōu)解搜索方式：以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜 索解空間樹。回溯法51）結(jié)點的構(gòu)造3、搜索策略、搜索策略2）結(jié)點的擴展3）下一個活結(jié)點的生成4）結(jié)點舍棄原則（剪支）6.1分支限界法的基本思想61 1）結(jié)點的構(gòu)造）結(jié)點的構(gòu)造一個所有兒子已經(jīng)產(chǎn)生的結(jié)點稱做死結(jié)點活結(jié)點：活結(jié)點：一個自身已生成但其兒子還沒有

3、全部生成的節(jié)點稱做活結(jié)點擴展結(jié)點：擴展結(jié)點： 一個正在產(chǎn)生兒子的結(jié)點稱為擴展結(jié)點死結(jié)點：死結(jié)點：構(gòu)造結(jié)點：與具體問題有關(guān)6.1分支限界法的基本思想回答結(jié)點：回答結(jié)點：滿足問題的全部約束的結(jié)點 72 2）活結(jié)點的擴展）活結(jié)點的擴展v每一個活結(jié)點只有一次機會成為擴展結(jié)點。v活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。v在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。6.1分支限界法的基本思想8(11)(11)(30)(30)(6)(6)(4)(4)(14)(14)(24)(24)(25)(25)(59)(59)(26)(26)(25)(25)6.

4、1分支限界法的基本思想2 2）活結(jié)點的擴展）活結(jié)點的擴展v每一個活結(jié)點只有一次機會成為擴展結(jié)點。v活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。v在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。93 3）下一個擴展結(jié)點的生成）下一個擴展結(jié)點的生成v（1）隊列式(FIFO)分支限界法 按照隊列先進先出（FIFO）原則選取下一個點為擴展節(jié)點。v（2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的活結(jié)點成為當前擴展節(jié)點。6.1分支限界法的基本思想106.1分支限界法的基本思想4 4）結(jié)點舍棄原則（剪支策略）結(jié)點舍棄原則（剪支策略）v

5、導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄；v在算法擴展結(jié)點的過程中，一旦發(fā)現(xiàn)一個結(jié)點的下界不小于（上界不大于）當前找到的最優(yōu)值，則算法剪去以該結(jié)點為根的子樹；v結(jié)點間的控制關(guān)系進行；(11)(11)(30)(30)(6)(6)(4)(4)(14)(14)(24)(24)(25)(25)(59)(59)(26)(26)(25)(25)116.3 裝載問題1. 問題描述 有一批共個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為Wi，且211ccwnii 裝載問題要求確定是否有一個合理的裝載方案可這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。 容易證明：如果一個給定裝載問

6、題有解，則采用下面的策略可得到最優(yōu)裝載方案。 (1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。 126.3 裝載問題2. 隊列式分支限界法 在算法的while循環(huán)中，首先檢測當前擴展結(jié)點的左兒子結(jié)點是否為可行結(jié)點。如果是則將其加入到活結(jié)點隊列中。然后將其右兒子結(jié)點加入到活結(jié)點隊列中(右兒子結(jié)點一定是可行結(jié)點)。2個兒子結(jié)點都產(chǎn)生后，當前擴展結(jié)點被舍棄。 活結(jié)點隊列中的隊首元素被取出作為當前擴展結(jié)點，由于隊列中每一層結(jié)點之后都有一個尾部標記-1，故在取隊首元素時，活結(jié)點隊列一定不空。當取出的元素是-1時，再判斷當前隊列是否為空。如果隊列非空，則將尾部標記-1加入活結(jié)點隊列，

7、算法開始處理下一層的活結(jié)點。13 2. 隊列式分支限界法int MaxLoading(int w,int c,int n) while (true) if (ew + wi bestw)bestw=wt; else Q.Add(wt);146.3 裝載問題3. 算法的改進 節(jié)點的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)bestw是當前最優(yōu)解；ew是當前擴展結(jié)點所相應(yīng)的重量；r是剩余集裝箱的重量。則當ew+rbestw時，可將其右子樹剪去，因為此時若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。 另外，為了確保右子樹成功剪枝，應(yīng)該在算法每一次進入左子樹的時候更新bestw的值。156

8、.3 裝載問題3. 算法的改進提前更新提前更新bestw bestw 右兒子剪枝右兒子剪枝 int MaxLoading(int w,int c,int n) while (true) int wt=ew+wi; if (wt bestw)bestw=wt; if( ibestw&i 0; j-) bestxj = E-leftChild; E = E-parent; 186.5 0-1背包問題1、算法的思想 首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進行排列。 在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝

9、滿剩余容量的價值和價值和。 算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。19 例題例題:0/1:0/1背包問題背包問題),18,12,10,10(),(,44321ppppn15),9,6,4,2(),(4321Mwwww 38 38 32 32 x x x x1 1=1 x=1 x1 1=0=0 38 32 38 32 32 22 32 22 x x2 2=1 x=1 x2 2=

10、0 =0 38 36 38 36 32 22 32 22 x x3 3=1 x=1 x3 3=0 =0 38 38 38 38 32 38 32 38 x x4 4=1 x=1 x4 4=0=0 38 20 38 20 38 20 38 20 1245738696.5 0-1背包問題206.5 0-1背包問題2、上界函數(shù)while (i = n & wi = cleft) / n表示物品總數(shù)，cleft為剩余空間 cleft -= wi; /wi表示i所占空間 b += pi; /pi表示i的價值 i+; if (i = n) b += pi / wi * cleft; / 裝填剩余容

11、量裝滿背包return b; /b為上界函數(shù)216.5 0-1背包問題 while (i != n + 1) / 非葉結(jié)點 double wt = cw + wi; if (wt bestp) bestp = cp + pi; addLiveNode(up,cp + pi,cw + wi,i + 1, enode, true); up = bound(i + 1); if (up = bestp) /檢查右兒子節(jié)點 addLiveNode(up,cp,cw,i + 1, enode, false); / 取下一個擴展節(jié)點（略）分支限界搜索分支限界搜索過程過程226.7 旅行售貨員問題1. 問題

12、描述 某售貨員要到若干城市去推銷商品，已知各城市之間的路程(或旅費)。他要選定一條從駐地出發(fā)，經(jīng)過每個城市一次，最后回到駐地的路線，使總的路程(或總旅費)最小。 路線是一個帶權(quán)圖。圖中各邊的費用（權(quán)）為正數(shù)。圖的一條周游路線是包括V中的每個頂點在內(nèi)的一條回路。周游路線的費用是這條路線上所有邊的費用之和。 旅行售貨員問題的解空間可以組織成一棵樹，從樹的根結(jié)點到任一葉結(jié)點的路徑定義了圖的一條周游路線。旅行售貨員問題要在圖G中找出費用最小的周游路線。 23BFLCGMHNDIOJEKQA 1 2 3 4 30 6 4 2 3 4 3 4 2 4 2 3 35 40 11 26 25 14 24 5

13、6 7 8 9 10 4 3 4 2 3 2 55 60 21 36 19 29 25 59 66 25 25 隊列式分支限界法 1P13423054201066.7 旅行售貨員問題24BFLCGMHNDIOJEKQA 1 2 3 4 30 25 6 4 8 3 2 3 4 2 4 2 3 35 40 11 26 25 14 24 4 7 5 6 4 3 4 2 3 2 55 60 21 36 19 29 25 59 66 25 25 優(yōu)先隊列式分支限界法 1P1342305420106； BE, D, C; ED, J, K, C; DH, J, K, I, C; HJ, K, I, C;

14、JK, I, C; KI,C; IC; C. 256.7 旅行售貨員問題2. 算法描述 算法開始時創(chuàng)建一個最小堆，用于表示活結(jié)點優(yōu)先隊列。堆中每個結(jié)點的子樹費用的下界lcost值是優(yōu)先隊列的優(yōu)先級。接著算法計算出圖中每個頂點的最小費用出邊并用minout記錄。如果所給的有向圖中某個頂點沒有出邊，則該圖不可能有回路，算法即告結(jié)束。如果每個頂點都有出邊，則根據(jù)計算出的minout作算法初始化。 算法的while循環(huán)體完成對排列樹內(nèi)部結(jié)點的擴展。對于當前擴展結(jié)點，算法分2種情況進行處理：266.7 旅行售貨員問題 1、首先考慮s=n-2的情形，此時當前擴展結(jié)點是排列樹中某個葉結(jié)點的父結(jié)點。如果該葉結(jié)

15、點相應(yīng)一條可行回路且費用小于當前最小費用，則將該葉結(jié)點插入到優(yōu)先隊列中，否則舍去該葉結(jié)點。 2、當sn-2時，算法依次產(chǎn)生當前擴展結(jié)點的所有兒子結(jié)點。由于當前擴展結(jié)點所相應(yīng)的路徑是x0:s，其可行兒子結(jié)點是從剩余頂點xs+1:n-1中選取的頂點xi，且(xs，xi)是所給有向圖G中的一條邊。對于當前擴展結(jié)點的每一個可行兒子結(jié)點，計算出其前綴(x0:s，xi)的費用cc和相應(yīng)的下界lcost。當lcost=r+1時依非減序排列，S1則取得極小值。同理如果選擇Pk使t2pk依非減序排列，則S2取得極小值。 ,max212SSFfMii這可以作為優(yōu)先隊列式分支限界法中的限界函數(shù)。 306.9 批處理

16、作業(yè)問題3. 算法描述 算法的while循環(huán)完成對排列樹內(nèi)部結(jié)點的有序擴展。在while循環(huán)體內(nèi)算法依次從活結(jié)點優(yōu)先隊列中取出具有最小bb值（完成時間和下界）的結(jié)點作為當前擴展結(jié)點，并加以擴展。 首先考慮E.s=n的情形，當前擴展結(jié)點E是排列樹中的葉結(jié)點。E.sf2是相應(yīng)于該葉結(jié)點的完成時間和。當E.sf2 bestc時更新當前最優(yōu)值bestc和相應(yīng)的當前最優(yōu)解bestx。 當E.sn時，算法依次產(chǎn)生當前擴展結(jié)點E的所有兒子結(jié)點。對于當前擴展結(jié)點的每一個兒子結(jié)點node，計算出其相應(yīng)的完成時間和的下界bb。當bb bestc時，將該兒子結(jié)點插入到活結(jié)點優(yōu)先隊列中。而當bb bestc時，可將結(jié)點node舍去。 316.9 批處理作業(yè)問題 while(E.s=n) if (E.s = n ) / 葉結(jié)點 if (E.sf2 bestc) bestc = E.sf2; for (int i = 0; i n; i+) bestxi = E.xi; 3. 算法描述 當當enodeenode.sf2.sf2bestcbestc時，時，更新當前最優(yōu)值更新當前最優(yōu)值bestebeste和和相應(yīng)的最優(yōu)解相應(yīng)的最優(yōu)解bestxbestx326.9 批處理作業(yè)問題3. 算法描述else / 產(chǎn)生當前擴