4

私は8パズルの問題でA*アルゴリズムを学んでいます。

A *については質問はありませんが、ヒューリスティックスコア（ニルソンのシーケンススコア）について質問があります。

JustinHeyes-JonesのWebページ-A*アルゴリズムはA*を非常に明確に説明しています。ニルソンのシーケンススコアの写真があります。

ニルソンのシーケンススコア

それは説明します：

ニルソンのシーケンススコア

中央のタイルのスコア1（空である必要があるため）

中央にないタイルごとに、時計回りのタイルが時計回りのタイルではない場合は、スコアを付け2ます。

このシーケンスに3を掛け、最後に各タイルを正しい位置に戻すために必要な合計距離を追加します。

上記のスコア計算の手順がわかりません。

たとえば、開始状態の場合、何h = 17ですか？

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

したがって、説明に従うと、 Bが中央にあるので、スコアは。になり1ます。

それで

中央にない各タイトルについて、時計回りのタイルが時計回りのタイルではない場合は、スコアを付け2ます。

この声明が何を意味するのかわかりません。太字のタイルは何を指しますか？太字は何を指しますか？太字は中央のタイトル（この例ではB）を示していますか？それとも、中央にない各タイルを指しますか？

から開始する次のステップなAので、C時計回りににしないでください。Aスコアは。になり2ます。そして、B時計回りに時計回りに回す必要がありますA。無視します。

4

1 に答える 1

5

次のように正方形に番号を付けましょう。

+---+---+---+
| 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)ます。つまり、 。xnext(A) = B, next(B) = C, ... , next(G) = H, next(H) = A

だからあなたの特定の質問に答えるために：

  1. タイルとは、正方形のタイル(N(x) + 1) % 8、つまりエッジの周りの次の正方形を指します
  2. 「中央にないタイルごとに」のタイルを指します
  3. 次のステップは、を見て与えられAます。 C時計回りにすべきではありません。そうすればA、が得られ2ます。次に、を見てみましょCう。D時計回りにする必要があるAので、これで問題ありません。見てみるD, E, FとG、これらはすべて問題ありませんが、到達したときHに0の隣にあるべきではないため、スコアは。になり4ます。Bを取得するために中央にあるため、1を追加します5。次に、を掛けて3を取得します15。次に、を追加1しBて適切な場所に1移動し、左に移動Aして最終的な合計を17。
于 2012-05-15T19:00:47.593 に答える