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

Question

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

我没有关于A *的问题，但有一些关于启发式得分 - 尼尔森的序列得分。

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

它解释说：

尼尔森的序列得分

中心的瓷砖得分1（因为它应该是空的）

对于不在中心的每个瓦片，如果顺时针方向的瓦片不是顺时针方向的瓦片，则得分为2。

将此序列乘以3，最后添加将每个图块移回其正确位置所需的总距离。

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

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

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

因此，按照描述，B位于中心，所以我们得到1的分数。

然后

对于不在中心的每个标题，如果顺时针方向的瓷砖不是顺时针方向的那个，那么得分为2。

我不确定这句话是什么意思。粗体瓷砖是指什么？它所指的粗体是什么？粗体是否指中心标题（本例中为B）？或者它是指不在中心的每个瓷砖？

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

Answer 1

让我们将方块编号如下：

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

现在，让N(x)成为瓦片x的当前平方数。因此，例如，如果瓷砖A在方形数3，那么N(A) = 3。请注意，“平铺”可以位于这些方块中的任何一个中，并且每个方块的数量保持不变（因此左上方的方格将始终为数字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上的tile，即边缘的下一个方块
2. 它指的是“每个瓷砖不在中心”的瓷砖
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的最终总数。