algorithm - 谁能更清楚地解释 Nilsson 在 8-puzzle 中的序列得分？

Question

我正在学习关于 8 拼图问题的 A* 算法。

我没有关于 A* 的问题，但有一些关于启发式分数的问题 - Nilsson 的序列分数。

Justin Heyes-Jones web pages - A* Algorithm非常清楚地解释了 A*。它有一张 Nilsson 序列分数的图片。

它解释说:

Nilsson 序列评分

A tile in the center scores 1 (since it should be empty)

For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

我无法理解上面计算分数的步骤。

例如，对于起始状态，h = 17是什么？

+---+---+---+
|   | A | C |
+---+---+---+
| H | B | D |
+---+---+---+
| G | F | E |
+---+---+---+

因此，根据描述，B 位于中心，因此我们的得分为 1。

然后

For each title not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

我不确定这句话是什么意思。加粗的 tile 指的是什么？加粗的 it 指的是什么？加粗的 it 是否指的是中心标题(本例中为 B)？或者它指的是不在中心的每个图 block ？

下一步是从A开始，所以C应该不是顺时针到A，那么我们的分数是2。然后B应该顺时针到A，然后我们忽略，依此类推？

Answer 1

让我们按如下方式给方 block 编号:

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 7 | 8 | 3 |
+---+---+---+
| 6 | 5 | 4 |
+---+---+---+

现在，令 N(x) 为方 block x 的当前平方数。因此，例如，如果方 block A 位于正方形数字 3 中，则 N(A) = 3。请注意，“瓷砖”可以位于这些方 block 中的任何一个中，并且每个方 block 的编号保持不变(因此左上角的方 block 将始终为数字 0)。

序列分数由下式给出:

for each tile x in (A, B, C, ..., H)
    score += distance from N(x) to the correct square for tile x
    if N(x) == 8  # i.e. the tile is in the center
       score += 3*1
    else if N(next(x)) != (N(x) + 1) % 8
       score += 3*2

其中 next(x) 将 x 带到下一个字母，即 next(A) = B, next(B) = C, ... , next(G) = H, next(H) = A.

所以回答你的具体问题:

1. tile 指正方形 (N(x) + 1) % 8 上的瓦片，即下一个圆边的正方形
2. 它指的是“for each tile not in the center”中的tile
3. 下一步是查看A。 C不应该顺时针到A，那么我们有2。接下来我们看C，D应该顺时针到A，这样就可以了。看D, E, F 和G 都是没问题的，但是当我们到H 的时候它不应该在0旁边，所以我们的分数是 4。我们加 1，因为 B 位于中心以获得 5。然后乘以 3 得到 15。然后添加 1 将 B 向上移动到正确的位置，添加 1 将 A 向左移动到正确的位置最终总计 17。