首页 > 代码库 > 分支限界法
分支限界法
一、分支限界法的基本思想
在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以使尽快找出一个最优解。
(1)活结点:如果已生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点。
(2)扩展结点:当前正在生成其儿子结点的活结点叫扩展结点(正扩展的结点)。
(3)死结点:不再进一步扩展或者其儿子结点已全部生成的结点就是死结点。
(4)解空间:对于问题的一个实例,解向量满足显式约束条件的所有多元组,构成了该实例的一个解空间。
(5)广度优先的问题状态生成法:在一个扩展结点变成死结点之前,它一直是扩展结点。
二、回溯法和分支限界法的比较
分支限界法与回溯法的不同:
(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
图1.1 回溯法和分支限界法的比较
分支限界法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。