第08章 分支與限界

1第八章分支與限界8.1分支與限界法的基本思想

8.2作業(yè)分配問題

8.3單源最短路徑問題

8.40/1背包問題

2l_結點（活結點）：所搜索到的結點不是葉結點，且滿足約束條件和目標函數的界，其兒子結點還未全部搜索完畢e_結點（擴展結點）：正在搜索其兒子結點的結點，它也是一個l_結點；d_結點（死結點）：不滿足約束條件、目標函數、或其兒子結點已全部搜索完畢的結點、或者葉結點。以d_結點作為根的子樹，可以在搜索過程中刪除

一基本思想8.1分支與限界法的基本思想3一基本思想1.在e_結點估算沿著它的各兒子結點搜索時，目標函數可能取得的“界”，2.把兒子結點和目標函數可能取得的“界”，保存在優(yōu)先隊列或堆中，3.從隊列或堆中選取“界”最大或最小的結點向下搜索，直到葉子結點，4.若葉子結點的目標函數的值，是結點表中的最大值或最小值，則沿葉子結點到根結點的路徑所確定的解，就是問題的最優(yōu)解，否則轉3繼續(xù)搜索8.1分支與限界法的基本思想4二目標函數“界”的特性

是局部解是相應的界1.對最小值問題，稱為下界，意思是向下搜索所可能取得的值最小不會小于這些下界若是所得到的局部解，滿足：

2.對最大值問題，稱為上界，意思是向下搜索所可能取得的值最大不會大于這些上界若是所得到的部分解，滿足：5三兩種分支方法設解向量，的取值范圍為有窮集，1in1.每棵子樹都有個分支：最壞情況下，結點表的空間為若狀態(tài)空間樹是完全n叉樹，結點表的空間為2.每棵子樹只有兩個分支，取特定值的分支、及不取特定值的分支：狀態(tài)空間樹是完全二叉樹，最壞情況下結點表的空間為6一分支限界法解作業(yè)分配問題的思想方法1.問題描述：

n個操作員以n種不同時間完成n種不同作業(yè)。要求分配每位操作員完成一項工作，使完成n項工作的總時間最少操作員編號為0,1,…n-1，作業(yè)也編號為0,1,…n-1，矩陣c描述每位操作員完成每個作業(yè)時所需的時間，元素ci,j表示第i位操作員完成第j號作業(yè)所需的時間向量x描述分配給操作員的作業(yè)編號，分量xi表示分配給第i位操作員的作業(yè)編號。8.2作業(yè)分配問題7一分支限界法解作業(yè)分配問題的思想方法2.思想方法：

1）從根結點開始，每遇到一個e_結點，就對它的所有兒子結點計算其下界，把它們登記在結點表中。

2）從表中選取下界最小的結點，重復上述過程。

3）當搜索到一個葉子結點時，如果該結點的下界是結點表中最小的，那么，該結點就是問題的最優(yōu)解。

4）否則，對下界最小的結點繼續(xù)進行擴展

8一分支限界法解作業(yè)分配問題的思想方法3.下界的確定：

1）搜索深度為0時，把第0號作業(yè)分配給第i位操作員所需時間至少為第i位操作員完成第0號作業(yè)所需時間，加上其余n-1個作業(yè)分別由其余n-1位操作員單獨完成時所需最短時間之和，有：

9一分支限界法解作業(yè)分配問題的思想方法3.下界的確定：例：4個操作員完成4個作業(yè)所需的時間表如下：

把第0號作業(yè)分配給第0位操作員時，所需時間至少不會小于3+7+6+3=1910一分支限界法解作業(yè)分配問題的思想方法3.下界的確定：

2）搜索深度為k時，前面第0,1,,k-1號作業(yè)已分別分配

給編號為i0,i1,,ik-1的操作員。S={0,1,,n-1}表示所有操作員的編號集合；mk-1={i0,i1,,ik-1}表示作業(yè)已分配的操作員編號集合。

當把第k號作業(yè)分配給編號為ik的操作員時，ikS-mk-1，

所需時間至少為：(8.2.1)

則上式為把第k號作業(yè)分配給編號為ik的操作員時的下界11一分支限界法解作業(yè)分配問題的思想方法4.算法實現步驟：

每個結點都包含已分配作業(yè)的操作員編號集合m、

未分配作業(yè)的操作員編號集合

S、

操作員的分配方案向量x、搜索深度

k、所需時間的下界t1）建立根結點X，令X.k=0，X.S={0,1,n-1}

，X.m=

把當前問題的可行解的最優(yōu)時間下界bound置為∞。2）對所有編號為

i的操作員，iX.S

，建立兒子結點

Yi，

把結點X的數據復制到結點

Yi。3）令Yi.m=Yi.m{i}，Yi.S=Yi.S-{i}

，Yi.x=Yi.k，Yi.k=Yi.k+1，按式（8.2.1）計算

Yi.t。12一分支限界法解作業(yè)分配問題的思想方法4.算法實現步驟：4）如果Yi.t<buond，轉步驟5），否則剪去結點Yi

，轉

步驟6）。5）把結點

Yi插入優(yōu)先隊列。如果結點

Yi是葉結點，表明它

是問題的一個可行解，用

Yi.t更新當前可行解的最優(yōu)時

間下界bound。（6）取下隊列首元素作為子樹的根結點X，若

X.k=n，則該

結點是葉結點，表明它是問題的最優(yōu)解，算法結束，向

量X.x便是作業(yè)最優(yōu)分配分案；否則，轉步驟2）。13一分支限界法解作業(yè)分配問題的思想方法例：圖8.1所示的4個操作員的作業(yè)最優(yōu)分配方案的搜索樹。14一分支限界法解作業(yè)分配問題的思想方法下界的確定：

則上式為把第k號作業(yè)分配給編號為ik的操作員時的下界求下面作業(yè)分配問題：

0123

0123

7344

6488

5133

371615一分支限界法解單源最短路徑問題的思想方法1.問題描述：給定有向賦權圖G=(V,E)，圖中每一條邊都具有非負長度，求從源頂點s到目標頂點t的最短路徑問題

2.思想方法：把源頂點s作為根結點開始進行搜索。對源頂點s的所有鄰接頂點，都產生一個分支結點，估計從源點s經該鄰接頂點到達目標頂點的距離作為該分支結點的下界，選擇下界最小的分支結點，對這個分支結點所對應的頂點的所有鄰接頂點繼續(xù)進行上述的搜索。

8.3單源最短路徑問題

16一分支限界法解單源最短路徑問題的思想方法3.下界的確定：假定d(node)是搜索樹中從根結點到結點

node所對應的頂點

u的路徑長度，頂點

u的鄰接頂點為v1,v2,vi

，而

cu,vi為頂點

u到其鄰接頂點

vi的距離。令

（8.3.1）

則結點

的下界

可表示為：

17一分支限界法解單源最短路徑問題的思想方法4.結點內部數據的描述：頂點編號為0,1,，n-1

搜索樹中結點的數據結構：structpath_node{int u; /*該結點所對應的頂點*/int path[n]; /*從源點開始的路徑上頂點編號*/int k; /*當前搜索深度下,路徑上的頂點個數*/int d；

/*從源點到本結點所對應頂點的路徑長度*/floatb; /*經本結點到目標頂點最短路徑長度下界*/structpath_node*next；};typedefstructpath_nodePATH_NODE;

18一分支限界法解單源最短路徑問題的思想方法5.算法步驟：假定源頂點為s，目標頂點為

t，

1）初始化：建立根結點X，令根結點的X.u=s，X.k=1，X.path[0]=s，X.d=0，X.b=0，當前可行解的最短路徑

下界

bound置為∞。

2）令頂點X.u所對應的頂點為u，對

u的所有鄰接頂點vi

建立兒子結點

Yi，把結點

X的數據復制到結點

Yi。

3）令Yi.u=vi

，Yi.path[yi.k]=vi

，Yi.k=Yi.k+1，Yi.d=Yi.d+cu,vi

，對頂點

vi按式（8.3.1）和式（8.3.2）

計算

h和Yi.b。19一分支限界法解單源最短路徑問題的思想方法5.算法步驟：

4）如果Yi.b<bound，轉步驟5），否則剪去結點

Yi，轉

步驟6）。

5）把結點

Yi插入優(yōu)先隊列。如果結點

Yi.u=t，表明它是問

題的一個可行解，用

Yi.b更新當前可行解的最短路徑長

度下界

bound。

6）取下優(yōu)先隊列首元素作為子樹的根結點

X，若X.u=t，

表明它是問題的最優(yōu)解，算法結束，數組

X.path存放

從源點

s到目標頂點

t的最短路徑上的頂點編號，X.d

存放該路徑的長度；否則，轉步驟（2）。20一分支限界法解單源最短路徑問題的思想方法

21一分支限界法解單源最短路徑問題的思想方法例

圖8.5表示用分支限界法求圖8.3所示有向圖的從源點

到目標頂點

的最短路徑的搜索過程。

22下界的確定：假定d(node)是搜索樹中從根結點到結點

node所對應的頂點

u的路徑長度，頂點

u的鄰接頂點為v1,v2,vl

，而

cu,vi為頂點

u到其鄰接頂點

vi的距離。令

（8.3.1）

則結點

的下界

可表示為：

畫出搜索樹，在節(jié)點旁標出相應的的下屆，寫出最后的最優(yōu)解。231.思想方法

2.求解過程8.40/1背包問題

241.思想方法1）分支選擇及物體分類

①

n個物體按價值重量比遞減順序排序后，重量分別為，價值分別為，物體序號集合為S={0,1,,n–1}，背包載重量為M②按物體價值重量比遞減順序（集合S中物體的順序號）把物體k裝入背包或不裝入背包進行分支搜索③物體劃分為三類：當搜索深度為k時確定裝入背包的物體集合，確定不裝入背包的物體集合，尚待選擇的物體集合，

252）分支時的處理①

搜索深度為k+1時，被搜索物體序號就是集合S中的元素k②把物體裝入背包的分支結點的處理：③不把物體裝入背包的分支結點的處理：

263）上界的確定

①b(k)：搜索深度為k時，分支結點的背包中物體價值上界②若：令b(k)=0③若：則：272.求解過程1）把物體按價值重量比遞減順序排序2）建立根結點X，