分支限界算法的研究與實現

王春梅

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

關鍵詞：分支限界； 解空間樹； 活結點； 擴展結點

中圖分類號：TN911-34文獻標識碼：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 引 言

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

1 分支限界算法

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

1.1 分支限界算法策略

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

(1) 產生當前擴展結點的所有子結點；

(2) 在產生的子結點中，拋棄那些不可能產生可行解(或最優解)的結點(剪枝)；

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

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

1.2 分支限界算法實施步驟

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

p為分支層數；C*為當前最優目標函數值；

P*為相應于C*的工件順序；

P1為當前結點(現在需要進行分支的結點)所對應的部分序列。

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

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

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

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

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

步驟6:若p≠0，去掉P1中最后一個工件，轉步驟3；否則，算法停止。C*是最優的目標函數值，P*是最優順序。

2 電路板布線問題

2.1 問題描述

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

圖1 布線簡圖

2.2 應用分支限界算法的設計思路

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

圖2 布線路徑圖

2.3 算法描述流程圖

算法流程如圖3所示。

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

圖3 算法描述流程圖

2.4 算法實現

電路板上方格位置的數據類型描述如下：

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

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

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; //左翼和右翼

算法開始測試起初方格與目標方格是否相同。如果相同，則不用計算，直接返回距離0(做無解對待)，否則算法設置方格陣列的“圍墻”，初始化矩陣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;//上

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

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

do { //標記相鄰可達方格

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)

{ //該方格未被標記

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

}

}

//是否到達目標位置finish？

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

//活結點隊列是否非空？

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

else

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

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

Q.begin++;//取下一個擴展結點

}

}while(true);

當到達finish時，可以回溯找到最初的start，然后形成最優路徑。因為從start到finish是多對一的情況，所以在回溯的時候，一定是一對一的關系，也就是說，路徑是惟一的。

//構造最短布線路徑

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

path=new Position［PathLen］;

//從目標位置finish開始向起始位置回溯

here=finish;

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

{path［j］=here;

//找前驅位置

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;//向前移動

}

測試結果,如圖4所示。

2.5 算法性能分析

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

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

圖4 測試結果

3 結 語

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

參考文獻

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

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

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

［4］潘愛民.VC++技術內幕[M].4版.北京：清華大學出版社，2004.

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

［6］[美]HORSTMANN Cay.C++核心思想[M].3版.北京：電子工業出版社，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］嚴蔚敏，吳偉民.數據結構C語言版[M].北京：清華大學出版社，1997.

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