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

五大常用算法之分支定界法看了五大常用算法之一这篇博文,感觉理解了很多,可是纯粹都是理论,缺少一些示例,所以准备综合一篇博文,以帮助自己记忆,原文:一、基本描述   类似于回溯法,也是一种在问题的解空间树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)


相关推荐

  • java心得体会_初学java之心得体会

    java心得体会_初学java之心得体会0.前言从学习java以来,已经进行过三次pta作业的训练。虽然每次作业的完成都遇到了些许困难和障碍,不是一帆风顺的,但通过自己的摸索,实践,总能完成作业要求,每次作业之后都有不同的收获。这些新的收获告诉我,实践出真知,动手会学习到更多东西。总结前面的三次作业,我发现面向对象程序设计这种语言不再那么神秘,我相信马上就能看到揭开神秘面纱后的的它。1.作业过程总结(1).总结三次作业的知识迭代关系第一…

  • php ora01017,使用dblink出现ORA-01017

    php ora01017,使用dblink出现ORA-01017本地的Oracle数据库是版本是10g的,远程的数据库版本版本是11g,在本地建数据库连接后执行测试查询语句竟然出错,用户名/密码明明本地的Oracle数据库是版本是10g的,远程的数据库版本版本是11g,在本地建数据库连接后执行测试查询语句竟然出错,用户名/密码明明是对的。SQL>createdatabaselinkDBLINK_TESTconnecttotestidenti…

  • Flutter Mac 安装全教程(Android / iOS)

    Flutter Mac 安装全教程(Android / iOS)本文来自于:https://flutter.io/docs/get-started/install/macos目录下载Flutter设置环境变量Flutter命令安装编辑IDE下载Flutterhttps://flutter.io/docs/development/tools/sdk/archive在这里获取Flutter的安装包,推荐使用stablechanne…

  • docker 离线安装_docker 离线安装

    docker 离线安装_docker 离线安装docker离线安装方法下载地址:https://download.docker.com/linux/static/stable/x86_64/参考文档:https://docs.docker.com/engine/install/binaries/机房设备无法访问互联网原因,需要进行离线安装K8S生态周报|Docker和containerd全版本漏洞公布,近期在Docker中发现了一个影响所有版本的安全漏洞CVE-2022-24769,该漏洞已经在Docker最新的版本v20

  • unittest测试框架原理_学软件测试4个月没找到工作

    unittest测试框架原理_学软件测试4个月没找到工作unittest框架解析unittest是python的单元测试框架,unittest单元测试提供了创建测试用例,测试套件以及批量执行的方案,unittest在安装pyhton以后就直接自带了,直接importunittest就可以使用。作为单元测试的框架,unittest也是可以对程序最小模块的一种敏捷化的测试。在自动化测试中,必须需要知道所使用语言的单元测试框架。利用单元测试框架,创建一个类,该类继承unittest的TestCase,这样可以把每个case看成是一个最小的单元,

    2022年10月15日
  • docker 使用 记录

    docker 使用 记录

发表回复

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

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