N個のパズルを解くA *ヒューリスティックの比較

Question

私は3種類のヒューリスティック関数を持つA *アルゴリズムを使ってNパズルを解こうとしています。私は時間の複雑さの観点からそれぞれのヒューリスティックをどのように比較するかを知りたい。私が使っている経験則は、マンハッタン距離、マンハッタン距離+線形矛盾、N-maxスワップです。特に、8パズルと15パズルの場合。

Answer 1

Nパズルは、一般的に、最短解を見つけるのに難しいので、あなたがどのヒューリスティックを使用しても、それらの複雑さの違いを見つけることはできません。あらゆる縛りの緊張を証明する。

8パズルまたは15パズルに制限されている場合、任意の許容ヒューリスティックを持つA *アルゴリズムは、ボード位置が有限であるにもかかわらずO（1）時間で実行されます。

Answer 2

@Harold氏は、ヒューリスティック関数の時間的複雑さを比較するアプローチは実験的なテストであると主張しています。あなたのケースでは、8-パズルと15-パズルのランダムな問題nのセットを生成し、異なるヒューリスティック関数を使用してそれらを解きます。注意すべきものがあります：

1. 比較は常にアルゴリズムを実装したときに、...

2. は一般的に、より多くを話すのハードウェアexpecs、プログラミング言語、あなたのスキルのようないくつかの要因に依存するであろう知識のあるヒューリスティックは、あまり知られていないノードよりも少ないノードを常に展開し、おそらくより高速になります。

   1. 問題：

   そして最後に、各問題のセットのための3つのヒューリスティックを比較するために、私は平均実行時間とグラフィックを示唆している（例えば5回それぞれの問題を繰り返します） x軸には難易度が並んでいます。

3. 実行時間は、ヒューリスティック関数ごとに（おそらく対数の差が分かりにくい場合は対数スケールで）y軸になります。

と同様の図で、調査した状態の数を示します。