前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分支限界法

分支限界法

作者头像
用户2965768
发布2018-08-30 16:35:44
1.7K0
发布2018-08-30 16:35:44
举报
文章被收录于专栏:wym

一.分支限界法的思想:

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

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

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

活结点表中。

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

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

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

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

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

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

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

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

三.分支界限法的边界

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

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

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

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

四.分支界限法的分支

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

并生产它的所有子女。

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

希望的结点。

五.查找路径的中止条件

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

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

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

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

六。 例子

求最小值,找下界。

那么,下界如何找呢?

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

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

有一份工作派了两个人。

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

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

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

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

选择最小值即可。

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

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

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

接下来对第二个点扩展

重复构造的过程,

这个解即为最优解。

我们再看一个例子,

01背包问题

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

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

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

就是这样,嗯。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年06月02日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档