Nパズル問題を解くアルゴリズムを実装しています。このアルゴリズムは、A* や Heuristic Bidirectional Search などの他のアルゴリズムを使用します。一般に、この両方のアルゴリズムは良い結果をもたらします。A* は 50 回を超える手数の問題の解決策を見つけるのに役立ち、他のより大きな解決策にはもう一方を使用します。
問題は次のとおりです。両方のアルゴリズムのヒューリスティックとしてマンハッタン距離を使用しており、ボードに繰り返しタイルがない場合は完全に機能するようです。たとえば、3x3 の場合、古典的な 8 パズルのスタート ボードは 1,2,3|4,5,6|7,8,0 となり、リピート タイルは 1,1,1|2,3,2|1 となります。 ,1,0. しかし、この場合 (ボードがタイルを繰り返した場合)、これらのアルゴリズムは機能しますが、同じではなく、さらに時間がかかり、より大きなソリューションが得られます。私はヒューリスティック関数を修正し、各タイルが元の位置への最短経路を取るようになりました。
質問: これらの問題に対するより良いヒューリスティックを知っている人はいますか? この Manhattan Distance Heuristic は、繰り返し要素の問題に対してまだ許容できますか? これはN-Puzzleとは別の問題ですか？
ありがとう...