分支限界法

广度优先搜索（BFS）策略 §

• 所谓“分支”，就是采用广度优先的策略，依次搜索当前节点的所有分支
• 抛弃不满足约束条件的相邻节点，其余节点加入“活节点表”
• 然后从表中选择一个节点作为下一个扩展节点，继续搜索

限界策略 §

• 为了加速搜索的进程，一般会在每一个活节点处，计算一个函数值
• 根据这些已计算出的函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解

回溯法与分支界限法的区别 §

	回溯法	分支限界法
对解空间树的搜索方式	DFS	BFS
存储节点常用数据结构	堆栈	队列
应用场景	找出满足约束条件的所有解 找出全局最优解	找出满足约束条件的一个解 找出局部最优解