【图文】第10讲分支限界法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
第10讲分支限界法
上传于||文档简介
大小：433.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢五大常用算法之五：分支限界法 - 文章 - 伯乐在线
& 五大常用算法之五：分支限界法
一、基本描述
类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
（1）分支搜索算法
所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。
选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。
1）FIFO搜索
2）LIFO搜索
3）优先队列式搜索
（2）分支限界搜索算法
二、分支限界法的一般过程
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
三、回溯法和分支限界法的一些区别
有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析----到底何时使用分支限界而何时使用回溯呢？
回溯法和分支限界法的一些区别：
方法对解空间树的搜索方式
存储结点的常用数据结构
结点存储特性常用应用
回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解
可能感兴趣的话题
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2017 伯乐在线sohocoder收集全网最新、最全项目(pythontip出品)
算法详解之分支限界法
首先我们来关注一个问题：
布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。如下图所示：
布线问题的解空间是一个图，则从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。
在实现上述算法时，
（1） 定义一个表示电路板上方格位置的类Position。
它的2个成员row和col分别表示方格所在的行和列。在方格处，布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0，1，2，3。下表中，offset[i].row和offset[i].col(i= 0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。
（2） 用二维数组grid表示所给的方格阵列。
初始时，grid[i][j] = 0, 表示该方格允许布线，而grid[i][j] = 1表示该方格被封锁，不允许布线。
算法图解：
代码贴出来：
#include &stdio.h&
typedef struct {
int FindPath (Position start, Position finish, int &PathLen, Position *&path)
{ //计算从起始位置start到目标位置finish的最短布线路径，找到返回1，否则，返回0
if ((start.row = = finish.row) && (start.col = = finish.col)) {
PathLen = 0;
return 0; } //start = finish
//设置方格阵列”围墙”
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; //左翼和右翼
//初始化相对位移
NumOfNbrs = 4; //相邻方格数
Position offset[4], here,
offset[0].row = 0;
offset[0].col = 1;
offset[0].row = 1;
offset[0].col = 0;
offset[0].row = 0;
offset[0].col = -1;
offset[0].row = -1;
offset[0].row = 0;
here.row = start.
here.col = start.
LinkedQueue &Position& Q; //标记可达方格位置
for (i = 0; i& NumOfN i++) { //标记可达相邻方格
nbr.row = here.row + offset[i].
nbr.col = here.col + offset[i].
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))//完成布线
Q.Add(nbr);
if ((nbr.row = = finishi.row) && (nbr.col = = finish.col))//完成布线
if (Q.IsEmpty()) //活队列是否为空
return 0; //无解
Q.delete(here); //取下一个扩展结点
}while (1);
//构造最短布线路径
PathLen = grid[finish.row][finish.col] － 2;
path = new Position[PathLen];
for (int j = PathLen - 1; j &= 0; j--) { //找前驱位置
for (i = 0; i& NumOfN i++) {
nbr.row = here.row + offset[i].
nbr.col = here.col + offset[i].
if (grid[nbr.row][nbr.col] = = j+2)
here = //向前移动
void main ()
int grid[8][8];
int PathLen, *
Position start,
start.row = 3;
start.col = 2;
finish.row = 4; finish.col = 6;
FindPath (start, finish, PathLen, path);
好了，问题解出来了。咦，我们用的是什么方法呢？呵呵，对，这就是分支限界算法。
算法总结：
分支限界法基本思想：
o 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
o 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
o 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
o 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
分支限界法与回溯法的不同：
（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
原文链接:/articles/zAv2Er
阅读: 399 |