java - マンハッタン距離ヒューリスティックを使用したスライディング パズル ソルバー

Question

私の友人と私はスライディング パズル プログラムを作成しました。そして、マンハッタン距離のメソッドを作成し、移動ごとに MD 結果を表示します。次の移動に最適なタイルは、MD の結果が最も少ないタイルであると最初に考えました。そして問題は、少なくとも 2 つの方向 (左、右、上、下) で同じマンハッタン距離が得られることがあるということです。したがって、最良の動きを選択するには、他の条件とアルゴリズムが必要だと考えています。そのため、どの要件が必要で、プログラムの何が問題なのかをお知らせください。

Answer 1

タイルではなく状態を考慮する必要があります。1 つのタイルだけでなく、州のすべての MD を考慮する必要があります。その場合、同じ MD 合計を持つ 2 つの状態がある場合、FIFO アプローチを使用できますが、ループを回避するために訪問済みの状態を探す必要があります。