これ15 Puzzleは、ヒューリスティックを含むモデリングアルゴリズムの古典的な問題です。この問題で一般的に使用されるヒューリスティックには、置き忘れたタイルの数を数えたり、各ブロック間のマンハッタン距離とゴール構成での位置の合計を見つけたりすることが含まれます。どちらも許容可能であることに注意してください。つまり、残りの移動数を過大評価することはありません。これにより、A*などの特定の検索アルゴリズムの最適性が保証されます。
Heuristicが適切だと思いますかA*、うまくいくようです、あなたは例を持っていますか、多分cまたはでjava？私が選択するヒューリスティックは、順列内のすべての反転の合計が奇数か偶数かを見つけることです。偶数の場合、15パズルは解決可能です。
順列の反転の数は、その逆順列の数と同じです（Skiena 1990、p。29; Knuth1998）。
私がそれを解決できることを知っている場合にのみ、それを解決することは理にかなっています。その場合のタスクは、逆数を減らすことであり、ビオラの問題は解決されました。解決策を見つけるには、80回を超えないようにする必要があります。
順列の方程式は次のとおりです。
0から16の範囲の階乗は、{1、2、6、24、120、720、5040、40320、362880、3628800、39916800、479001600、6227020800、87178291200、1307674368000、20922789888000}です。さらに必要な場合は、WolframAlphaでRange[1,20]を検索してください。
それについてもっと知りたい場合は、15Puzzleを読んでください。
A*algorihtmを使用したC++での15パズルの実装https://gist.github.com/sunloverz/7338003