常用算法笔记 > 分支限界法
分支限界法思想

和回溯法相似,也是一种搜索算法,但回溯法是找出问题的许多解,而分支限界法是找出原问题的一个解。或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解

在当前节点(扩展节点)处,先生成其所有的儿子节点(分支),然后再从当前的活节点(当前节点的子节点)表中选择下一个扩展节点。为了有效地选择下一个扩展节点,加速搜索的进程,在每一个活节点处,计算一个函数值(限界),并根据函数值,从当前活节点表中选择一个最有利的节点作为扩展节点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。

 

分支限界法:

1)FIFO分支限界法

3)优先队列分支限界法:按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

 

示例:装载问题,旅行售货员问题