A *

Question

の結果を事前に計算A*検索アルゴリズムについて学習し、N-Puzzleの最速ソリューションを見つけるためにそれを使用しています。初期開始状態のいくつかのランダムシードについて、パズルは解くことができず、アルゴリズムが探索空間全体を探索し、与えられた開始状態に対する解がないと判定するまで、非常に長い待ち時間が生じることがある。

A*アルゴリズムがこのようなシナリオを回避できないかどうかを事前に計算する方法があるかどうかは疑問でした。私はそれが可能である方法について少しは読んだが、それを行う方法に関して直接的な答えを見つけることができない。

いずれかのガイダンスやオプションがありがとうございます。

Answer 1

私はあなたに問題が解決できるかどうかを知るメカニズムを提供していないと思います。具体的にN-Puzzleのために、私は、これはそれを解決できるかどうかをチェックするのに役立つことができると思います：

http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/

あなたが奇数量の反転を持っている状態にある場合、あなたは確かに知っているようですその順列の問題は実行不可能である。

Answer 2

具体的には、Nパズルのパリティは2つしかないので、現在のパズルがどのパリティであるかを確認するだけです。

一般A *問題についてはmath stackexchange

にこれを行う方法に関する詳細な説明があり、なし、グラフが解けるの場合は、計算を事前にする方法はありません。