数据结构与算法：Java版-分支限界法解题思路

分支限界法类似于回溯法，也是一种在问题的解空间树上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同，在解空间树上搜索方式不同。在求解目标上，回溯法的求解目标是找出解空间树中满足约束条件的所有解或最优解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。在搜索方式上，回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

那么分支限界法如何搜索呢？首先在扩展结点处，先生成其所有的孩子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有孩子结点。在这些孩子结点中，导致不可行解或导致非最优解的孩子结点被舍弃，其余孩子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法具体的算法步骤如下。

步骤1：设置最优解的初值。

步骤2：扩展根结点的所有儿子。对每一子结点x判定其是否满足解向量约束条件，对满足约束条件的x计算其限界值，满足限界条件的x加入活结点表。

步骤3：若x为叶子结点，检查是否比当前最优解更优，是则用该解更新当前最优解。(www.xing528.com)

步骤4：取活结点表中的第一个结点为子树根，重复步骤2。若活结点表中为空，则解题完毕。

从分支限界法的解题思路可以看出，会用到数据结构中的队列结构帮助实现求解过程。根据活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。

（1） 队列式分支限界法。按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。队列式分支限界法搜索解空间树的方式类似于解空间树的广度优先搜索，不同的是队列式分支限界法不搜索不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。

（2） 优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。结点的优先级常用一个与该结点有关的数值p来表示。最大优先队列规定p值较大的结点的优先级较高。在算法实现时通常用数据结构中的最大堆来实现最大优先队列，用最大堆的取最大值运算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规定p值较小的结点的优先级较高。同样可以用最小堆来实现。采用优先队列式分支限界算法解决具体问题时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点的p值。

不同的问题可以用不同的分支限界法解决，一般用回溯法求最优解的问题也可以用分支限界法解决，如0-1背包问题、装载问题、旅行商问题等。后面会以旅行商问题为例讲解分支限界法是怎么解决问题的。