当前位置:   article > 正文

五大算法之分支界限法

分支界限

基本思想
  分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。
搜索策略
  在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一个扩展结点,以加速搜索的进程,在每一活结点处,根据限界函数估算目标函数的可能取值(优先值),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点(使目标函数取得极值(极大/极小)的结点)作为扩展结点,优先进行广度优先搜索,使搜索朝着解空间树上有最优解的分支推进, 不断调整搜索方向,以便尽快地找出一个最优解。

特点
    限界函数常基于问题的目标函数,适用于求解最优化问题。

在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分枝界限法与回溯法的区别

1)求解目标不同
             回溯法的求解目标是找出解空间树中满足约束条件的所有解
            分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
(2)搜索方式不同
             回溯法以深度优先的方式搜索解空间树
             分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树
(3)对扩展结点的扩展方式不同
             分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。
(4)存储空间的要求不同
            分支限界法的存储空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。

求解步骤
①定义解空间(对解编码)
②确定解空间的树结构
③按BFS等方式搜索
a.每个活结点仅有一次机会变成扩展结点
b.由扩展结点生成一步可达的新结点
c.在新结点中,删除不可能导出最优解的结点 //限界策略
d.将剩余的新结点加入活结点表(队列)中
e.从活结点表中选择结点再扩展 //分支策略
f.直至活结点表为空

常见的两种分支界限法:

1)队列式(FIFO)分支限界法
按队列先进先出(FIFO)原则选取下一个结点为扩展结点。
从活结点表中取出结点的顺序与加入结点的顺序相同,因此活结点表的性质与队列相同。
(2)优先队列式分支限界法
按优先队列中规定的优先级,选取优先级最高的结点成为当前扩展结点。
每个结点都有一个对应的耗费或收益,以此决定结点的优先级。
如果查找一个具有最小耗费的解,则活结点可用小根堆来建立,下一个扩展结点就是具有最小耗费的活结点。
如果搜索一个具有最大收益的解,则可用大根堆来构造活结点表,下一个扩展结点是具有最大收益的活结点。

问题的解空间:与回溯法相同,一般用解空间树(Solution Space Tree,也称状态空间树)的方式组织。

优先队列式分枝界限法求解最大化问题的一般过程

根据限界函数确定目标函数的界[down,up]
将待处理结点活结点表初始化为空
对根结点的每个孩子结点x执行下列操作
3.1 估算结点x的目标函数值value
3.2 若(value>=down),则将结点x加入活结点表中
循环直到某个叶子结点的目标函数值在活结点表中最大
4.1 i=活结点表中值最大的结点
4.2 对结点i的每个孩子结点x执行下列操作
4.2.1 估算结点x的目标函数值value
4.2.2 若(value>=down),则将结点x加入活结点表中
4.2.3 若(结点x是叶子结点且结点x的value值在活结点表中最大),则将结点x对应的解输出,算法结束
4.2.4 若(结点x是叶子结点且结点x的value值在活结点表中不是最大),则令down=value,并且将活结点表中所有小于value的结点删除

分支界限法的时间性能

分支限界法的最坏时间复杂性为指数阶
    和回溯法都属于穷举法。
   在最坏情况下,遍历解空间树的时间复杂性为指数阶。
   解空间树具有指数阶个结点。
与回溯法不同之处
    分支限界法首先扩展解空间树中的上层结点,并采用限界函数,有利于实行大范围剪枝。
    根据限界函数不断调整搜索方向,选择最有可能取得最优解的子树优先进行搜索。
    如果选择了结点的合理扩展顺序以及设计了一个好的限界函数,分支限界法可以快速得到问题的解。

分支限界法的较高效率是以付出一定代价为基础的,其工作方式造成了算法设计的复杂性。
更好的限界函数
   好限界函数通常需花费更多的时间计算相应的目标函数值。
   对于具体的问题实例,通常需要进行大量实验,才能确定一个好的限界函数。
   为得到最优解,需保存从根结点到各个扩展结的路径或构建搜索经过的树
   分支限界法跳跃式处理结点,在搜索到某个叶子结点得到最优值时,为从该叶子结点求出对应的最优解中的各个分量,需要对每个扩展结点保存该结点到根结点的路径,或者在搜索过程中构建搜索经过的树结构。加大了算法的设计复杂度。
活结点表
   维护待处理结点活结点表
   在表中快速查找取得极值的结点
   上述工作都需要较大的存储空间。
   在最坏情况下,分支限界法需要的空间复杂性是指数阶。

 

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/630006
推荐阅读
相关标签
  

闽ICP备14008679号