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

8.2作業(yè)分配問(wèn)題

8.3單源最短路徑問(wèn)題

8.40/1背包問(wèn)題

2l_結(jié)點(diǎn)（活結(jié)點(diǎn)）：所搜索到的結(jié)點(diǎn)不是葉結(jié)點(diǎn)，且滿(mǎn)足約束條件和目標(biāo)函數(shù)的界，其兒子結(jié)點(diǎn)還未全部搜索完畢e_結(jié)點(diǎn)（擴(kuò)展結(jié)點(diǎn)）：正在搜索其兒子結(jié)點(diǎn)的結(jié)點(diǎn)，它也是一個(gè)l_結(jié)點(diǎn)；d_結(jié)點(diǎn)（死結(jié)點(diǎn)）：不滿(mǎn)足約束條件、目標(biāo)函數(shù)、或其兒子結(jié)點(diǎn)已全部搜索完畢的結(jié)點(diǎn)、或者葉結(jié)點(diǎn)。以d_結(jié)點(diǎn)作為根的子樹(shù)，可以在搜索過(guò)程中刪除

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

是局部解是相應(yīng)的界1.對(duì)最小值問(wèn)題，稱(chēng)為下界，意思是向下搜索所可能取得的值最小不會(huì)小于這些下界若是所得到的局部解，滿(mǎn)足：

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

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

1）從根結(jié)點(diǎn)開(kāi)始，每遇到一個(gè)e_結(jié)點(diǎn)，就對(duì)它的所有兒子結(jié)點(diǎn)計(jì)算其下界，把它們登記在結(jié)點(diǎn)表中。

2）從表中選取下界最小的結(jié)點(diǎn)，重復(fù)上述過(guò)程。

3）當(dāng)搜索到一個(gè)葉子結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)的下界是結(jié)點(diǎn)表中最小的，那么，該結(jié)點(diǎn)就是問(wèn)題的最優(yōu)解。

4）否則，對(duì)下界最小的結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展

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

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

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

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

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

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

當(dāng)把第k號(hào)作業(yè)分配給編號(hào)為ik的操作員時(shí)，ikS-mk-1，

所需時(shí)間至少為：(8.2.1)

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

每個(gè)結(jié)點(diǎn)都包含已分配作業(yè)的操作員編號(hào)集合m、

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

S、

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

k、所需時(shí)間的下界t1）建立根結(jié)點(diǎn)X，令X.k=0，X.S={0,1,n-1}

，X.m=

把當(dāng)前問(wèn)題的可行解的最優(yōu)時(shí)間下界bound置為∞。2）對(duì)所有編號(hào)為

i的操作員，iX.S

，建立兒子結(jié)點(diǎn)

Yi，

把結(jié)點(diǎn)X的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)

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

，Yi.x=Yi.k，Yi.k=Yi.k+1，按式（8.2.1）計(jì)算

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

，轉(zhuǎn)

步驟6）。5）把結(jié)點(diǎn)

Yi插入優(yōu)先隊(duì)列。如果結(jié)點(diǎn)

Yi是葉結(jié)點(diǎn)，表明它

是問(wèn)題的一個(gè)可行解，用

Yi.t更新當(dāng)前可行解的最優(yōu)時(shí)

間下界bound。（6）取下隊(duì)列首元素作為子樹(shù)的根結(jié)點(diǎn)X，若

X.k=n，則該

結(jié)點(diǎn)是葉結(jié)點(diǎn)，表明它是問(wèn)題的最優(yōu)解，算法結(jié)束，向

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

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

0123

0123

7344

6488

5133

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

2.思想方法：把源頂點(diǎn)s作為根結(jié)點(diǎn)開(kāi)始進(jìn)行搜索。對(duì)源頂點(diǎn)s的所有鄰接頂點(diǎn)，都產(chǎn)生一個(gè)分支結(jié)點(diǎn)，估計(jì)從源點(diǎn)s經(jīng)該鄰接頂點(diǎn)到達(dá)目標(biāo)頂點(diǎn)的距離作為該分支結(jié)點(diǎn)的下界，選擇下界最小的分支結(jié)點(diǎn)，對(duì)這個(gè)分支結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)的所有鄰接頂點(diǎn)繼續(xù)進(jìn)行上述的搜索。

8.3單源最短路徑問(wèn)題

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

node所對(duì)應(yīng)的頂點(diǎn)

u的路徑長(zhǎng)度，頂點(diǎn)

u的鄰接頂點(diǎn)為v1,v2,vi

，而

cu,vi為頂點(diǎn)

u到其鄰接頂點(diǎn)

vi的距離。令

（8.3.1）

則結(jié)點(diǎn)

的下界

可表示為：

17一分支限界法解單源最短路徑問(wèn)題的思想方法4.結(jié)點(diǎn)內(nèi)部數(shù)據(jù)的描述：頂點(diǎn)編號(hào)為0,1,，n-1

搜索樹(shù)中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：structpath_node{int u; /*該結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)*/int path[n]; /*從源點(diǎn)開(kāi)始的路徑上頂點(diǎn)編號(hào)*/int k; /*當(dāng)前搜索深度下,路徑上的頂點(diǎn)個(gè)數(shù)*/int d；

/*從源點(diǎn)到本結(jié)點(diǎn)所對(duì)應(yīng)頂點(diǎn)的路徑長(zhǎng)度*/floatb; /*經(jīng)本結(jié)點(diǎn)到目標(biāo)頂點(diǎn)最短路徑長(zhǎng)度下界*/structpath_node*next；};typedefstructpath_nodePATH_NODE;

18一分支限界法解單源最短路徑問(wèn)題的思想方法5.算法步驟：假定源頂點(diǎn)為s，目標(biāo)頂點(diǎn)為

t，

1）初始化：建立根結(jié)點(diǎn)X，令根結(jié)點(diǎn)的X.u=s，X.k=1，X.path[0]=s，X.d=0，X.b=0，當(dāng)前可行解的最短路徑

下界

bound置為∞。

2）令頂點(diǎn)X.u所對(duì)應(yīng)的頂點(diǎn)為u，對(duì)

u的所有鄰接頂點(diǎn)vi

建立兒子結(jié)點(diǎn)

Yi，把結(jié)點(diǎn)

X的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)

Yi。

3）令Yi.u=vi

，Yi.path[yi.k]=vi

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

，對(duì)頂點(diǎn)

vi按式（8.3.1）和式（8.3.2）

計(jì)算

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

4）如果Yi.b<bound，轉(zhuǎn)步驟5），否則剪去結(jié)點(diǎn)

Yi，轉(zhuǎn)

步驟6）。

5）把結(jié)點(diǎn)

Yi插入優(yōu)先隊(duì)列。如果結(jié)點(diǎn)

Yi.u=t，表明它是問(wèn)

題的一個(gè)可行解，用

Yi.b更新當(dāng)前可行解的最短路徑長(zhǎng)

度下界

bound。

6）取下優(yōu)先隊(duì)列首元素作為子樹(shù)的根結(jié)點(diǎn)

X，若X.u=t，

表明它是問(wèn)題的最優(yōu)解，算法結(jié)束，數(shù)組

X.path存放

從源點(diǎn)

s到目標(biāo)頂點(diǎn)

t的最短路徑上的頂點(diǎn)編號(hào)，X.d

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

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

圖8.5表示用分支限界法求圖8.3所示有向圖的從源點(diǎn)

到目標(biāo)頂點(diǎn)

的最短路徑的搜索過(guò)程。

22下界的確定：假定d(node)是搜索樹(shù)中從根結(jié)點(diǎn)到結(jié)點(diǎn)

node所對(duì)應(yīng)的頂點(diǎn)

u的路徑長(zhǎng)度，頂點(diǎn)

u的鄰接頂點(diǎn)為v1,v2,vl

，而

cu,vi為頂點(diǎn)

u到其鄰接頂點(diǎn)

vi的距離。令

（8.3.1）

則結(jié)點(diǎn)

的下界

可表示為：

畫(huà)出搜索樹(shù)，在節(jié)點(diǎn)旁標(biāo)出相應(yīng)的的下屆，寫(xiě)出最后的最優(yōu)解。231.思想方法

2.求解過(guò)程8.40/1背包問(wèn)題

241.思想方法1）分支選擇及物體分類(lèi)

①

n個(gè)物體按價(jià)值重量比遞減順序排序后，重量分別為，價(jià)值分別為，物體序號(hào)集合為S={0,1,,n–1}，背包載重量為M②按物體價(jià)值重量比遞減順序（集合S中物體的順序號(hào)）把物體k裝入背包或不裝入背包進(jìn)行分支搜索③物體劃分為三類(lèi)：當(dāng)搜索深度為k時(shí)確定裝入背包的物體集合，確定不裝入背包的物體集合，尚待選擇的物體集合，

252）分支時(shí)的處理①

搜索深度為k+1時(shí)，被搜索物體序號(hào)就是集合S中的元素k②把物體裝入背包的分支結(jié)點(diǎn)的處理：③不把物體裝入背包的分支結(jié)點(diǎn)的處理：

263）上界的確定

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