算法設(shè)計(jì)與分析 第6章

第6章分支限界法1學(xué)習(xí)要點(diǎn)理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）隊(duì)列式(FIFO)分支限界法（2）優(yōu)先隊(duì)列式分支限界法通過應(yīng)用范例學(xué)習(xí)分支限界法的設(shè)計(jì)策略。（1）單源最短路徑問題（2）裝載問題；（3）0-1背包問題；（4）旅行售貨員問題26.1 分支限界法的基本思想分支限界法與回溯法（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。

（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。

36.1 分支限界法的基本思想

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。

此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。

在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。46.1 分支限界法的基本思想常見的兩種分支限界法（1）隊(duì)列式(FIFO)分支限界法按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。

（2）優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。5n=3時(shí)的0-1背包問題，用完全二叉樹表示的解空間,實(shí)例如下：w=[16,15,15],p=[45,25,25],c=30。（1）隊(duì)列式(FIFO)分支限界法（2）優(yōu)先隊(duì)列式分支限界法極大堆來表示活結(jié)點(diǎn)表的優(yōu)先隊(duì)列。61243301045620四城市旅行售貨員問題。（1）隊(duì)列式(FIFO)分支限界法（2）優(yōu)先隊(duì)列式分支限界法極小堆來存儲(chǔ)活結(jié)點(diǎn)表76.50-1背包問題算法的思想

首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。

在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)是剩下的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。

算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。811×w=11無效解w=4,v=40ub=70

2w=4,v=40ub=76

3w=0,v=0ub=6045

6w=9,v=65ub=69

7w=4,v=40ub=64

8w=12無效解

9

w=9,v=65

ub=65×優(yōu)先隊(duì)列式分支限界法求解0/1背包問題

4個(gè)物品的重量分別為(4,7,5,3)，價(jià)值分別為(40,42,25,12)，背包容量W=10。

1

w=0,v=0

ub=10096.50-1背包問題上界函數(shù)Boundcleft=c-cw;b=cp;while(i<=n&&w[i]<=cleft)//n表示物品總數(shù)，cleft為剩余容量{cleft-=w[i];//w[i]表示i號(hào)的物品重量b+=p[i];//p[i]表示i號(hào)的物品價(jià)值i++;}if(i<=n)b+=p[i]/w[i]*cleft;//裝填剩余容量裝滿背包returnb;

//b為上界函數(shù)返回值106.50-1背包問題

while(i!=n+1){//非葉結(jié)點(diǎn)

//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)

Typewwt=cw+w[i];if(wt<=c){//左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn)

if(cp+p[i]>bestp)bestp=cp+p[i];//bestp為當(dāng)前最優(yōu)值

AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}//up為價(jià)值上界//將一個(gè)新的活結(jié)點(diǎn)插入到子集樹和最大堆中,true表示為左子樹up=Bound(i+1);//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)

if(up>=bestp)//右子樹可能含最優(yōu)解

AddLiveNode(up,cp,cw,false,i+1);

//取下一個(gè)擴(kuò)展節(jié)點(diǎn)（略）}分支限界搜索過程1122

6.7TSP問題

TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。

526 31 13

27 498

34 5C=∞

3 1 5 8

3158∞679 6∞42 74∞3 923∞(a)一個(gè)無向圖(b)無向圖的代價(jià)矩陣圖示無向圖及其代價(jià)矩陣1223

采用貪心法求得近似解為1→3→5→4→2→1，其路徑長(zhǎng)度為1+2+3+7+3=16，這可以作為TSP問題的上界。 把矩陣中每一行最小的元素相加，可以得到一個(gè)簡(jiǎn)單的下界，其路徑長(zhǎng)度為1+3+1+3+2=10，但是還有一個(gè)信息量更大的下界：考慮一個(gè)TSP問題的完整解，在每條路徑上，每個(gè)城市都有兩條鄰接邊，一條是進(jìn)入這個(gè)城市的，另一條是離開這個(gè)城市的，那么，如果把矩陣中每一行最小的兩個(gè)元素相加再除以2，如果圖中所有的代價(jià)都是整數(shù)，再對(duì)這個(gè)結(jié)果向上取整，就得到了一個(gè)合理的下界。

lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

于是，得到了目標(biāo)函數(shù)的界[14,16]。需要強(qiáng)調(diào)的是，這個(gè)解并不是一個(gè)合法的選擇（可能沒有構(gòu)成哈密頓回路），它僅僅給出了一個(gè)參考下界。13∑2c[r][r∑∑r行最小的兩個(gè)元素)/224部分解的目標(biāo)函數(shù)值的計(jì)算方法例如，以下無向圖中，如果部分解包含邊(1,4)，則該部分解的下界是lb=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16。ri∈Urj?Ulb=(k?1

i=1ii+1]+ri行不在路徑上的最小元素+j

526 31 13

27 498

34 5C=∞

3 1 5 8

3158∞679 6∞42 74∞3 923∞(a)一個(gè)無向圖(b)無向圖的代價(jià)矩陣圖示無向圖及其代價(jià)矩陣1425

21→2lb=14×

31→3lb=14

41→4lb=16

51→5lb=19

62→3lb=16

72→4lb=16

82→5lb=19×

93→2lb=16

103→4lb=15

113→5lb=14lb=1912×135→25→4lb=16lb=14 14 4→2lb=18

164→5

15×4→2lb=15 17 5→2×分支限界法求解TSP問題示例

1

start lb=141526具體的搜索過程如下（加黑表示該路徑上已經(jīng)確定的邊）：（1）在根結(jié)點(diǎn)1，根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的值為lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14；（2）在結(jié)點(diǎn)2，從城市1到城市2，路徑長(zhǎng)度為3，目標(biāo)函數(shù)的值為((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14，將結(jié)點(diǎn)2加入待處理結(jié)點(diǎn)活結(jié)點(diǎn)表中；在結(jié)點(diǎn)3，從城市1到城市3，路徑長(zhǎng)度為1，目標(biāo)函數(shù)的值為((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14，將結(jié)點(diǎn)3加入活結(jié)點(diǎn)表中；在結(jié)點(diǎn)4，從城市1到城市4，路徑長(zhǎng)度為5，目標(biāo)函數(shù)的值為((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，將結(jié)點(diǎn)4加入活結(jié)點(diǎn)表中；在結(jié)點(diǎn)5，從城市1到城市5，路徑長(zhǎng)度為8，目標(biāo)函數(shù)的值為((1+8)+(3+6)+(1+2)+(3+5)+(2+8))/2=19，超出目標(biāo)函數(shù)的界，將結(jié)點(diǎn)5丟棄；166.7旅行售貨員問題算法描述template<classType>classTraveling{friendvoidmain(void);public:TypeBBTSP(intv[]);private:

intn;//圖G的頂點(diǎn)數(shù)

Type**a,//鄰接矩陣

NoEdge,//無邊標(biāo)志

cc,//當(dāng)前費(fèi)用

bestc;//當(dāng)前最小費(fèi)用};176.7旅行售貨員問題算法描述template<classType>classMinHeapNode{friendTraveling<Type>;public:operatorType()const{returnlcost;}private:Typelcost,//子樹費(fèi)用的下界

cc,//當(dāng)前費(fèi)用

rcost;//x[s:n-1]中頂點(diǎn)最小出邊費(fèi)用和

ints,//根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑為x[0:s]*x;//需要進(jìn)一步搜索的結(jié)點(diǎn)為x[s+1:n-1]};186.7旅行售貨員問題算法描述template<classType>TypeTraveling<Type>::BBTSP(intv[]){//解旅行售貨員的優(yōu)先隊(duì)列分支定界法,定義最小堆容量為1000

MinHeap<MinHeapNode<Type>>H(1000);Type*MinOut=newType[n+1];//計(jì)算MinOut[i]=頂點(diǎn)i的最小出邊費(fèi)用

TypeMinSum=0;//最小出邊的費(fèi)用和

int

i,j;

for(i=1;i<=n;i++){TypeMin=NoEdge;

for(j=1;j<=n;j++)

if(a[i][j]!=NoEdge&&(a[i][j]<Min||Min==NoEdge))Min=a[i][j];

if(Min==NoEdge)returnNoEdge;//無回路

MinOut[i]=Min;

MinSum+=Min;}196.7旅行售貨員問題算法描述//初始化

MinHeapNode<Type>E;

E.x=newint[n];

for(i=0;i<n;i++)

E.x[i]=i+1;//需要進(jìn)一步搜索的結(jié)點(diǎn)為x[s+1:n-1]

E.s=0;//根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑為x[0:s]

E.cc=0;

E.rcost=MinSum;//x[s:n-1]中頂點(diǎn)最小出邊費(fèi)用和Typebestc=NoEdge;206.7旅行售貨員問題算法描述//搜索排列空間樹

while(E.s<n-1){//非葉節(jié)點(diǎn)

if(E.s==n-2){//當(dāng)前擴(kuò)展結(jié)點(diǎn)是葉結(jié)點(diǎn)的父結(jié)點(diǎn)

//再加2條邊構(gòu)成回路

//判斷回路是否優(yōu)于當(dāng)前最優(yōu)解

if(a[E.x[n-2]][E.x[n-1]]!=NoEdge&&a[E.x[n-1]][1]!=NoEdge&&(E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]<bestc||bestc==NoEdge)){//是一條比之前找到的費(fèi)用更小的回路

bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1];

E.cc=bestc;

E.lcost=bestc;

E.s++;

H.Insert(E);}//把滿足if條件的葉結(jié)點(diǎn)插入到優(yōu)先隊(duì)列elsedelete[]E.x;}//不滿足條件就舍棄該葉結(jié)點(diǎn)

21else{//非葉節(jié)點(diǎn)的父結(jié)點(diǎn)時(shí)，產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有兒子結(jié)點(diǎn)

for(i=E.s+1;i<n;i++){

if(a[E.x[E.s]][E.x[i]]!=NoEdge){//可行子結(jié)點(diǎn)

Typecc=E.cc+a[E.x[E.s]][E.x[i]];Typercost=E.rcost-MinOut[E.x[E.s]];Typeb=cc+rcost;//子節(jié)點(diǎn)的下界

if(b<bestc||bestc==NoEdge){//子樹可能含有最優(yōu)解,結(jié)點(diǎn)插入最小堆

MinHeapNode<Type>N;

N.x=newint[n];

for(j=0;j<n;j++)

N.x[j]=E.x[j];N.x[E.s+1]=E.x[i];//下一個(gè)擴(kuò)展結(jié)點(diǎn)

N.x[i]=E.x[E.s+1];//原先的擴(kuò)展結(jié)點(diǎn)被交換到后面