[Algorithm] ダイクストラのアルゴリズムとA-Starはどうやって比較されますか?


Answers

ダイクストラ:

それはソースから各ノードへの実際のコスト値である1つのコスト関数を有する: f(x)=g(x)
実際のコストのみを考慮して、ソースから他のすべてのノードまでの最短経路を見つけます。

検索:

それは2つのコスト関数を有する。

  1. g(x) :ダイクストラと同じ。 ノードxに到達するための実際のコスト。
  2. h(x) :ノードxから目標ノードまでの近似コスト。 ヒューリスティックな関数です。 このヒューリスティック関数は、コストを過大評価するべきではありません。 つまり、ノードxから目標ノードに到達するための実際のコストは、 h(x)以上でなければなりません。 認めるヒューリスティックと呼ばれています。

各ノードの総コストは、 f(x)=g(x)+h(x)によって計算される。

A *検索は、有望と思われる場合にのみノードを展開します。 現在のノードから目標ノードに到達することに焦点を当てるだけで、他のすべてのノードに到達することはありません。 ヒューリスティック関数が許容される場合は最適です。

だからあなたのヒューリスティック関数が将来のコストを近似するのが良いなら、Dijkstraよりもはるかに少ないノードを探索する必要があります。

Question

私はMario AI Competitionのメンバーが何をしているのかを見ていて、A *(A-Star)Pathing Algorithmを使ってきれいなマリオボットを作りました。

alt text http://julian.togelius.com/mariocompetition2009/screen1.png
マリオA *ボットの動画

私の質問は、A-StarとDijkstraはどう違うのですか? それらを見て、彼らは似ているようです。

なぜ誰かがそれを使うのでしょうか? 特にゲームでのパスのコンテキストでは?




ダイクストラのアルゴリズムは、経路探索に決して使用されません。 まともなヒューリスティックを思いつくことができれば、A *を使うのは簡単です(通常はゲーム、特に2Dの世界では簡単です)。 探索空間に依存して、Iterative Deepening A *は、より少ないメモリを使用するので、時には好ましい。




あなたがAstarのpsuedocodeを見ると:

foreach y in neighbor_nodes(x)
             if y in closedset
                 continue

一方、あなたがDijkstraために同じものを見るなら、

for each neighbor v of u:         
             alt := dist[u] + dist_between(u, v) ;

つまり、Astarはノードを複数回評価することはしませんが、
一度ノードを見るだけで十分であると考えているからです
そのヒューリスティックに変換する。

OTOH、Dijkstraのアルゴリズムは、それ自体を修正するのを恥ずかしくない。
ノードが再びポップアップします。

Astarをより速く、経路発見に適したものにする必要があります。




DijkstraのガイドバージョンをA *と見なすことができます。 つまり、すべてのノードを探索する代わりに、ヒューリスティックを使用して方向を選択します。

より具体的には、優先度キューを使用してアルゴリズムを実装する場合、訪問しているノードの優先度はコスト(以前のノードのコスト+ここに到達するコスト)とここからのヒューリスティックな推定値の関数になります目標へ ダイクストラでは、優先順位はノードへの実際のコストの影響を受けます。 いずれの場合も、停止基準は目標に到達しています。




Dijkstraのアルゴリズムは完全に最適であり、常に最短経路を見つけることができます。 しかし、主に複数の目標ノードを検出するために使用されるため、時間がかかる傾向があります。

一方では、ヒューリスティックな値が重要です。これは、目標に向かってマンハッタンの距離など、目標に近づくように定義することができます。 ヒューリスティックな要因に依存する最適または完全ないずれかになります。 1つの目標ノードがあれば確実に高速です。