165

マリオ AI コンペティションの参加者が何をしているかを見ていましたが、そのうちの何人かは A* (A-Star) Pathing Algorithm を利用して非常に優れたマリオ ボットを作成しました。

代替テキスト
( Mario A* ボットの動作のビデオ)

私の質問は、A-Star は Dijkstra と比べてどうですか? それらを見てみると、それらは似ているように見えます。

なぜ誰かが一方を他方よりも使用するのでしょうか? 特にゲームのパスのコンテキストでは?

4

12 に答える 12

197

Dijkstra is a special case for A* (when the heuristics is zero).

于 2009-08-26T05:18:30.183 に答える
123

ダイクストラ:

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

検索：

2 つのコスト関数があります。

  1. g(x): ダイクストラと同じ。ノードに到達するための実際のコストx。
  2. h(x)x: ノードからゴール ノードまでの概算コスト。これはヒューリスティック関数です。このヒューリスティック関数は、コストを過大評価してはなりません。つまり、ノードからゴール ノードに到達するための実際のコストは、xより大きいか等しい必要がありますh(x)。これは許容ヒューリスティックと呼ばれます。

各ノードの総コストは次のように計算されます。f(x)=g(x)+h(x)

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

したがって、ヒューリスティック関数が将来のコストを概算するのに適している場合は、ダイクストラよりもはるかに少ないノードを探索する必要があります。

于 2013-04-28T22:36:35.900 に答える
21

前のポスターが言ったことに加えて、ダイクストラにはヒューリスティックがなく、各ステップで最小コストのエッジを選択するため、グラフのより多くを「カバー」する傾向があります。そのため、Dijkstra は A* よりも役立つ可能性があります。良い例は、複数のターゲット ノードの候補があり、どれが最も近いかがわからない場合です (A* の場合、候補ノードごとに 1 回ずつ、複数回実行する必要があります)。

于 2009-08-26T05:45:10.580 に答える
9

ダイクストラのアルゴリズムは、経路探索には決して使用されません。A* を使用することは、適切なヒューリスティックを考え出すことができれば簡単です (通常、ゲーム、特に 2D の世界では簡単です)。探索空間によっては、使用するメモリが少ないため、反復的深化 A* が望ましい場合があります。

于 2009-08-26T05:45:11.050 に答える
5

ダイクストラは、開始ノードから他のすべてのノードまでの最小コストを見つけます。A *は、開始ノードから目標ノードまでの最小コストを求めます。

したがって、必要なのが1つのノードから別のノードまでの最小距離だけである場合、ダイクストラは効率が低下するように思われます。

于 2010-05-22T23:19:34.117 に答える
2

ダイクストラのアルゴリズムは最短経路を確実に見つけます。一方、A* はヒューリスティックに依存します。このため、A* は Dijkstra のアルゴリズムよりも高速であり、優れたヒューリスティックがあれば、優れた結果が得られます。

于 2009-09-20T03:40:58.030 に答える
0

Astarの疑似コードを見ると、次のようになります。 

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 はノードを 2 回以上評価しないということです。これは 、そのヒューリスティック
により、ノードを 1 回見るだけで十分であると考えているためです。

OTOH、ダイクストラのアルゴリズムは
、ノードが再びポップアップした場合に備えて、それ自体を修正することをためらいません.

これにより、Astar がより高速になり、パス検索により適したものになるはずです。

于 2010-12-05T11:11:54.677 に答える
-1

ダイクストラのアルゴリズムは間違いなく完全で最適であり、常に最短経路を見つけることができます。ただし、主に複数のゴールノードを検出するために使用されるため、時間がかかる傾向があります。

A* search一方、目標までのマンハッタン距離など、より近くで目標に到達するように定義できるヒューリスティック値を持つ問題。ヒューリスティックな要因に応じて、最適または完全のいずれかになります。目標ノードが 1 つの場合は、間違いなく高速です。

于 2011-10-30T14:45:02.317 に答える