文档章节

算法---->分支限界

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 2781
阅读 10
收藏 0

分支限界法

  

一、分支搜索

 活结点:自己已经被生成,但还没有被检测的结点。

“分支”是采用广度优先的策略,依次生成E-结点所有分支,也就是所有的儿子结点。和回溯法一样,可以在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点。

选择下一个E-结点方式的不同导致几种分支搜索方式:

搜索方式

 

活节点存储结构

活结点选择

FIFO搜索

First In First Out,BFS

队列

取出队首结点

LIFO搜索

Last In First Out,D-Search

栈弹出一个结点

优先队列式搜索

Least Cost(最小代价)

优先级最高的结点

 

1.1、分支搜索-FIFO搜索

1.一开始,根结点是唯一的活结点,根结点入队。

2.从活结点队中取出根结点后,作为当前扩展结点。

3.对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。

4.再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点,……,直到找到一个解或活结点队列为空为止。

1.2、分支搜索-LIFO搜索

  1. 一开始,根结点入栈。
  2. 从栈中弹出一个结点为当前扩展结点。
  3. 对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子入栈;
  4. 再从栈中弹出一个结点(栈中最后进来的结点)为当前扩展结点,……,直到找到一个解或栈为空为止。

LIFO和FIFO分枝-限界法存在的问题

对下一个E-结点的选择规则过于死板、盲目。对于有可能快速检索到一个答案结点的结点没有给出任何优先权。

1.3、分支搜索-优先队列式搜索(LC检索、最小成本检索)

  • 为了加速搜索的进程,可以采用有效的方式选择E-结点进行扩展。
  • 优先队列式搜索,对每一活结点计算一个优先级(某些信息的函数值);
  • 根据这些优先级,从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。

对于任一结点,用该结点导致答案结点的成本(代价)来衡量该结点的优先级——成本越小越优先。

二、LC检索中最小成本的计算

2.1、结点成本函数C(X)的定义:

    1)如果X是答案结点,则C(X)是由状态空间树的根结点到X的成本(即所用的代价,可以是级数、计算复杂度等)

    2)  如果X不是答案结点且子树X不包含任何答案结点,则C(X)=∞

    3)  如果X不是答案结点但子树X包含答案结点,则C(X)等于子树X中具有最小成本的答案结点的成本

计算一个结点的代价通常要检索包含一个答案结点的子树X才能确定,因此计算C(X)的工作量和复杂度与解原始问题是相同的。要得到精确的成本函数一般是不现实的,需要成本估计函数g^(X)

2.2、成本估计函数g^(x)

出现的新问题:仅利用g^(X) 会导致算法偏向纵深检查,无法有效处理下面这种情况:即g^(W)<g^(Z),但Z比W更接近答案结点

2.3、成本估计函数改进

为使算法不过分偏向于纵深检查,需改进成本估计函数,使其不只考虑结点X到一个答案结点的估计成本,还应考虑根节点到结点X的成本.可以减少算法作偏向于纵深检查的可能性,它强使算法优先检索更靠近答案结点但又离根较近的结点。

 c^(X) =f(h(X)) + g^(X)

h(X)为根结点到结点X的成本

g^(X)是由X到达一个答案结点所需做的附加工作的估计函数 

2.4、统一

 LC-限界检索:选择c^(·)值最小的活结点作为下一个E-结点

 BFS: g^(X)=0; f (h(X)) =X的级数

 D-Search:f(h(X)) =0;每当Y是X的一个儿子时,总有g^(X)>=g^(Y),

 

三、分枝-限界法

3.1、限界函数

在结点的生成过程中,需要用限界函数杀死还没有全部生成儿子结点的一些活结点——这些活结点无法满足限界函数的条件,不可能导致问题的答案。剪枝函数给出每个可行节点相应的子树可能获得的最大价值的上界,若这上界不比当前最大价值大,则剪枝。

3.2、目标函数限界U的调整

初始U可取∞,随回答结点值的求出逐步更新为U=c(x*),x*为已知回答结点中值最小者。

3.3、分支限界法基本思想

在问题的解空间树中进行广度优先搜索. 找一个回答结点使其对应路径的权最小(最大)。当搜索到达一个扩展结点时,一次性扩展它的所有儿子,将那些满足约束条件且最小耗费函数目标函数限界的儿子,插入活动结点表中, 再从活动结点表中取下一结点同样扩展. 直到找到所需的解或活动结点表为空为止。

3.4、分支限界法的搜索策略

在当前节点(扩展节点)处,先生成其所有的儿子节点(分支),然后再从当前的活节点(当前节点的子节点)表中选择下一个扩展节点。为了有效地选择下一个扩展节点,加速搜索的进程,在每一个活节点处,分别估算这些孩子结点的目标函数的可能取值(对最小化问题,估算结点的down,对最大化问题,估算结点的up)。如果某孩子结点的目标函数值超出目标函数的界,则将其丢弃(从此结点生成的解不会比目前已得的更好),否则入待处理表。,并根据函数值,从当前活节点表中选择一个最有利的节点作为扩展节点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。 

3.5、分支限界法解题步骤

1.取U=U(T).

2.扩展根结点的所有儿子.对每一子结点x判定其是否满足约束条件, 

   对满足约束条件的x计算 , 将≤U的x加入活动结点表.

3. x为叶结点时,检查是否c(x)<U,是则用c(x)更U.

4.取活动结点表中的第一个结点为根, 重复2.

四、对比回溯法

分支限界法类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。

分枝-限界法在生成当前E-结点全部儿子之后再生成其它活结点的儿子,且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。

回溯法:使用限界函数的深度优先结点生成方法称为回溯法(backtracking)

 

1.回溯法的求解目标是找出解空间中满足约束条件的所有解,想必之下,分支限界法的求解目标则是找出满足约束条件的一个解,或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。

2.另外还有一个非常大的不同点就是,回溯法以深度优先的方式搜索解空间,而分支界限法则以广度优先的方式或以最小耗费优先的方式搜索解空间。采用广度优先搜索策略的目的是:尽早发现剪枝点.

3.分支限界法不仅通过约束条件,而且可通过目标函数的限界来减少无效搜索

 

回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。它们在问题的解空间树T上搜索的方法不同,适合解决的问题也就不同。一般情况下,回溯法的求解目标是找出T中满足约束条件的所有解的方案,而支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。相对而言,分支限界算法的解空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。

 

 

在处理最优问题时,采用穷举法、回溯法或分支限界法都可以通过利用当前最优解和上界函数加速。仅就对限界剪支的效率而言,优先队列的分支限界法显然要更充分一些。在穷举法中通过上界函数与当前情况下函数值的比较可以直接略过不合要求的情况而省去了更进一步的枚举和判断;回溯法则因为层次的划分,可以在上界函数值小于当前最优解时,剪去以该结点为根的子树,也就是节省了搜索范围;分支限界法在这方面除了可以做到回溯法能做到的之外,同时若采用优先队列的分支限界法,用上界函数作为活结点的优先级,一旦有叶结点成为当前扩展结点,就意味着该叶结点所对应的解即为最优解,可以立即终止其余的过程。在前面的例题中曾说明,优先队列的分支限界法更象是有选择、有目的地进行搜索,时间效率、空间效率都是比较高的。

五、应用

分支限界---->15-谜问题

分支限界---->装载问题

分支限界---->0/1背包问题

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/16/5637084.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
算法设计与分析复习——第六章:分支先结法

第六章:分支先结法 1,请简述分支限界法的算法思想以及两种主要的实现方法。 答:分支限界法的算法思想是在问题的解空间树上以广度优先或最小耗费(最大效益)优先方式搜索问题的满足约束条...

科技小能手
2017/11/12
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
五大常用算法:分治、动态规划、贪心、回溯、分支限界

分治:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 http://www.cnblogs.com/ste...

毛朱
2015/09/11
2.5K
0
回溯算法之购物车(0-1 背包问题)

1、问题(参考趣学算法) 2、分析 3、代码实现 #include include using namespace std; define MAX_NUM 200 //商品的个数,载物车最大承受重量int n = 0, W = 0;//当前载物车里面的总重量和总...

u011068702
05/10
0
0
算法设计策略----回溯法和分枝限界法

显示约束和解空间:规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题,显示约束规定了所有可能的元组,他们组成问题的候选解集,被称为该问题实例的解空间。 隐式约束和判定函数...

Superheros
03/10
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 种族不同,禁止交往

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @小小编辑:推荐歌曲《苏菲小姐》- 鱼果 《苏菲小姐》- 鱼果 手机党少年们想听歌,请使劲儿戳(这里) @貓夏:下大雨 正是睡觉的好时候 临睡前...

小小编辑
今天
183
6
Python 搭建简单服务器

Python动态服务器网页(需要使用WSGI接口),基本实现步骤如下: 1.等待客户端的链接,服务器会收到一个http协议的请求数据报 2.利用正则表达式对这个请求数据报进行解析(请求方式、提取出文...

代码打碟手
今天
1
0
Confluence 6 删除垃圾内容

属性(profile)垃圾 属性垃圾的定义为,一个垃圾用户在 Confluence 创建了用户,但是这个用户在自己的属性页面中添加了垃圾 URL。 如果你有很多垃圾用户在你的系统中创建了属性,你可以使用...

honeymose
今天
0
0
qduoj~前端~二次开发~打包docker镜像并上传到阿里云容器镜像仓库

上一篇文章https://my.oschina.net/finchxu/blog/1930017记录了怎么在本地修改前端,现在我要把我的修改添加到部署到本地的前端的docker容器中,然后打包这个容器成为一个本地镜像,然后把这...

虚拟世界的懒猫
今天
1
0
UML中 的各种符号含义

Class Notation A class notation consists of three parts: Class Name The name of the class appears in the first partition. Class Attributes Attributes are shown in the second par......

hutaishi
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部