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

Question

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

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

Justin Heyes-Jones网页 - A*算法非常清楚地解释了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)为tile的当前平方数x.因此,例如,如果图块A是方形编号3,那么N(A) = 3.请注意,"tile"可以位于这些方块中的任何一个中,并且每个方块的数量保持不变(因此左上方的方格将始终为数字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指的是方块上的tile (N(x) + 1) % 8,即边缘的下一个方块
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.