第八章分支限界法 §1算法基本思想 本章叙述中为了区别图中的顶点和解空间树中的顶点,凡是在解 空间树中出线队顶点一律称为结点。 分支限界法同回溯法类似,它也是在解空间中搜索问题的可行解 或最优解,但搜索的方式不同。回溯法采用深度优先的方式,朝纵深 方向搜索,直至达到问题的一个可行解,或经判断沿此路径不会达到 问题的可行解或最优解时,停止向前搜索,并沿原路返回到该路径上 最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支 定界法则采用宽度优先的方式搜索解空间树,它将活结点存放在一个 特殊的表中。其策略是:在扩展结点处,先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃,其余儿子加入活结 点表中。此后,从活结点表中取出一个结点作为当前扩展结点。并重 复上述结点扩展过程。所以,分支限界法与回溯法的本质区别在于搜 索方式的不同。回溯法更适于处理那些求所有可行解的问题,而分支 限界法更适于处理那些只确定一个可行解,特别是最优化问题。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法。最常见的有以下两种方式: 1).队列式(FIF0)分支限界法:将活结点表组织成一个队列, 并按队列的先进先出原则选取下一个结点作为当前扩展结点。 2).优先队列式分支限界法:将活结点表组织成一个优先队列, 并按优先队列给结点规定的优先级选取优先级最高的下一个结点作
第八章 分支限界法 §1 算法基本思想 本章叙述中为了区别图中的顶点和解空间树中的顶点，凡是在解 空间树中出线队顶点一律称为结点。 分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解 或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝纵深 方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到 问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上 最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支 定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个 特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子结点, 将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结 点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重 复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜 索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支 限界法更适于处理那些只确定一个可行解，特别是最优化问题。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限 界法。最常见的有以下两种方式： 1).队列式（FIFO）分支限界法：将活结点表组织成一个队列， 并按队列的先进先出原则选取下一个结点作为当前扩展结点。 2).优先队列式分支限界法： 将活结点表组织成一个优先队列， 并按优先队列给结点规定的优先级选取优先级最高的下一个结点作
为当前扩展结点。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索,不同的是队列式分支限界法不搜索以不可行结点(已经 被判定不能导致可行解或不能导致最优解的结点)为根的子树。这是 因为,按照规则,这样的结点未被列入活结点表。 优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。结点的优先级常用一个与该结点有关的数值p来表 。最大优先队列规定p值较大的结点点的优先级较髙。在算法实现 时通常用一个最大堆来实现最大优先队列,用最大堆的 Deletemax运 算抽取堆中的下一个结点作为当前扩展结点,体现最大效益优先的原 则。类似地,最小优先队列规定p值较小的结点的优先级较高。在算 法实现时,常用一个最小堆来实现,用最小堆的 Deletemin运算抽取 堆中下一个结点作为当前扩展结点,体现最小优先的原则。采用优先 队列式分支定界算法解决具体问题时,应根据问题的特点选用最大优 先或最小优先队列,确定各个结点点的p值。 例1旅行商问题,n=4,其解空间树是一棵排列树。如文档“旅 行商搜索树”。赋权图G给出如下: 30 求赋权图G的 最小权 Hamilton圈 20 采用队列式分支限界法以排列树中的结点B作为初始扩展结点
为当前扩展结点。 队列式分支限界法的搜索解空间树的方式类似于解空间树的宽 度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经 被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是 因为，按照规则，这样的结点未被列入活结点表。 优先队列式分支限界法的搜索方式是根据活结点的优先级确定 下一个扩展结点。结点的优先级常用一个与该结点有关的数值 p 来表 示。最大优先队列规定 p 值较大的结点点的优先级较高。在算法实现 时通常用一个最大堆来实现最大优先队列，用最大堆的 Deletemax 运 算抽取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原 则。类似地，最小优先队列规定 p 值较小的结点的优先级较高。在算 法实现时，常用一个最小堆来实现，用最小堆的 Deletemin 运算抽取 堆中下一个结点作为当前扩展结点，体现最小优先的原则。采用优先 队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优 先或最小优先队列，确定各个结点点的 p 值。 例 1 旅行商问题，n=4，其解空间树是一棵排列树。如文档“旅 行商搜索树”。赋权图 G 给出如下： 30 6 10 求赋权图 G 的 5 4 最小权 Hamilton 圈 20 采用队列式分支限界法以排列树中的结点 B 作为初始扩展结点。 1 4 2 3
此时,活结点队列为空。由于从图G的顶点1到顶点2、3和4均有 边相连,B的儿子C、D和E都是可行结点,它们被依次加入到活结 点队列中,并舍弃当前扩展结点B。当前活结点队列中的队首结点C 成为下一个扩展结点。由于图G的顶点2到顶点3和4有边相连,故 结点C的二个儿子F和G均为可行结点,可以加入活结点队列。接下 来,结点D和结点E相继成为扩展结点。此时活结点队列中的结点依 次为F、G、H、I、J、K。结点F成为下一个扩展结点,但其儿子L 是解空间树的叶结点,我们找到了一条 Hamilton圈(1,2,3,4,1), 其费用为59。下一个扩展结点G的儿子M也是叶结点,得到另一条 Hamilton圈(1,2,4,3,1),其费用为66。结点H成为当前扩展 结点,其儿子N也是叶结点,得到第三条 Hamilton圈,其费用为25, 这是当前知道的最短 Hamilton圈。下一个扩展结点是I,由于从根 结点到结点I的费用26已经超过当前最优值,故没有必要扩展I 以Ⅰ为根的子树被剪掉。最后J和K被依次扩展,活结点队列称为空 集,算法终止。算法搜索到的最优值是25,相应的最优解是从根结 点到结点N的路径(1,3,2,4,1)。 采用优先队列式分支限界法,用一个最小堆存储活结点表,优先 级函数是结点的当前费用。算法还是排列树的结点B和空优先队列开 始。结点B被扩展后,它的3个儿子C、D和E被依次插入堆中。此 时,由于E是堆中具有最小当前费用(为4)的结点,所以处于堆顶 的位置,它自然成为下一个扩展结点。结点E被扩展后,其儿子J和 K被插入当前堆中,它们的费用分别为14和24。此时,堆顶元素是
此时，活结点队列为空。由于从图 G 的顶点 1 到顶点 2、3 和 4 均有 边相连，B 的儿子 C、D 和 E 都是可行结点，它们被依次加入到活结 点队列中，并舍弃当前扩展结点 B。当前活结点队列中的队首结点 C 成为下一个扩展结点。由于图 G 的顶点 2 到顶点 3 和 4 有边相连，故 结点 C 的二个儿子 F 和 G 均为可行结点，可以加入活结点队列。接下 来，结点 D 和结点 E 相继成为扩展结点。此时活结点队列中的结点依 次为 F、G、H、I、J、K。结点 F 成为下一个扩展结点，但其儿子 L 是解空间树的叶结点，我们找到了一条 Hamilton 圈（1，2，3，4，1）， 其费用为 59。下一个扩展结点 G 的儿子 M 也是叶结点，得到另一条 Hamilton 圈（1，2，4，3，1），其费用为 66。结点 H 成为当前扩展 结点，其儿子 N 也是叶结点，得到第三条 Hamilton 圈，其费用为 25， 这是当前知道的最短 Hamilton 圈。下一个扩展结点是 I，由于从根 结点到结点 I 的费用 26 已经超过当前最优值，故没有必要扩展 I， 以 I 为根的子树被剪掉。最后 J 和 K 被依次扩展，活结点队列称为空 集，算法终止。算法搜索到的最优值是 25，相应的最优解是从根结 点到结点 N 的路径（1，3，2，4，1）。 采用优先队列式分支限界法，用一个最小堆存储活结点表，优先 级函数是结点的当前费用。算法还是排列树的结点 B 和空优先队列开 始。结点 B 被扩展后，它的 3 个儿子 C、D 和 E 被依次插入堆中。此 时，由于 E 是堆中具有最小当前费用（为 4）的结点，所以处于堆顶 的位置，它自然成为下一个扩展结点。结点 E 被扩展后，其儿子 J 和 K 被插入当前堆中，它们的费用分别为 14 和 24。此时，堆顶元素是
它成为下一个扩展结点。它的2个儿子H和I被插入堆中。此时 堆中元素是结点C、H、Ⅰ、J、K。在这些结点中,H具有最小费用, 成为下一个扩展结点。扩展结点H后得到一条 Hamilton圈(1,3,2, 4,1),相应的费用为25。接下来,结点J成为扩展结点,并由此得 到一条 Hamilton圈(1,4,2,3,1),费用仍为25。此后的两个扩 展结点是K和I。由结点K得到的 Hamilton圈的费用高于当前所知 最小费用,结点Ⅰ当前的费用已经高于当前所知最小费用,因而,它 们都不能得到最优解。最后,优先队列为空,算法终止。 §2优先级的确定与LC-检索 对于优先队列式分支限界法,结点优先级的确定直接影响着算法 性能。我们当然希望这样的活结点X成为当前扩展结点 1).以X为根的子树中含有问题的答案结点 2).在所有满足条件1)的活结点中,X距离答案结点“最近”。 但是,要给出可能导致答案结点的活结点附以优先级,必须要附加若 干计算工作,即要付出代价。对于任一结点,要付出的代价可以使用 两种标准来度量 (i).在生成一个答案结点之前,子树X需要生成的结点数; (ii).在子树X中离X最近的那个答案结点到X的路径长度 容易看出,如果使用度量(ⅱ),在对于每一种分枝限界算法,总是生 成最小数目的结点;如果采用度量(ii),则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结点。用c(·)表示一个 理想的优先级函数,定义如下:
D，它成为下一个扩展结点。它的 2 个儿子 H 和 I 被插入堆中。此时， 堆中元素是结点 C、H、I、J、K。在这些结点中，H 具有最小费用， 成为下一个扩展结点。扩展结点 H 后得到一条 Hamilton 圈（1，3，2， 4，1），相应的费用为 25。接下来，结点 J 成为扩展结点，并由此得 到一条 Hamilton 圈（1，4，2，3，1），费用仍为 25。此后的两个扩 展结点是 K 和 I。由结点 K 得到的 Hamilton 圈的费用高于当前所知 最小费用，结点 I 当前的费用已经高于当前所知最小费用，因而，它 们都不能得到最优解。最后，优先队列为空，算法终止。 §2 优先级的确定与 LC-检索 对于优先队列式分支限界法，结点优先级的确定直接影响着算法 性能。我们当然希望这样的活结点 X 成为当前扩展结点： 1).以 X 为根的子树中含有问题的答案结点； 2).在所有满足条件 1)的活结点中，X 距离答案结点“最近”。 但是，要给出可能导致答案结点的活结点附以优先级，必须要附加若 干计算工作，即要付出代价。对于任一结点，要付出的代价可以使用 两种标准来度量： (i).在生成一个答案结点之前，子树 X 需要生成的结点数； (ii).在子树 X 中离 X 最近的那个答案结点到 X 的路径长度。 容易看出，如果使用度量(i)，在对于每一种分枝限界算法，总是生 成最小数目的结点；如果采用度量(ii),则要成为扩展结点的结点只 是由根到最近的那个答案结点路径上的那些结点。用 c(·)表示一个 理想的优先级函数，定义如下：
a).如果X是答案结点,则c(X)是解空间树中,由根结点到X的 成本(即所用的代价,如级数、计算复杂度等); b).如果X不是答案结点,而且以X为根的子树中不含答案结点 则c(X)定义为∞; c).如果X不是答案结点,但是以X为根的子树中含答案结点,则 c(X)是具有最小成本的答案结点的成本。 如果能够获得这样的优先级函数,则优先队列式分支限界法将以 最少的搜索时间找到问题的解。然而,这样的优先级函数的计算工作 量不亚于解原问题。实际问题中都是采用一个估计函数e,它由两部 分决定:解空间树的根结点到Ⅹ的成本f(X)和X到答案结点的估计 成本g(X),即(X)=f(X)+g(X).称为成本估计函数。根据成本估 计函数选择下一个扩展结点的策略总是选取(·)值最小的活结点作 为下一个扩展结点。这种搜索策略称为最小成本检索( Least cost search),简称LC-检索。如果取g=0,f(X)等于X在解空间树中的级, 则LC-检索即是宽度优先搜索(BFS);如果f=0,且g满足: Y是X的儿子→g(Y≤g(X (8.2.1) 则LC-检索即是深度优先搜索(ODFS).在以后所提到的成本函数ε中, 函数g都满足(8.2.1)式。 例子15迷问题 在一个分成4×4的棋盘上排列15块号牌,如图(a)。其中会出 现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、 右的一块号牌移入空格。要求通过一系列合法移动,将号牌的初始排
a).如果 X 是答案结点，则 c(X)是解空间树中，由根结点到 X 的 成本(即所用的代价，如级数、计算复杂度等)； b).如果 X 不是答案结点，而且以 X 为根的子树中不含答案结点， 则 c(X)定义为∞； c).如果 X 不是答案结点，但是以 X 为根的子树中含答案结点，则 c(X)是具有最小成本的答案结点的成本。 如果能够获得这样的优先级函数，则优先队列式分支限界法将以 最少的搜索时间找到问题的解。然而，这样的优先级函数的计算工作 量不亚于解原问题。实际问题中都是采用一个估计函数 ĉ，它由两部 分决定：解空间树的根结点到 X 的成本 f(X)和 X 到答案结点的估计 成本 g(X)，即 ĉ(X)= f(X)+g(X). ĉ 称为成本估计函数。根据成本估 计函数选择下一个扩展结点的策略总是选取 ĉ(·)值最小的活结点作 为下一个扩展结点。这种搜索策略称为最小成本检索（Least Cost search），简称 LC-检索。如果取 g=0,f(X)等于 X 在解空间树中的级， 则 LC-检索即是宽度优先搜索(BFS)；如果 f=0，且 g 满足： Y 是 X 的儿子 ⇒ g(Y)≤ g(X) (8.2.1) 则 LC-检索即是深度优先搜索(DFS).在以后所提到的成本函数 ĉ 中， 函数 g 都满足(8.2.1)式。 例子 15 迷问题 在一个分成 4×4 的棋盘上排列 15 块号牌，如图(a)。其中会出 现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、 右的一块号牌移入空格。要求通过一系列合法移动，将号牌的初始排