算法設計與分析 第6章

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

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

36.1 分支限界法的基本思想

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

此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續(xù)到找到所需的解或活結點表為空時為止。

在分支限界法中，每一個活結點只有一次機會成為擴展結點?；罱Y點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優(yōu)解的兒子結點被舍棄，其余兒子結點被加入活結點表中。46.1 分支限界法的基本思想常見的兩種分支限界法（1）隊列式(FIFO)分支限界法按照隊列先進先出（FIFO）原則選取下一個節(jié)點為擴展節(jié)點。

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

首先，要對輸入數據進行預處理，將各物品依其單位重量價值從大到小進行排列。

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

算法首先檢查當前擴展結點的左兒子結點的可行性。如果該左兒子結點是可行結點，則將它加入到子集樹和活結點優(yōu)先隊列中。當前擴展結點的右兒子結點一定是可行結點，僅當右兒子結點滿足上界約束時才將它加入子集樹和活結點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(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)先隊列式分支限界法求解0/1背包問題

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

1

w=0,v=0

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

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

while(i!=n+1){//非葉結點

//檢查當前擴展結點的左兒子結點

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

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

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

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

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

//取下一個擴展節(jié)點（略）}分支限界搜索過程1122

6.7TSP問題

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

526 31 13

27 498

34 5C=∞

3 1 5 8

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

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

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

于是，得到了目標函數的界[14,16]。需要強調的是，這個解并不是一個合法的選擇（可能沒有構成哈密頓回路），它僅僅給出了一個參考下界。13∑2c[r][r∑∑r行最小的兩個元素)/224部分解的目標函數值的計算方法例如，以下無向圖中，如果部分解包含邊(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)一個無向圖(b)無向圖的代價矩陣圖示無向圖及其代價矩陣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具體的搜索過程如下（加黑表示該路徑上已經確定的邊）：（1）在根結點1，根據限界函數計算目標函數的值為lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14；（2）在結點2，從城市1到城市2，路徑長度為3，目標函數的值為((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14，將結點2加入待處理結點活結點表中；在結點3，從城市1到城市3，路徑長度為1，目標函數的值為((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14，將結點3加入活結點表中；在結點4，從城市1到城市4，路徑長度為5，目標函數的值為((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16，將結點4加入活結點表中；在結點5，從城市1到城市5，路徑長度為8，目標函數的值為((1+8)+(3+6)+(1+2)+(3+5)+(2+8))/2=19，超出目標函數的界，將結點5丟棄；166.7旅行售貨員問題算法描述template<classType>classTraveling{friendvoidmain(void);public:TypeBBTSP(intv[]);private:

intn;//圖G的頂點數

Type**a,//鄰接矩陣

NoEdge,//無邊標志

cc,//當前費用

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

cc,//當前費用

rcost;//x[s:n-1]中頂點最小出邊費用和

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

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

TypeMinSum=0;//最小出邊的費用和

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;//需要進一步搜索的結點為x[s+1:n-1]

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

E.cc=0;

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

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

if(E.s==n-2){//當前擴展結點是葉結點的父結點

//再加2條邊構成回路

//判斷回路是否優(yōu)于當前最優(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)){//是一條比之前找到的費用更小的回路

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條件的葉結點插入到優(yōu)先隊列elsedelete[]E.x;}//不滿足條件就舍棄該葉結點

21else{//非葉節(jié)點的父結點時，產生當前擴展結點的所有兒子結點

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

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

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

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

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];//下一個擴展結點

N.x[i]=E.x[E.s+1];//原先的擴展結點被交換到后面