分支限界算法的研究與實現(xiàn)

王春梅

摘 要：分支限界算法是一種在問題的解空間樹上搜索問題的解的方法，主要采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹，其核心思想就是“剪枝”。首先提出了分支限界算法的一般策略與實施步驟，然后以電路板布線問題為實例，設(shè)計并實現(xiàn)該問題的算法，經(jīng)過實驗數(shù)據(jù)驗證了其性能，進而反映了分支限界算法的高效性。

關(guān)鍵詞：分支限界； 解空間樹； 活結(jié)點； 擴展結(jié)點

中圖分類號：TN911-34文獻標(biāo)識碼：A

文章編號：1004-373X(2011)09-0121-03

Research and Implementation of Branch and Bound Algorithm

WANG Chun-mei

(Department of Computer, Xian Institute of Posts and Telecommunications, Xian 710121, China)

Abstract： The algorithm of branch and bound is a solution to search problems in the tree of solution space, whose main solution is breadth-first search (BFS) or the least cost first, and the central idea is "pruning". The general strategy and implementation steps of the branch and bound algorithm are proposed. Taking the wiring problem of circuit board as an example, whose algorithm is designed and implemented. The efficiency of the branch and bound algorithm is verified through experimental data, and its high performance is showed.

Keywords： branch and bound; tree of solution space; live node; extension node

0 引 言

分支限界算法原在運籌學(xué)中用于求解整數(shù)規(guī)劃(或者混合整數(shù)規(guī)劃)問題，是過程系統(tǒng)綜合的一類方法。將該方法原理用于過程系統(tǒng)綜合可大大減少需要計算的方案數(shù)目?，F(xiàn)如今，分支限界類算法應(yīng)用極為廣泛，如市場分析，方案選擇，信號傳輸，人工智能等方面。因而，分支限界類算法具有較高的研究價值。本文首先提出了分支限界算法的一般策略與實施步驟；其次，設(shè)計并實現(xiàn)了電路板布線問題。

1 分支限界算法

分支限界算法又稱為分支定界搜索法，分支是將一組解分為幾組子解，限界是建立這些子組解的目標(biāo)函數(shù)的邊界。它是一種在問題的解空間樹上搜索問題的解的方法，主要采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹，并且在分支定界算法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點在問題的解空間樹上搜索問題的解的方法。

1.1 分支限界算法策略

對問題的解空間樹進行搜索的策略為：

(1) 產(chǎn)生當(dāng)前擴展結(jié)點的所有子結(jié)點；

(2) 在產(chǎn)生的子結(jié)點中，拋棄那些不可能產(chǎn)生可行解(或最優(yōu)解)的結(jié)點(剪枝)；

(3) 將其余的子結(jié)點加入活結(jié)點表；

(4) 從活結(jié)點表中選擇下一個活結(jié)點作為新的擴展結(jié)點。

1.2 分支限界算法實施步驟

分支限界算法實施步驟如下，其中：

p為分支層數(shù)；C*為當(dāng)前最優(yōu)目標(biāo)函數(shù)值；

P*為相應(yīng)于C*的工件順序；

P1為當(dāng)前結(jié)點(現(xiàn)在需要進行分支的結(jié)點)所對應(yīng)的部分序列。

步驟1:初始化：設(shè)置p=0，P1=á；(空集)，C*=∞,設(shè)當(dāng)前結(jié)點總與P1相對應(yīng)。此時，當(dāng)前結(jié)點即根結(jié)點。

步驟2:計算從當(dāng)前結(jié)點分支得到的各個子結(jié)點的下界，并按下界值由小到大對各子結(jié)點排序。令p←p+1；

步驟3:如果當(dāng)前結(jié)點被探測盡，令p←p-1，轉(zhuǎn)步驟6，否則，設(shè)當(dāng)前層(第p層)各活動子結(jié)點中具有最小下界值的結(jié)點為Q，則在P1末尾加入Q對應(yīng)第p位置上的工件，此時的當(dāng)前結(jié)點轉(zhuǎn)到Q，轉(zhuǎn)步驟4。

步驟4:因為當(dāng)前結(jié)點是同層同父結(jié)點具有最小下界值的結(jié)點，如果當(dāng)前結(jié)點下界值大于或等于C*，則不必再搜索當(dāng)前結(jié)點及其同層同父的活動結(jié)點,這樣,當(dāng)前結(jié)點的上一層結(jié)點(父結(jié)點)被探測盡,p←p-1，去掉P1中的最后一個工件，轉(zhuǎn)步驟6，否則，轉(zhuǎn)步驟5。

步驟5:如果p=n，則得到一個較優(yōu)順序。令P*=P1，C*是當(dāng)前結(jié)點的下界值，p←p-1，去掉P1中最后一個工件，轉(zhuǎn)步驟6；否則轉(zhuǎn)步驟2。

步驟6:若p≠0，去掉P1中最后一個工件，轉(zhuǎn)步驟3；否則，算法停止。C*是最優(yōu)的目標(biāo)函數(shù)值，P*是最優(yōu)順序。

2 電路板布線問題

2.1 問題描述

布線問題就是在N×M的方格陣列，如何找到x到y(tǒng)的最短路徑，其中黑色的單元格代表不可以過，如圖1所示，在布線時只能沿直線或直角，不能走斜線。

圖1 布線簡圖

2.2 應(yīng)用分支限界算法的設(shè)計思路

布線問題的解空間是一個圖。解這個問題的隊列式分支限界法從起始位置x開始，將它作為第一個擴展結(jié)點。與該擴展結(jié)點相鄰并且可達的方格成為可行結(jié)點被加入到活結(jié)點隊列，且將這些方格標(biāo)記為1，即從起始方格x到這些方格的距離為1。接著，從活結(jié)點隊列中取出隊列首結(jié)點作為下一個擴展結(jié)點，并將與當(dāng)前擴展結(jié)點相鄰且未標(biāo)記過的方格標(biāo)記為2，并存入活結(jié)點隊列。這個過程一直繼續(xù)直到搜索到目標(biāo)方格y或活結(jié)點隊列為空為止。如圖2所示。

圖2 布線路徑圖

2.3 算法描述流程圖

算法流程如圖3所示。

圖中，條件1：起點與終點相同；條件2：鄰格是不是終點；條件3：隊列是否為空。

圖3 算法描述流程圖

2.4 算法實現(xiàn)

電路板上方格位置的數(shù)據(jù)類型描述如下：

typedef struct

{

int row; //方格的行

int col; //方格的列

}Position;

在電路板的任何一個方格處，布線可沿右、下、左、上4個方向進行。沿著這4個方向的移動分別記為移動0,1,2。使用offset［i］.row和offset［i］.col表示向前一步的位移(4個方向)，如表1所示。

表1 4個方向的位移

移動方向offset［i］.rowoffset［i］.col

0右01

1下10

2左0-1

3上-10

使用一個二維數(shù)組grid［ ］［ ］表示所給的方格陣列。初始狀態(tài)，grid［i］［j］=0表示方格允許布線，而grid［i］［j］=1表示方格被封鎖。為了方便處理最外圍的邊界，在初始化的時候設(shè)置一圈為1，相當(dāng)于設(shè)置一道圍墻，這一圈方格是附加格。

int i ;

for( i=0; i<= m+1; i++)

grid［0］［i］=grid［n+1］［i］=1; //頂部和底部

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

grid［i］［0］=grid［i］［m+1］=1; //左翼和右翼

算法開始測試起初方格與目標(biāo)方格是否相同。如果相同，則不用計算，直接返回距離0(做無解對待)，否則算法設(shè)置方格陣列的“圍墻”，初始化矩陣offset。

//初始化相對位移

Position offset［4］;

offset［0］.row=0; offset［0］.col=1;//右

offset［1］.row=1; offset［1］.col=0;//下

offset［2］.row=0; offset［2］.col=-1;//左

offset［3］.row=-1; offset［3］.col=0;//上

算法設(shè)置初始位置為2(因為0和1已經(jīng)在前面使用)，故最后算路徑的時候，應(yīng)該減去2。

算法從起始位置start開始，標(biāo)記所有距離為3的方格并存入活結(jié)點隊列中，然后依次是4，5，…的方格，直到finish或活結(jié)點隊列為空。

do { //標(biāo)記相鄰可達方格

for( i=0; i

{nbr.row=here.row + offset［i］.row;

nbr.col=here.col+offset［i］.col;

if(grid［nbr.row］［nbr.col］==0)

{ //該方格未被標(biāo)記

grid［nbr.row］［nbr.col］=grid［here.row］［here.col］+1;

if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布線

//Q.Add(nbr);

Q.col［Q.end］ = nbr.col;

Q.row［Q.end］ = nbr.row;

Q.end++;

}

}

//是否到達目標(biāo)位置finish？

if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布線

//活結(jié)點隊列是否非空？

if(Q.begin==Q.end)return false;//無解

else

{here.row=Q.row［Q.begin］;

here.col=Q.col［Q.begin］;

Q.begin++;//取下一個擴展結(jié)點

}

}while(true);

當(dāng)?shù)竭_finish時，可以回溯找到最初的start，然后形成最優(yōu)路徑。因為從start到finish是多對一的情況，所以在回溯的時候，一定是一對一的關(guān)系，也就是說，路徑是惟一的。

//構(gòu)造最短布線路徑

PathLen=grid［finish.row］［finish.col］-2;

path=new Position［PathLen］;

//從目標(biāo)位置finish開始向起始位置回溯

here=finish;

for( j = PathLen-1; j>=0; j--)

{path［j］=here;

//找前驅(qū)位置

for( i=0; i

{nbr.row=here.row+offset［i］.row;

nbr.col=here.col+offset［i］.col;

if(grid［nbr.row］［nbr.col］==j+2) break;

}

here=nbr;//向前移動

}

測試結(jié)果,如圖4所示。

2.5 算法性能分析

由于每個方格成為活結(jié)點進入活結(jié)點隊列最多一次，因此活結(jié)點隊列中最多處理m×n個活結(jié)點。擴

展每個結(jié)點需O(1)，因此算法共消耗O(m×n)，即O(n2)，構(gòu)造相應(yīng)的最短路徑需要O(L)，其中，L是最短布線路徑的長度。

圖4 測試結(jié)果

3 結(jié) 語

在大量離散型問題的研究中，分支限界類算法具有廣泛的應(yīng)用價值，如何提高算法的效率，從而更加有效的應(yīng)用實際生活，還需要對算法的策略和實施做進一步的研究和實踐。當(dāng)然，除了分支限界算法，還有如回溯算法，記憶算法，貪心算法，螞蟻算法等，把握各種算法的核心以及如何改進復(fù)雜度，進而在有限的資源下提高算法的效率，都是今后需要研究的方向。

參考文獻

［1］[沙特]AlSUWAIYE M H.Alogrithms Design Techniques and Analysis[M].北京：電子工業(yè)出版社，2004.

［2］[美]CORMEN Thomas H.Introduction to Algorithms[M].北京：機械工業(yè)出版社，2005.

［3］王曉東.計算機算法設(shè)計與分析[M].3版.北京：電子工業(yè)出版社，2007.

［4］潘愛民.VC++技術(shù)內(nèi)幕[M].4版.北京：清華大學(xué)出版社，2004.

［5］孫鑫.VC++深入詳解[M].北京：電子工業(yè)出版社，2006.

［6］[美]HORSTMANN Cay.C++核心思想[M].3版.北京：電子工業(yè)出版社，2004.

［7］[美]PRATA Stephen.C++Primer Plus[M].北京：人民郵電出版社，2002.

［8］Anon Visual C++ knowledge base[EB/OL]. [2000-02-13]. http://www.vckbase.com.

［9］Anon. Visual C++ developer center [EB/OL]. [2009-09-12]. http://msdn.microsoft.com/visualc/.

［10］嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版[M].北京：清華大學(xué)出版社，1997.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文