分支限界法是五大常用算法之一

一、基本描述

与回溯法类似地，在解空间树T上搜索问题解也是一种算法——分支限界法。然而，在求取问题解决方案的目标上存在显著差异：回溯法旨在通过探索所有可能的方式寻找满足约束条件的所有可行解决方案；而分支限界法则主要致力于寻找满足特定约束条件的一个可行解决方案，并在此基础上寻求使某一目标函数值达到极大或极小的最优解决方案。

（1）分支搜索算法

即为按照广度优先的方法展开搜索过程，在遍历E-节点的所有分支时会依次考察每一个相邻节点；在此过程中会排除那些不符合约束条件的节点；而那些符合条件的节点则会被成功地加入到活节点列表中。随后系统会从列表中选取下一个待处理的E-节点，并继续展开后续搜索步骤。

选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。

1）FIFO搜索

2）LIFO搜索

3）优先队列式搜索

（2）分支限界搜索算法

二、分支限界法的一般过程

基于不同的求解目标，在构建同一棵解空间树T时

分支限界法的核心策略在于：当处理节点时，在其子节点之间进行遍历，并系统性地筛选潜在的目标节点。为了高效地确定下一个处理节点，并加快搜索速度，在每一活节点处都需要评估每个节点的价值（限界）。通过这些评估结果来优先探索可能包含最优解的路径。

分支限界法通常采用广度优先策略或基于最小耗费（最大效益）的优先级来探索问题的解空间树结构。