王春梅

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

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

中圖分類號(hào)：TN911-34文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引 言

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

1 分支限界算法

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

1.1 分支限界算法策略

對(duì)問題的解空間樹進(jìn)行搜索的策略為：

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

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

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

(4) 從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)。

1.2 分支限界算法實(shí)施步驟

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

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

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

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

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

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

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

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

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

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

2 電路板布線問題

2.1 問題描述

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

圖1 布線簡(jiǎn)圖

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

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

圖2 布線路徑圖

2.3 算法描述流程圖

算法流程如圖3所示。

圖中，條件1：起點(diǎn)與終點(diǎn)相同；條件2：鄰格是不是終點(diǎn)；條件3：隊(duì)列是否為空。

圖3 算法描述流程圖

2.4 算法實(shí)現(xiàn)

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

typedef struct

{

int row; //方格的行

int col; //方格的列

}Position;

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

表1 4個(gè)方向的位移

移動(dòng)方向offset［i］.rowoffset［i］.col

0右01

1下10

2左0-1

3上-10

使用一個(gè)二維數(shù)組grid［ ］［ ］表示所給的方格陣列。初始狀態(tài)，grid［i］［j］=0表示方格允許布線，而grid［i］［j］=1表示方格被封鎖。為了方便處理最外圍的邊界，在初始化的時(shí)候設(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; //左翼和右翼

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

//初始化相對(duì)位移

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(因?yàn)?和1已經(jīng)在前面使用)，故最后算路徑的時(shí)候，應(yīng)該減去2。

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

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

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++;

}

}

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

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

//活結(jié)點(diǎn)隊(duì)列是否非空？

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

else

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

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

Q.begin++;//取下一個(gè)擴(kuò)展結(jié)點(diǎn)

}

}while(true);

當(dāng)?shù)竭_(dá)finish時(shí)，可以回溯找到最初的start，然后形成最優(yōu)路徑。因?yàn)閺膕tart到finish是多對(duì)一的情況，所以在回溯的時(shí)候，一定是一對(duì)一的關(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;//向前移動(dòng)

}

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

2.5 算法性能分析

由于每個(gè)方格成為活結(jié)點(diǎn)進(jìn)入活結(jié)點(diǎn)隊(duì)列最多一次，因此活結(jié)點(diǎn)隊(duì)列中最多處理m×n個(gè)活結(jié)點(diǎn)。擴(kuò)

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

圖4 測(cè)試結(jié)果

3 結(jié) 語

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

參考文獻(xiàn)

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

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

［3］王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[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］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版[M].北京：清華大學(xué)出版社，1997.

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