文档章节

算法---->分支限界

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 2781
阅读 10
收藏 0
点赞 0
评论 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

游戏与常用的五大算法---下篇

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

loving_forever_ ⋅ 2017/01/08 ⋅ 0

五大常用算法:分治、动态规划、贪心、回溯、分支限界

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

毛朱 ⋅ 2015/09/11 ⋅ 0

回溯算法之购物车(0-1 背包问题)

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

u011068702 ⋅ 05/10 ⋅ 0

算法设计策略----回溯法和分枝限界法

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

Superheros ⋅ 03/10 ⋅ 0

动态规划和分治法,贪心算法以及递归的再一次深刻理解和体会

每次体会算法都有新的感觉,刷题越多,对算法的理解感觉也就越深刻。 下面我们来重新体会下分治法,动态规划,贪心法,递归的理解。 1.分治法: 将问题分成单独的阶段,每个阶段互相不干扰很...

qingliangdexiar ⋅ 2017/08/25 ⋅ 0

swift学习——点点滴滴——3~著名算法

⽐比较著名的算法有 冒泡法,贪⼼心算法,递归法,迭代法,分治法,动态规划法,分⽀支限界 法,回溯法,A*寻路算法 等等。 ps:记录下,日后多多练习这些算法。

cat_l_fish ⋅ 2014/11/03 ⋅ 0

面试算法:线性表

链表 队列 堆栈 实践应用 难题首选[动归],受阻[贪心][暴力];考虑[分治]思想,配合[排序][哈希]; 动态规划:动态数组降低空间复杂度 贪心法:Dijkstra最短路径、最小生成树Prim、Kruskal算...

datacube ⋅ 2016/07/20 ⋅ 0

几种常用的算法简介

1、穷举法 穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出满足条件的解。 穷举法的运用关键在于解决两个问题: 如何列举所有的可能解; 如何判别可能解...

hanzhankang ⋅ 2014/01/21 ⋅ 0

异步社区本周半价电子书(5月28日-6月03日)

《Kafka入门与实践》 作者:牟大恩 点此链接购买纸书 本书以Kafka 0.10.1.1版本以基础,对Kafka的基本组件的实现细节及其基本应用进行了详细介绍,同时,通过对Kafka与当前大数据主流框架整合...

异步社区 ⋅ 05/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Gitee 生成并部署SSH key

1.如何生成ssh公钥 你可以按如下命令来生成 sshkey: ssh-keygen -t rsa -C "xxxxx@xxxxx.com" # Generating public/private rsa key pair...# 三次回车即可生成 ssh key 查看你的 ...

晨猫 ⋅ 26分钟前 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部