8

幅優先探索を使用して 8 パズル ソルバーを作成しました。ここで、ヒューリスティックを使用するようにコードを変更したいと思います。次の2つの質問に答えていただけるとありがたいです。

可解性

8 のパズルが解けるかどうかをどのように判断しますか? （開始状態と目標状態が与えられた場合）これはウィキペディアの言うことです：

不変量は、16 個の正方形すべての順列のパリティに、空の正方形の右下隅からのタクシー距離 (行数と列数) のパリティを加えたものです。

残念ながら、私にはその意味が理解できませんでした。理解するのは少し複雑でした。誰かがそれをもっと簡単な言葉で説明できますか?

最短ソリューション

ヒューリスティックが与えられた場合、A* アルゴリズムを使用して最短の解を与えることが保証されますか? より具体的には、オープン リストの最初のノードには、オープン リストに存在するすべてのノードの深さの最小値である深さ (または非常に太った動きの数) が常にありますか?

ヒューリスティックは、上記のステートメントが真であるために何らかの条件を満たす必要がありますか?

編集:許容可能なヒューリスティックが常に最適なソリューションを提供するのはどうしてですか? そして、ヒューリスティックが許容できるかどうかをどのようにテストするのでしょうか?

ここにリストされているヒューリスティックを使用します

Manhattan Distance 
Linear Conflict 
Pattern Database 
Misplaced Tiles
Nilsson's Sequence Score 
N-MaxSwap X-Y 
Tiles out of row and column

Eyal Schneider からの説明:

ここに画像の説明を入力 ここに画像の説明を入力 ここに画像の説明を入力

4

3 に答える 3

6

解決可能性の問題についてのみ言及します。順列の背景が必要です。

順列は、順序付けられたセットの並べ替えです。たとえば、2134 はリスト 1234 の並べ替えであり、1 と 2 の場所が入れ替わっています。順列にはパリティ プロパティがあります。反転数のパリティを指します。たとえば、次の順列では、正確に 3 つの反転が存在することがわかります (23、24、34)。

1234
1432

これは、順列のパリティが奇数であることを意味します。次の順列には偶数パリティ (12, 34) があります。

1234
2143

当然、恒等順列 (アイテムの順序を維持する) には偶数パリティがあります。

15 パズル (または 8 パズル) の任意の状態は、最初の行から始まる行の連結として見ると、最終状態の順列と見なすことができます。すべての正当な動きは、順列のパリティを変更することに注意してください (2 つの要素を交換し、それらの間の項目を含む反転の数が偶数でなければならないため)。したがって、空の正方形が最終的な状態に到達するために偶数のステップを移動する必要があることがわかっている場合、順列も偶数でなければなりません。そうしないと、最終状態の奇数順列で終了し、必然的にそれとは異なります。空の正方形のステップ数が奇数の場合も同様です。

あなたが提供したウィキペディアのリンクによると、上記の基準は、特定のパズルが解決可能であるために十分かつ必要です.

于 2013-02-17T12:00:15.450 に答える
3

A* アルゴリズムは、ヒューリスティックが常に実際のコストを過小評価する場合 (この場合、ソリューションに必要な移動の実際の数)、最短のソリューション (等しい短いものが複数ある場合は 1 つ)を見つけることが保証されます。

しかし、その場で私はあなたの問題に対する良いヒューリスティックを思いつくことができません. そのようなヒューリスティックを見つけるには、少し考える必要があります。

A* を使用する真の技術は、実際のコストを常に過小評価するヒューリスティックを見つけることですが、検索を高速化するために可能な限り少なくすることです。

このようなヒューリスティックの最初のアイデア:

  1. 私の頭に浮かんだかなり退屈だが有効なヒューリスティックは、空のフィールドから最終目的地までのマンハッタン距離です。
  2. 各フィールドから最終目的地までのマンハッタン距離の合計を、1 回の移動で位置を変更できるフィールドの最大数で割った値。(これは非常に優れたヒューリスティックだと思います)
于 2013-02-17T11:32:33.930 に答える
0

来た人のために、OPが値のペアを取得した方法と、強調表示されたもの、つまり反転を理解するのに数時間かかった方法を彼が決定する方法を説明しようとします。まずはペア。最初に目標状態を取り、それを 1D 配列 (たとえば A) [1,2,3,8,0,4,7,5] として想像します。その配列の各値には、テーブル内の独自の列があります（ペアの最初の値である下に移動します）。次に、配列（i + 1）の右に1つの値を移動し、最後まで移動します再びダウン、2 番目のペアの値。例 (状態 A): 最初の列、2 番目の値は [2,3,8,0,4,7,5] が下がり始めます。2 列目は [3,8,0,4,7,5] などで始まります。

反転については大丈夫です。2 組の値のそれぞれについて、開始状態でのINDEXの場所を見つけます。左のINDEX > 右のINDEXの場合、反転 (強調表示) されます。状態 A の最初の 4 つのペアは次のとおりです。(1,2)、(1,3)、(1,8)、(1,0)
1 はインデックス 3
2 はインデックス 0
3 > 0 なので反転。

1 は 3
3 は 2
3 > 2 なので反転

1 は 3
8 は 1
3 > 2 なので反転

1 は 3
0 は 7
3 < 7 なので反転なし

各ペアに対してこれを行い、合計反転を集計します。偶数または奇数 (空白スポットのマンハッタン距離と全反転) の場合、それは解決可能です。お役に立てれば！

于 2017-01-02T17:12:07.077 に答える