分支限界法的基本思想是什么？

分支限界法的基本思想是什么？

分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题的算法。但分支限界法的求解目标是找出满足约束条件的一个最优解。搜索策略是广度优先，既在扩展结点点，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。在每一个活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点队列中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上最优解的分枝推进，以便尽快找到一个最优解。