私は、タイルに数字がないスライド タイル パズルの一般化されたバージョンに取り組んできました。代わりに、各場所にはタイルまたは穴があり、ブール値で true または false (タイルまたは穴) として表されます。
検索のポイントは、n タイルの初期状態と n ターゲット位置の目標状態を取得し、A* を使用してタイルを移動する方法の解を見つけ、すべてのターゲット位置にデータが取り込まれるようにすることです。以下は、4x3 グリッドの例です。
Initial State:
T F T F
F F T F
F F T T
Goal State
T T T T
T F F F
F F F F
私はこれを行うためにさまざまなヒューリスティックに取り組んできましたが、最も成功したのは次のようなロジックでした。
int heuristicVal = 0
for every tile (i)...
int closest = infinity
for every goal location (j)...
if (manhattan distance of ij < closest) closest = manhattan distance of ij
end for
heuristicVal += closest
end for
return heuristicVal
残念ながら、2 つ以上のタイルがヒューリスティックによって同じターゲット位置に誘導されている状況では、これでも遅すぎました。タイルの数を掛けheuristicValてみたところ、突然指数関数的にスピードアップしました。以前は 28 秒かかっていた問題が、1 秒未満で済みました。
編集：この変更により、結局、常に最適なソリューションが生成されるとは限らないことが判明しました。ただし、なぜそれほど高速化されたのか、または許容されなくなったにもかかわらず、なぜまだ正しい (次善の) 答えが見つかっているのか、私にはわかりません。