パス探索アルゴリズム：A * Vsジャンプポイント検索

Question

A *はダイクストラのアルゴリズムより優れていると認識していますが、これはヒューリスティックな値を考慮に入れるためですが、最短パスを見つけるのに最も効率的なアルゴリズムであるA *障害がある環境では？違いは何ですか？

Answer 1

ジャンプポイント検索は、グラフ上のいくつかの条件に基づいて改良されたA *です。したがって、これらの条件を満たすならば、JPSはA *より厳密に優れています（同じ最適性、最良の場合は大きさの順番が良く、悪い場合はおそらく同じ複雑さですが、 は少し悪い定数です）条件を満たしていなければ、それを使うことはできません。

A *に対するJPSの改善点は基本的に、均一なコスト関数（同じ方向にAからB、BからCに移行するのにかかるコストが同じ）があるグラフをスキップすると場合によってはいくつかのステップがあり、Bのノードを拡張せずにAからCへ直接移動することができます。

JPSはA *よりも枝刈りのテクニックであり、最適ではない。これは、均一なコストのグリッド条件のためです。
概念的には、これは、非均一なグリッド上でA *を使用するのと同じです。隣接ノードは、障害の発生なしにその方向にどれくらい行くことができるか、実行したジャンプのコストを表します。ですから、障害物に遭遇することなく右に10ノード進むことができれば、10 * cのコストで単一のノードを減らす（または直接ジャンプする）ことができます。ここでcはあるノードからもう一つは右です。

元の用紙はありませんhere.