A *サーチ変形

Wikipedia listing for A* search状態：溶液が存在することが保証されている場合、またはそのようなアルゴリズムが適合されている言い換えればA *サーチ変形

、閉集合は、（ツリー検索アルゴリズムをもたらす）を省略することができます新しいノードは、以前の繰り返しよりも小さいfの値を持つ場合にのみ、オープンセットに追加されます。

ただし、これを実行すると、他の点で機能的なA *検索の実装で誤った結果を受け取ることがわかりました。誰かがこの変更をどうやって行うのか、いくつかの光を当てはめることができますか？

私はあなたが書いたものを理解していれば、あなたが閉じたノードを再訪された単調なヒューリスティックに問題があるの？その場合は、この動作を示す例を示してください。 –

あなたのヒューリスティックは以下を満たしていることを確認します：

H（x）は< = D（x、y）は+ H（Y）

あなたのヒューリスティック機能は、取得の費用を過大評価しないことを意味しています現在地から目的地または目的地まで

たとえば、グリッド内にあり、このグリッド上の両方の点でAからBに到達しようとするとします。

このヒューリスティックは、過大評価しない[2 ^（crtX -goalX）^ 2 +（のcrtY -goalY）]

H（X）= SQRTの：良いヒューリスティック関数は、現在位置と目標との間のユークリッド距離であります三角不等式のために。

2011-12-08 00:51:25 Adrian

答えて