0

A* 検索アルゴリズムを実装しようとしています。今のところ、私は壁が散らばっている環境を通る良い道を見つけようとしています. 壁はランダムに生成され、場合によってはパスが「スタック」します。捜索がその前とそのすべての側面 (この混乱にそれを導いたものを除く) に壁に遭遇した場合、停止します。これを防ぐためにできることはありますか？私は、H 値に「カラスが飛ぶように」ポイント システムを使用しています。これは、壁を無視し、目的地までの距離を推定するだけです。これにより、このトラップに陥ることがあります。

ありがとう。

4

3 に答える 3

2

距離を過小評価することは、A* にとって「適切」です。

しかし、深さ/幅の問題があるようです。

特定の位置からオプションを評価するときは、それらをオプションのリストに追加して、スコアでチェックおよびソートする必要があります。特定の位置を評価した直後に、その位置から利用可能なオプションを確認する理由はありません。つまり、各位置のすべてのオプションを同じリストに入れる必要があります。このように、行き止まりになった場合、それ以上のオプションは生成されず、リストから 2 番目にスコアの高いオプションを取り出して評価します。

于 2010-12-14T02:27:14.577 に答える
1

有向非巡回グラフのように状態空間を考えると、A *がターミナルノードではないリーフノードに遭遇した場合、そのノードはすでにクローズドリストに移動されているため、問題にはなりません。

非終端（ゴール）リーフノードに遭遇した直後にA *の実装が停止し、まだオープンリストに他のノードがある場合、A*の実装は正しくありません。

于 2010-12-14T02:34:23.737 に答える
0

行き止まりになったとしても、問題にはなりません。A* アルゴリズムは、ヒューリスティックが最も低い次のブロックされていないノードを見つけて、最初からやり直す必要があります。

于 2010-12-14T02:28:11.303 に答える