分支限界算法的研究与实现

摘 要：分支限界算法是一种在问题的解空间树上搜索问题的解的方法，主要采用广度优先或最小耗费优先的方法搜索解空间树，其核心思想就是“剪枝”。首先提出了分支限界算法的一般策略与实施步骤，然后以电路板布线问题为实例，设计并实现该问题的算法，经过实验数据验证了其性能，进而反映了分支限界算法的高效性。

关键词：分支限界； 解空间树； 活结点； 扩展结点

中图分类号：TN911-34文献标识码：A

文章编号：1004-373X(2011)09-0121-03

Research and Implementation of Branch and Bound Algorithm

WANG Chun-mei

(Department of Computer, Xi’an Institute of Posts and Telecommunications, Xi’an 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:计算从当前结点分支得到的各个子结点的下界，并按下界值由小到大对各子结点排序。令pp+1；

步骤3:如果当前结点被探测尽，令pp-1，转步骤6，否则，设当前层(第p层)各活动子结点中具有最小下界值的结点为Q，则在P1末尾加入Q对应第p位置上的工件，此时的当前结点转到Q，转步骤4。

步骤4:因为当前结点是同层同父结点具有最小下界值的结点，如果当前结点下界值大于或等于C*，则不必再搜索当前结点及其同层同父的活动结点,这样,当前结点的上一层结点(父结点)被探测尽,pp-1，去掉P1中的最后一个工件，转步骤6，否则，转步骤5。

步骤5:如果p=n，则得到一个较优顺序。令P*=P1，C*是当前结点的下界值，pp-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

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

for( i=0; 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]. .

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

［10］严蔚敏，吴伟民.数据结构C语言版[M].北京：清华大学出版社，1997.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文