五大常用算法之分支定界法

五大常用算法之分支定界法看了五大常用算法之一这篇博文,感觉理解了很多,可是纯粹都是理论,缺少一些示例,所以准备综合一篇博文,以帮助自己记忆,原文:一、基本描述   类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

看了五大常用算法之一这篇博文,感觉理解了很多,可是纯粹都是理论,缺少一些示例,所以准备综合一篇博文,以帮助自己记忆,原文:

http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741378.html

一、基本描述

    类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解

   (1)分支搜索算法

    所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。

     选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。

   1)FIFO搜索

   2)LIFO搜索

   3)优先队列式搜索

(2)分支限界搜索算法 

二、分支限界法的一般过程

    由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T

    分支限界法的搜索策略是:在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。

    分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

三、回溯法和分支限界法的一些区别

    有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决,但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢?

回溯法和分支限界法的一些区别:

   方法对解空间树的搜索方式       存储结点的常用数据结构      结点存储特性常用应用

  回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解

  分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解

其他更好的解释:

分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点。

利用分支定界算法对问题的解空间树进行搜索,它的搜索策略是:

1 .产生当前扩展结点的所有孩子结点;

2 .在产生的孩子结点中,抛弃那些不可能产生可行解(或最优解)的结点;

3 .将其余的孩子结点加入活结点表;

4 .从活结点表中选择下一个活结点作为新的扩展结点。

如此循环,直到找到问题的可行解(最优解)或活结点表为空。

从活结点表中选择下一个活结点作为新的扩展结点,根据选择方式的不同,分支定界算法通常可以分为两种形式:

1 . FIFO(First In First Out) 分支定界算法:按照先进先出原则选择下一个活结点作为扩展结点,即从活结点表中取出结点的顺序与加入结点的顺序相同。

2 .最小耗费或最大收益分支定界算法:在这种情况下,每个结点都有一个耗费或收益。假如要查找一个具有最小耗费的解,那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点;假如要查找一个具有最大收益的解,那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。

FIFO分支定界算法

因为没有一个感觉好的说明,固贴上两个网址上的算法,有兴趣可以看一看。

FIFO分支定界算法初探

http://www.21shipin.com/html/62062.shtml

常用算法大全-分枝定界

http://www.cppblog.com/ivenher/articles/1777.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/230742.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • notepad正则删除关键词所在行

    notepad正则删除关键词所在行

  • python,java,c语言哪个好_小萌新

    python,java,c语言哪个好_小萌新大学那会也被这个问题被困惑了大半年,直到毕业拿了几个大厂offer才发现语言的选择也就那一回事,我猜不少人刚入门的人依然被这个问题困扰着,所以决定认真分享一波我的经历。如果你还处于大一,大二,或者刚刚入门阶段,那么我认为,语言的选择并不重要,更重要的是底层/通用基础的学习,例如数据结构,算法,计算机网络这些,因为这些语言,是存在很多相同的特性的,例如你学习了C++,后面要转Java,那么其实还是可以很快就上手的。而且,等到了差不多毕业去应聘校招的时候,其实公司并不会对语言有严格的要求,例如你要面

    2022年10月22日
  • 【转】document.cookie详解

    【转】document.cookie详解js中cookie详解

  • VggNet10模型的cifar10深度学习训练

    VggNet10模型的cifar10深度学习训练目录一:数据准备:二:VGG模型三:代码部分1.input_data.py2.VGG.py3.tools.py4.train_and_val.py一:数据准备:先放些链接,cifar10的数据集的下载地址:http://www.cs.toronto.edu/~kriz/cifar.html用二进制tfcords的数据集训练,下载第三个,下载的数据文件集是…

  • springmvc笔记_SpringMVC优点

    springmvc笔记_SpringMVC优点MVC简介普通的web项目每次都要进行手动的把jar包导进去,否则会报500,classnotfound[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VstjHhuz-1609824493673)(C:\Users\王东梁\AppData\Roaming\Typora\typora-user-images\image-20210104132339761.png)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L9AgS48A-16

    2022年10月15日
  • MPU9250传感器

    MPU9250内部包括3轴陀螺仪、3轴加速度计和3轴磁力计,这3个功能输出都是16位的数字量;可以通过常用的数据总线(IIC)接口和单片机进行数据交互,传输速率400kHz/s。陀螺仪的角速度测量范围±2000(°/s),具有良好的动态响应特性。加速度计的测量范围最大为±16g(g为重力加速度),静态测量精度高。磁力计采用高灵度霍尔型传感器进行数据采集,磁感应强度测量范围为±4800μT,可用于对偏航角的辅助测量。MPU9250自带的数字运动处理器DMP硬件加速引擎,可

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号