Twiddle と呼ばれる小さなパズル ゲームの最適な解決策を見つけようとしています (ゲームのアプレットはここにあります)。このゲームには、1 から 9 までの数字の 3x3 マトリックスがあります。目標は、最小限の移動で数字を正しい順序に並べることです。一手ごとに、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 が 0 であるが、状態が完全に順序付けられていない場合、h = 1 よりも。
しかし、一度に 4 つの要素を回転させるという問題があります。そのため、これらの推定回転を 1 回の移動で 2 つ (またはそれ以上) 実行できるまれなケースがあります。これは、これらのヒューリスティックが解までの距離を過大評価していることを意味します。
私の現在の回避策は、少なくとも私のテストケースでは、この問題を解決する計算からコーナーの 1 つを単純に除外することです。本当に問題が解決するかどうか、またはこのヒューリスティックがいくつかのエッジケースでまだ過大評価されているかどうかは調査していません。
だから私の質問は、あなたが思いつくことができる最高のヒューリスティックは何ですか?
（免責事項：これは大学のプロジェクトのためのものなので、これはちょっとした宿題です。しかし、私は思いついたリソースを自由に使用できるので、皆さんに聞いても大丈夫です。また、私を助けてくれた Stackoverflow の功績を認めます。 ) )