分支限界法

一.分支限界法的思想:

1)在分支限界法中,每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点

中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入

活结点表中。

2)此后,从活结点表中取下一结点成为当前扩展结点,并重复上述扩展

过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

二.分支限界法与回溯法的异同

1)求解目标:回溯法求解的目标时找出解空间树中满足约束条件的所有解,

而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束

条件的解中找出在某种意义下的最优解。

2)搜索方式不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则

以广度优先或以最小耗费优先的方式搜索解空间树。

三.分支界限法的边界

用分支界限法解决问题的关键是找边界,上界或下界。

1)对于一颗状态空间树的每一个结点所代表的部分解,要提供一种方法,

计算出通过这个部分解繁衍出的任何解在目标函数上的最佳值边界。

2)对于最小化问题,找下界,对于最大化问题,找上界。

四.分支界限法的分支

1)在当前树的未中止(活的)叶子节点中,选择其中最有希望的结点,

并生产它的所有子女。

2)比较活叶子结点的上界/下界,把具有最佳上界/下界的结点作为最有

希望的结点。

五.查找路径的中止条件

1)该结点的边界值不能超过目前最佳解的值。

2) 该结点无法代表任何可行解,因为它已经违反了约束条件。

3)该结点代表的可行解的子集只包含一个单独的点

(因此无法给出更多的选择)。

六。 例子

求最小值,找下界。

那么,下界如何找呢?

    我们可以按照行优先和列优先。 这里我们采用行优先,找出每一行最小值求和,那么最优解一定不会大于这个值,

因为这样选出的下界是可能违法约束条件的,这里的下界就是:

有一份工作派了两个人。

接着开始构树,start为开始的根节点,那么他会有几个分支呢?

看完第一张图再想想看,应该是4个分支,把接下来的分支都计算出

问题来了,为什么下面这张图改变了值呢?不是选3,1,4而是4,5,4

这里我们注意下不能选已经安排的工作,(这一层以前包括这一层都是已经安排的),其他行

选择最小值即可。

然后我们看,选哪一个继续扩展呢?是四个都扩展吗?

答案是否定的,因为其他三个是在未被安排的工作取最小值的情况下求的和,可能违反约束条件(每个工作派一个人),

在这种情况下都比别的小,没有必要扩展了,

接下来对第二个点扩展

重复构造的过程,

这个解即为最优解。

我们再看一个例子,

01背包问题

这个是求最大值,则求上界。

性价比最后一栏是第一个是10,不方便改啦(懒。。)

根据决策函数(这个不唯一,看个人怎么想),然后一样的每次选择当前最小(大)消耗

就是这样,嗯。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术点滴

绝对均匀图生成算法一、何为绝对均匀图?二、简单讨论一下三、试一下递归?四、核心思想五、算法实现与测试

最近在研究图计算的性能,需要构造不同的测试数据对图算法进行压测,其中就涉及到均匀图的概念。

1052
来自专栏生信技能树

R语言的各种统计分布函数

http://www.bio-info-trainee.com/1656.html

3183
来自专栏小樱的经验随笔

想了解概率图模型?你要先理解图论的基本定义与形式

图论一直是数学里十分重要的学科,其以图为研究对象,通常用来描述某些事物之间的某种特定关系。而在机器学习的世界里,我们希望从数据中挖掘出隐含信息或模型。因此,如...

3668
来自专栏量子位

亚马逊发布新版MXNet:支持英伟达Volta和稀疏张量

安妮 编译自 AWS官博 量子位 出品 | 公众号 QbitAI Apache MXNet v0.12来了。 今天凌晨,亚马逊宣布了MXNet新版本,在这个版本...

4026
来自专栏人工智能LeadAI

TensorFlow应用实战-17-Qlearning实现迷宫小游戏

总共有12个状态,s1到s12.对于每一个状态会有四个动作。对于每个状态下的每个动作会有一个Q的值。

4481
来自专栏黑豆梨的曲线机器学习路线

牛顿法(Newton Method)求解f(x)=0

https://en.wikipedia.org/wiki/Newton%27s_method

3289
来自专栏和蔼的张星的图像处理专栏

暗通道去雾改进算法及实现

上次搞的暗通道去雾的算法交给老师就算是交差了,当时也就是个调研而已。前几天又被老师叫过去说还是需要720p(1280*720)图像的实时处理,看能不能再做一些优...

3542
来自专栏深度学习之tensorflow实战篇

推荐算法图推荐-基于随机游走的personalrank算法实现

推荐算法图推荐 基于图的模型(graph-based model)是推荐系统中的重要内容。其实,很多研究人员把基于邻域的模型也称为基于图的模型,因为可以把基于邻...

1.9K9
来自专栏数据小魔方

R语言数据可视化之——TreeMap

今天这一篇跟大家分享R语言数据可视化之——TreeMap。 在R语言中制作树状图需要独立的树状图工具包——TreeMap的支持。 该包中提供特有的treemap...

3314
来自专栏机器之心

NIPS 2018 | 程序翻译新突破:UC伯克利提出树到树的程序翻译神经网络

程序是构建计算机应用、IT 产业和数码世界的主要工具。为了方便程序员为不同的应用开发程序,人们发明了各种编程语言。与此同时,当程序员想要将用不同语言编写的程序组...

1071

扫码关注云+社区

领取腾讯云代金券