列转换成自然排列,如图(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 转换成目标状态所需的最小移动数。对它的一种可能的选 择是