4

我正在学习关于 8 谜题的 A* 算法。

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

Justin Heyes-Jones 网页 - A* 算法非常清楚地解释了 A*。它有一张 Nilsson 序列分数的图片。

Nilsson 的序列分数

它解释说：

Nilsson 的序列得分

中间的牌得分1（因为它应该是空的）

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

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

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

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

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

所以，按照描述， B是在中心，所以我们有一个分数1。

然后

对于不在中心的每个标题，如果顺时针方向的图块不是顺时针方向的图块，则得分2。

我不确定这句话是什么意思。加粗的瓷砖指的是什么？加粗的表示什么？加粗的是否指的是中心标题（本例中为 B）？还是它指的是不在中心的每个图块？

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

4

1 回答 1

5

Let us number the squares as follows:

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

Now, let N(x) be the current square number for tile x. So, for example, if a tile A is in the square number 3, then N(A) = 3. Note that a "tile" can be in any of these squares and the number of each square remains the same (so the upper left square will always be the number 0).

The sequence score is given by:

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

where next(x) takes x to the next letter, i.e. next(A) = B, next(B) = C, ... , next(G) = H, next(H) = A.

So to answer your specific questions:

  1. tile refers to the tile on square (N(x) + 1) % 8, i.e. the next square round the edge
  2. it refers to the tile in "for each tile not in the center"
  3. The next step is given by looking at A. C should not be clockwise to A, then we have 2. Next we look at C, D should be clockwise to A, so this is okay. Looking at D, E, F and G all of these are okay, but when we get to H it should not be next to 0, so we have a score of 4. We add 1 because B is in the center to get 5. Then multiply by 3 to get 15. Then add 1 to move B up to the right place, and 1 to move A left to the right place for a final total of 17.
于 2012-05-15T19:00:47.593 回答