*検索のための優れたヒューリスティックを見つける

Question

Twiddleと呼ばれる小さなパズルゲームの最適なソリューションを見つけようとしています（ゲームを持つアプレットが見つかります ここ）。ゲームには3x3マトリックスがあり、数値は1から9です。目標は、最小の動きを使用して数値を正しい順序で提供することです。各移動では、時計回りまたは反時計回りのいずれかで2x2平方を回転させることができます。

つまり、この状態がある場合

6 3 9
8 7 5
1 2 4

そして、あなたはあなたが取得する左上2x2平方に時計回りに回転します

8 6 9
7 3 5
1 2 4

A*検索を使用して最適なソリューションを見つけています。私のf（）は、単に必要な回転数です。私のヒューリスティック機能はすでに最適なソリューションにつながります（私がそれを変更する場合は、最後に通知を参照してください）が、それがあなたが見つけることができる最高のものではないと思います。私の現在のヒューリスティックは各コーナーを取り、コーナーの数を見て、この数値が解決された状態（この位置に数をもたらすために必要な回転数が与えられます）にある位置までのマンハッテン距離を計算し、すべてを合計しますこれらの値。つまり、上記の例を挙げます：

6 3 9
8 7 5
1 2 4

そして、この終わりの状態

1 2 3
4 5 6
7 8 9 

次に、ヒューリスティックが次のことを行います

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

さらに、Hの場合、H = 1よりも状態が完全に順序付けられていない場合。

しかし、4つの要素を一度に回転させるという問題があります。したがって、1つの動きで2つの（より多くの鉱石）の推定回転を行うことができるまれなケースがあります。これは、これらのヒューリスティックがソリューションまでの距離を過大評価することを意味します。

私の現在の回避策は、少なくとも私のテストケースでこの問題を解決する計算からコーナーの1つを単純に除外することです。私は研究をしていません 本当 問題を解決するか、このヒューリスティックがいくつかのエッジケースでまだ過大評価されている場合。

だから私の質問は次のとおりです。 あなたが思いつくことができる最高のヒューリスティックは何ですか？

（免責事項：これは大学のプロジェクトのためのものなので、これは少し宿題です。しかし、私はあなたに尋ねても大丈夫です。 ）））

Answer 1

多くの場合、シンプルさが最も効果的です。単一の整数を形成すると9桁（行目に順序で）を考慮してください。解は、可能な限り少ない整数I（g）= 123456789で表されます。例として、H（s）= 639875124-123456789。

Answer 2

コーナー要素だけでなく、距離を計算するときは、すべての要素を考慮する必要があります。すべての角の要素1、3、7、9が自宅にあると想像してください。しかし、他のすべてはそうではありません。

最終状態の隣人であるこれらの要素は、各ステップ中に近づく傾向があるべきだと主張することができます。したがって、隣接する距離はヒューリスティックの一部である可能性がありますが、おそらく最終状態までの要素の距離よりも影響が弱いでしょう。

Answer 3

すべての数値を考慮に入れて4で割って次の整数に切り上げることにより、アプローチから強引に（つまり、過大評価ではなく）ヒューリスティックを得ることができます。

ヒューリスティックを改善するために、数字のペアを見ることができます。左上にたとえば、数字1と2が交換されている場合、それらを固定するには少なくとも3回の回転が必要です。これは、個別に考慮して1+1よりも良い値です。最終的には、4で分割する必要があります。数字を任意にペアリングするか、すべてのペアを試して、最適な分割をペアに見つけることさえできます。