最短経路を見つけるためのダイクストラアルゴリズムは、A *アルゴリズムよりも優れていますか?
2181 次
2 に答える
11
最短経路を見つけるのは得意ではありません。A* に許容できるヒューリスティックがある限り、Dijkstra よりも短いパスをすばやく見つけることができます。
Mehrad がコメントで指摘したように、0 を返すヒューリスティック関数を A* に与えると、A* は Dijktras に劣化します。
A*のウィキペディアの記事には、これらすべてに関する有益な情報がたくさんあります。
于 2011-02-13T06:18:29.320 に答える
3
特定のソース ノードからグラフ内のすべてのノードへの最短パスを見つけたい場合、ダイクストラは A* よりも優れています。これは、特定のターゲットで停止しない場合でもダイクストラがグラフ全体をカバーするためです。単純な Dijkstra A* とは対照的に、目的指向のアルゴリズムであるため、ソース ノードとターゲット ノードの両方を知る必要があります。A* アルゴリズムを使用して N ノードでグラフ全体をカバーする場合は、基本的にソース ノードからアルゴリズムを N 回実行する必要があります。
ダイクストラは、ソース ノードからグラフの多くのターゲットへの最短パスを見つけるのにも適している場合があります。ターゲットの位置 (特にソースからの距離)、ターゲット M の数、グラフのサイズ、A* ヒューリスティックの品質に応じて、1 つのダイクストラを実行する方が実行するよりもパフォーマンスが優れているか劣っているという損益分岐点があります。 A* アルゴリズムの M 倍。
編集：マシューの正しい批判的なコメントに触発されて、少し言い換えてコメントを追加します：
- Dijkstra は、すべてのノードへの最短経路を見つけることにおいて、A* より優れているわけではありません。正しいのは、A* より悪くないということです。
- A* を持つすべてのノードへの最短パスを見つけるには、ターゲット ノードまでのコストを推定する関数をゼロに設定します (ターゲット ノードがないため)。ターゲット ノードまでのコストを推定する関数をゼロに設定すると、A* は Dijkstra と同じになります。Dijkstra は A* の特殊なケースです。（関数がゼロに設定されている場合、アルゴリズムを（単に「ダイクストラ」ではなく）「A*」と呼ぶ必要があるかどうかは疑問です。ゼロ以外の関数を持つことがA *のコアであるためです。）
- すべてのノードへの最短経路を見つけようとすると、次のようにも言えます。ダイクストラで十分です。A* の改良は必要なく、ここでは役に立ちません。
- 最後の注意事項は、グラフ内の検索にも当てはまります。たとえば、特定のソース ノードに最も近い、特定のフラグでマークされたノードを見つけます。ターゲットが事前にわからないため、検索されたノードのコストを見積もる関数を定義することはできません。したがって、A* (狭義の非ゼロ関数) は適用できません。
于 2011-02-13T14:15:31.087 に答える