分支限界法
什么是分支限界法?
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
分支限界法与回溯法区别：
- 求解目标： 回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
- 搜索方式： 回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
常见的2种分支限界法：
- 队列式分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
- 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
算法流程
- 确定问题的解空间树；
- 确定一个合理的限界函数；
- 按BFS广度优先方式搜索解空间树；
- 重复上述过程，直到得到最优解；