21

私はパス検索プログラムを開発しています。理論的にはA*の方がダイクストラより優れていると言われています。実際、後者は前者の特殊なケースです。しかし、現実の世界でテストすると、本当に A* の方が優れているのではないかと疑い始めます。

各ノードの緯度と経度が与えられている第 9 回 DIMACS 実装チャレンジ - 最短経路のニューヨーク市のデータを使用しました。

A* を適用する場合、sin、cos、arcsin、平方根を含むHaversine Formulaを使用して、2 点間の球面距離を計算する必要があります。これらはすべて非常に時間がかかります。

結果は、

ダイクストラを使用: 39.953 ミリ秒、256540 ノードを拡張。

A* を使用すると、108.475 ミリ秒で、255135 ノードが拡張されました。

A* では、拡張したノードが 1405 未満であることに注意してください。ただし、ヒューリスティックを計算する時間は、節約された時間よりもはるかに多くなります。

私の理解では、その理由は、非常に大きな実際のグラフでは、ヒューリスティックの重みが非常に小さくなり、計算時間が支配的である一方で、ヒューリスティックの影響を無視できるからです。

4

5 に答える 5

36

A* の要点を多かれ少なかれ見逃していると思います。これは、部分的に意図的により多くの作業を行うことによって、しかし安価なヒューリスティックを使用して、非常にパフォーマンスの高いアルゴリズムになることを意図しています。

A* のノード選択では、距離の近似値を使用する必要があります。(latdiff^2)+(lngdiff^2) を近似距離として使用するだけで、アルゴリズムは Dijkstra よりもはるかにパフォーマンスが高くなり、実際のシナリオでそれほど悪い結果が得られることはありません。実際には、Haversine を使用して選択したノードの移動距離を適切に計算すると、結果はまったく同じになるはずです。潜在的な次のトラバーサルを選択するために安価なアルゴリズムを使用するだけです。

于 2013-04-15T16:39:19.340 に答える
11

A*いくつかの簡単なパラメーターを設定することで、ダイクストラに減らすことができます。Dijkstra で改善されない場合、次の 3 つの可能性があります。

  1. 使用されたヒューリスティックは正しくありません。いわゆる許容ヒューリスティックではありません。A*コスト関数の一部として、ゴールまでの距離を過大評価しないヒューリスティックを使用する必要があります。
  2. ヒューリスティックはコストが高すぎて計算できません。
  3. 実際のグラフ構造は特殊です。

後者の場合、既存の研究に基づいて構築するようにしてください。たとえば、Abraham et al. による「Highway Dimension、Shortest Paths、および Provably Efficient Algorithms」などがあります。

于 2013-05-10T15:34:22.107 に答える
9

宇宙の他のすべてのものと同様に、トレードオフがあります。ダイクストラのアルゴリズムを使用してヒューリスティックを正確に計算することはできますが、それでは目的が果たせませんよね?

A* は、最初にどの方向に拡張するかという一般的な考えを持って目標に向かって傾くという点で優れたアルゴリズムです。とはいえ、必要なのは一般的な方向性だけなので、ヒューリスティックはできるだけ単純にする必要があります。

実際、実際のデータに基づかないより正確な幾何学的計算が、必ずしもより良い方向性を示すとは限りません。それらがデータに基づいていない限り、これらすべてのヒューリスティックは、同じように (正しくない) 正しい方向を示します。

于 2013-04-15T16:43:05.950 に答える
4

一般に、A* は Dijkstra よりもパフォーマンスが優れていますが、実際には A* で使用するヒューリスティック関数に依存します。楽観的で最低コストのパスを見つける h(n) が必要です。h(n) は実際のコストよりも小さくなければなりません。h(n) >= コストの場合、説明したような状況になります。

ヒューリスティック関数を投稿できますか?

于 2013-04-15T16:48:38.427 に答える