我正在学习8数码问题的A*算法。
我对A*算法没有疑问，但对启发式分数——Nilsson的序列分数有些疑问。
Justin Heyes-Jones的网页 – A*算法对A*算法的解释非常清楚。其中有一张关于Nilsson序列分数的图片。
它解释道：
Nilsson的序列分数
中心位置的方块得分
1（因为它应该是空的）对于不在中心的每个方块，如果顺时针方向的下一个方块不是它应该顺时针方向的方块，则得分
2。将这个序列乘以三，最后加上将每个方块移动回正确位置所需的总距离。
我无法理解上述计算分数的步骤。
例如，对于初始状态，h = 17是什么意思？
+---+---+---+| | A | C |+---+---+---+| H | B | D |+---+---+---+| G | F | E |+---+---+---+所以，按照描述，B在中心位置，我们得分1。
然后
对于不在中心的每个方块，如果顺时针方向的下一个方块不是它应该顺时针方向的方块，则得分
2。
我不确定这句话是什么意思。加粗的方块指的是什么？加粗的它指的是什么？加粗的它是指中心方块（在这个例子中是B）吗？还是指每个不在中心的方块？
下一步是否从A开始，所以C不应该顺时针紧邻A，然后我们得分2。然后B应该顺时针紧邻A，那么我们忽略，依此类推？
回答：
让我们按以下方式编号方块：
+---+---+---+| 0 | 1 | 2 |+---+---+---+| 7 | 8 | 3 |+---+---+---+| 6 | 5 | 4 |+---+---+---+现在，让N(x)表示方块x当前所在的方块编号。所以，例如，如果方块A在编号为3的方块中，那么N(A) = 3。请注意，一个“方块”可以位于这些方块中的任何一个，方块的编号保持不变（所以左上角的方块总是编号0）。
序列分数的计算如下：
对于每个方块 x 在 (A, B, C, ..., H) 中 分数 += 从 N(x) 到方块 x 正确位置的距离 如果 N(x) == 8 # 即方块在中心 分数 += 3*1 否则如果 N(next(x)) != (N(x) + 1) % 8 分数 += 3*2其中next(x)将x转换为下一个字母，即next(A) = B, next(B) = C, ... , next(G) = H, next(H) = A。
所以，回答你的具体问题：
- 方块指的是位于方块
(N(x) + 1) % 8上的方块，即沿着边缘的下一个方块 - 它指的是“对于不在中心的每个方块”中的方块
- 下一步是查看
A。C不应该顺时针紧邻A，那么我们得分2。接下来查看C，D应该顺时针紧邻C，所以这是可以的。查看D, E, F和G，这些都是可以的，但当我们查看H时，它不应该紧邻0，所以我们得分4。因为B在中心，我们加1得到5。然后乘以3得到15。然后加上1来将B向上移动到正确位置，再加上1来将A向左移动到正确位置，最终总分为17。
