广度优先搜索与最优子树剪枝结合的方法

1.分支限界法与回溯法对比分析

（1）问题求解目标：回溯法旨在解空间树中识别出所有符合约束条件的可行解，而分支限界法的目标则是确定一个满足约束条件的解，或者在所有满足约束条件的解中，找到某种标准下最优的解。
（2）搜索策略差异：回溯法采用深度优先策略对解空间树进行遍历，而分支限界法则依据广度优先或最小耗费优先的原则进行搜索。

2.分支限界法的基本思想

分支限界法通常采用广度优先或以最小耗费（最大效益）为优先原则，对问题的解空间树进行搜索。在该方法中，每个活结点仅有一次机会被选为扩展结点。一旦某个活结点被选为扩展结点，将一次性生成其所有子节点。在这些子节点中，若存在导致不可行解或非最优解的情况，则会被直接舍弃，而其余可行的子节点则被添加至活结点表中。随后，从活结点表中选取下一个节点作为当前的扩展结点，并重复上述扩展过程。这一流程将持续进行，直至找到目标解或活结点表为空为止。

3.常见的两种分支限界法

【

（1）基于先进先出原则的队列式分支限界法
在该方法中，扩展结点的选择依据队列的先进先出规则进行确定。
（2）基于优先级排序的分支限界法
此方法通过优先队列中的优先级设定，选择当前优先级最高的结点作为扩展对象。

4.单源最短路径问题

4.1 问题的描述