第八章分支限界法 §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)。其中会出 现一个空格。棋盘上号牌的一次合法移动是指将位于空格上、下、左、 右的一块号牌移入空格。要求通过一系列合法移动，将号牌的初始排
列转换成自然排列,如图(b) 234 2 5678 61114 [891d13 131415 图(a) 图(b) 图(c 如果将棋盘的各个位置按照号牌的自然排列发给序号,右下角发 给16号。则号牌的每一种排列都可以看作是0,1,…,15这16个 数的排列,其中,0的位置代表空格。如图(a)对应的排列是 (1,3,4,15,2,0,5,12,7,6,11,14,8,9,10,13).事实上,不是号牌的每 种排列都能够经过一系列合法移动转换成自然排列的。用Less(i) 记排列P中位于i后面且号比i小的号牌数,则排列P可以经一系列 合法移动转换成自然排列的充要条件是 ∑LesS(+X是偶数 (8.2.2) l≤i<15 其中,当空格在图(c)的某个#位置时,X=1;否则X=0.以后记 r(P)=∑Les(),称为排列P的逆序数。例如,图(a)中排列的逆序 1≤i≤15 数为16,X=0,所以图(a)中排列可经一系列合法移动转换成自然排列。 在处理实际问题中,一般是根据具体问题的特性,确定成本估 计函数C(X)=f(X)+g(X)中的函数f(X)和g(X).在本例中,我们令f(x) 是由根到结点X的路径的长度,g(X)是以X为根的子树中,由X到目 标状态(自然排列)的一条最短路径长度的估计值。为此,g(X)至少应 是把状态X转换成目标状态所需的最小移动数。对它的一种可能的选 择是
列转换成自然排列，如图(b). 1 3 4 15 1 2 3 4 ＃ ＃ 2 5 12 5 6 7 8 ＃ ＃ 7 6 11 14 9 10 11 12 ＃ ＃ 8 9 10 13 13 14 15 ＃ ＃ 图 (a) 图 (b) 图 (c) 如果将棋盘的各个位置按照号牌的自然排列发给序号，右下角发 给 16 号。则号牌的每一种排列都可以看作是 0，1，…，15 这 16 个 数的排列，其中， 0 的位置代表空格。如图 (a)对应的排列是 (1,3,4,15,2,0,5,12,7,6,11,14,8,9,10,13).事实上，不是号牌的每 一种排列都能够经过一系列合法移动转换成自然排列的。用 Less(i) 记排列 P 中位于 i 后面且号比 i 小的号牌数，则排列 P 可以经一系列 合法移动转换成自然排列的充要条件是 ∑ ≤ ≤ + 1 15 ( ) i Less i X 是偶数 （8.2.2） 其中，当空格在图(c)的某个＃位置时，X=1; 否则 X=0.以后记 ∑ ≤ ≤ = 1 15 ( ) ( ) i τ P Less i ,称为排列 P 的逆序数。例如，图(a)中排列的逆序 数为 16，X=0,所以图(a)中排列可经一系列合法移动转换成自然排列。 在处理实际问题中，一般是根据具体问题的特性，确定成本估 计函数 ĉ(X)= f(X)+g(X)中的函数 f(X)和 g(X).在本例中，我们令 f(x) 是由根到结点 X 的路径的长度，g(X)是以 X 为根的子树中，由 X 到目 标状态(自然排列)的一条最短路径长度的估计值。为此，g(X)至少应 是把状态 X 转换成目标状态所需的最小移动数。对它的一种可能的选 择是
g(X)=排列X的不在自然位置的牌的数目(8.2.3) 图(a)的排列中,不在自然位置的牌号分别是:3,4,15,2,5,12 7,6,14,8,9,10,13,共13个。g(X)=13.将图(a)中的排列转换 成自然排列至少需要13次合法的移动。可见,估价函数e(X)是函数 c(X)的下界。按照这样成本估价函数,则15迷问题解空间树的搜索 过程可以从文档“15迷空间树”的图(1)中看出。 首先以结点1作为扩展结点,生成4个儿子:2,3,4,5后死 去。这4个儿子的成本估值分别为:c(2)=1+4;c(3)=1+4;(4)=1+2 e(5)=1+4.因而结点4成为当前扩展结点,生成4个儿子,但有一个 儿子同其祖父相同被舍弃。剩下的3个儿子的成本估值分别为 e(10)=2+1;e(11)=2+3;c(12)=2+3,此时,活结点表中共有6个结 点:2,3,5,10,11,12,其中结点10的成本估值最小。故以结点 10作为新的扩展结点。它能生成3个儿子,其中有一个因同其祖父 相同而被舍弃。剩下的2个儿子是结点22和23。但结点23所表示 的号牌排列是自然的,至此得到可行解。 如果采用队列式分枝限界法,即采用宽度优先搜索,势必将图 (1)中的所有状态全部搜索。如果采用深度优先搜索,则图(2)中也只 给出了一部分搜索步骤,而且结点12表示的号牌排列与自然排列还 相距甚远。由此看出选择合适的优先级函数对于分枝限界法效率的影 响甚大。 值得注意的是按照成本估价函数ε(X确定的优先级进行搜索, 所得到的答案结点未必是最小成本答案结点。例如,下面的解空间树
g(X)= 排列 X 的不在自然位置的牌的数目 (8.2.3) 图(a)的排列中，不在自然位置的牌号分别是：3，4，15，2，5，12， 7，6，14，8，9，10，13，共 13 个。g(X)=13.将图(a)中的排列转换 成自然排列至少需要 13 次合法的移动。可见，估价函数 ĉ(X)是函数 c(X)的下界。按照这样成本估价函数，则 15 迷问题解空间树的搜索 过程可以从文档“15 迷空间树”的图(1)中看出。 首先以结点 1 作为扩展结点，生成 4 个儿子：2，3，4，5 后死 去。这 4 个儿子的成本估值分别为：ĉ(2)=1+4; ĉ(3)=1+4; ĉ(4)=1+2; ĉ(5)=1+4.因而结点 4 成为当前扩展结点，生成 4 个儿子，但有一个 儿子同其祖父相同被舍弃。剩下的 3 个儿子的成本估值分别为 ĉ(10)=2+1；ĉ(11)=2+3；ĉ(12)=2+3，此时，活结点表中共有 6 个结 点：2，3，5，10，11，12，其中结点 10 的成本估值最小。故以结点 10 作为新的扩展结点。它能生成 3 个儿子，其中有一个因同其祖父 相同而被舍弃。剩下的 2 个儿子是结点 22 和 23。但结点 23 所表示 的号牌排列是自然的，至此得到可行解。 如果采用队列式分枝限界法，即采用宽度优先搜索，势必将图 (1)中的所有状态全部搜索。如果采用深度优先搜索，则图(2)中也只 给出了一部分搜索步骤，而且结点 12 表示的号牌排列与自然排列还 相距甚远。由此看出选择合适的优先级函数对于分枝限界法效率的影 响甚大。 值得注意的是按照成本估价函数 ĉ(X)确定的优先级进行搜索， 所得到的答案结点未必是最小成本答案结点。例如，下面的解空间树
中,每个结点X旁有两个数:上面的是最下成本c(X),下面的是成本 估价ε(X)。整个解空间树中有两个答案结点。如果按照估价函数进 行搜索,根结点1首先成为扩展结点,然后是结点2,在扩展结点2 时,得到一个答案结点4,它时结点2的一个儿子。这个答案结点的 成本是20,比另一个答案结点6的成本大 10 10 定理8.1在有限的解空间树中,如果对每对结点X和Y,成本函 数c与成本估价函数e均满足:“c(X)<c(Y”=〉“e(X)<e(Y 则按照成本估价函数搜索能够达到最小成本答案结点。 般情况下,不易找到定理8.1中要求的成本估价函数。对于成 本估价函数,一般有一个基本要求 e(X)≤c(X),对任意结点X 8.2.4) e(X)=c(X),当X是答案结点时。 (8.2.5) 在以下给出的算法中,要求搜索一直继续到一个答案结点变成扩 展结点为止 搜索最小成本答案结点LC一检索 Leastcost(T,)//T是问题的解空间树 1E=T;//第一个扩展结点 2置活结点表为空
中，每个结点 X 旁有两个数：上面的是最下成本 c(X),下面的是成本 估价 ĉ(X)。整个解空间树中有两个答案结点。如果按照估价函数进 行搜索，根结点 1 首先成为扩展结点，然后是结点 2，在扩展结点 2 时，得到一个答案结点 4，它时结点 2 的一个儿子。这个答案结点的 成本是 20，比另一个答案结点 6 的成本大。 10 0 20 10 2 4 20 ∞ ∞ 10 20 ∞ ∞ 10 定理 8.1 在有限的解空间树中，如果对每对结点 X 和 Y，成本函 数 c 与成本估价函数 ĉ 均满足：“c(X) “ĉ(X) < ĉ(Y)” , 则按照成本估价函数搜索能够达到最小成本答案结点。 一般情况下，不易找到定理 8.1 中要求的成本估价函数。对于成 本估价函数，一般有一个基本要求： ĉ(X)≤ c(X), 对任意结点 X； (8.2.4) ĉ(X)＝c(X)，当 X 是答案结点时。 (8.2.5) 在以下给出的算法中，要求搜索一直继续到一个答案结点变成扩 展结点为止。 搜索最小成本答案结点 LC－检索 LeastCost(T, ĉ)//T 是问题的解空间树 1 E=T; //第一个扩展结点 2 置活结点表为空; 1 2 3 4 5 6 7
3 loop ifE是答案结点then 输出从E到T的路径; return 6 endif forE的每个儿子Xdo Add (X): Parent (X=E 9 endfor 10if不再有活结点then print(‘ no answer node’);stop; 12 dif Least(e 14 endloop 15 end Leastcost 其中, Least(X)是从活结点表中找一个具有最小c值的活结点,从活 结点表中删除该结点,再将该结点赋给变量X;Ad(X)是将新的活结 点加到活结点表中。 Parent(X)将活结点X与它的父亲相连接。 在算法 LeastCost中,由于答案结点E是扩展结点,所以,对于 活结点表中的每个结点L均有C(E)≤c(L).再由假设e(E)=c(E),e(L) ≤c(L),得c(E)≤c①L),即E是一个最小成本答案结点。 综上所述,采用优先队列式分枝限界法,其搜索解空间树的算法 主要决定于三个因素:约束函数、限界函数和优先级函数。前两项主 要是限制被搜索的结点数量,而优先级函数则是用来确定搜索的次
3 loop 4 if E 是答案结点 then 5 输出从 E 到 T 的路径；return； 6 endif 7 for E 的每个儿子 X do 8 Add(X); Parent(X)=E; 9 endfor 10 if 不再有活结点 then 11 print(‘no answer node’); stop; 12 endif 13 Least(E); 14 endloop 15 end LeastCost 其中，Least(X)是从活结点表中找一个具有最小 ĉ 值的活结点，从活 结点表中删除该结点，再将该结点赋给变量 X；Add(X)是将新的活结 点加到活结点表中。Parent(X)将活结点 X 与它的父亲相连接。 在算法 LeastCost 中，由于答案结点 E 是扩展结点，所以，对于 活结点表中的每个结点 L 均有 ĉ(E)≤ ĉ(L).再由假设 ĉ(E)=c(E)，ĉ(L) ≤ c(L)，得 c(E)≤ c(L)，即 E 是一个最小成本答案结点。 综上所述，采用优先队列式分枝限界法，其搜索解空间树的算法 主要决定于三个因素：约束函数、限界函数和优先级函数。前两项主 要是限制被搜索的结点数量，而优先级函数则是用来确定搜索的次
序。但是,在处理实际问题中,未必把这三种函数全部列出来,特别 是优先级函数往往同限界函数合为一体。以下给出处理极小化最优问 题的优先队列式分枝限界法的一般流程。 找最小成本结点的LC-分枝限界算法 LCBB(T,e,u,ε,cost)//假定解空间树T包含一个解结点且c(X)≤ //c(X)≤u(X)。c(X)是最小成本函数,c(X是成本估价函数, //u(X)是限界函数;当X是答案结点时,cost(X)是X所对应的解 //的成本。E是一个充分小的正数 1 E=T: Parent(E=0 2ifT是解结点 then u=min(cost(T),u(T)ε);ans=T; 3 else U=u(t)+a, ans=0 4 endif 5将活结点表初始化为空集 loop 7forE的每个儿子Xdo ifc(X)<U&&X是一个可行结点then Add(X): Parent(X)=E 10 case :X是解结点&&cost(X)<U 12 U=min (cost(X), u(X)+e) ans=X 13 u(X)+e<U: U=u(X)+a
序。但是，在处理实际问题中，未必把这三种函数全部列出来，特别 是优先级函数往往同限界函数合为一体。以下给出处理极小化最优问 题的优先队列式分枝限界法的一般流程。 找最小成本结点的 LC-分枝限界算法 LCBB(T, ĉ,u, ε,cost) //假定解空间树 T 包含一个解结点且 ĉ(X) ≤ //c(X) ≤ u(X)。c(X)是最小成本函数，ĉ(X)是成本估价函数， //u(X)是限界函数;当 X 是答案结点时，cost(X)是 X 所对应的解 //的成本。ε 是一个充分小的正数。 1 E＝T; Parent(E)=0; 2 if T 是解结点 then U=min(cost(T),u(T)+ε); ans=T; 3 else U=u(T)+ε; ans=0; 4 endif 5 将活结点表初始化为空集； 6 loop 7 for E 的每个儿子 X do 8 if ĉ(X)<U && X 是一个可行结点 then 9 Add(X); Parent(X)=E; 10 case 11 :X 是解结点 && cost(X)<U: 12 U=min(cost(X),u(X)+ε); ans=X; 13 :u(X)+ε<U: 14 U=u(X)+ε;
