列转换成自然排列,如图(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) < c(Y)” ＝> “ĉ(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 是一个最小成本答案结点。 综上所述，采用优先队列式分枝限界法，其搜索解空间树的算法 主要决定于三个因素：约束函数、限界函数和优先级函数。前两项主 要是限制被搜索的结点数量，而优先级函数则是用来确定搜索的次