A* と Dijkstra アルゴリズムの速度をプロファイリングしようとしています。http://www.boost.org/doc/libs/1_38_0/libs/graph/example/astar-cities.cppおよびhttp://www.boost.org/doc/libs/1_50_0で入手可能なコードを使用しています/libs/graph/doc/dijkstra_shortest_paths.html . 500 個のエッジと 300 個のノードを持つ単純なグラフを試しました。
ダイクストラではソース頂点から他のすべての頂点までの最短距離が見つかるため、A* はダイクストラよりも優れたパフォーマンスを発揮すると予想していました。一方、A* では、ゴール ノードまでの最短距離のみが検出されます。
ただし、プロファイリングでは、Dijkstra のパフォーマンスが A* よりわずかに優れていることが示されました。それは可能ですか、それとも何か不足していますか?
Djikstra のアルゴリズムはキューを使用しますが、A* はプライオリティ キューを使用します。一般に、キューは優先キューよりも優れたパフォーマンスを発揮します(たとえば、リンク リストまたは循環配列をO(1)使用したキューからのエンキュー/デキューは であり、ヒープを使用した優先キューからのエンキュー/デキューは ですO(log n))。
ただし、一般的に、このわずかな違いによって A* の実行速度が Djikstra のものよりも遅くなるケースは、いずれにせよ両方のアルゴリズムが非常に高速に実行される傾向があります - 小さな迷路や考慮すべき経路の数が少ない迷路(そのようなもの)ジグザグの迷路として) . より遅い場合(障害物がほとんどない屋外)では、A * ははるかに高速に実行されるはずです。
ケースには 300 ノードがあるため、コードに問題がある可能性が高くなります。それを見なければ、これ以上あなたを助けることはできません。
ヒューリスティックが不正確であるか、A * がダイクストラよりも多くのパスをデータセットに対して実行しているように聞こえます (これもおそらくヒューリスティックによるものです)。
編集:たとえば、A* 実装がデータ セット全体を走査し、毎回 1 つのノード (最適なヒューリスティックを持つノード) のみを展開する場合、ダイクストラよりも全体的に多くのパスを実行できます (各ノードをできるだけ早く展開します)。 ）。
可能であれば、全体の処理時間だけを見るのではなく、各アルゴリズムによって実行されるパスの数をプロファイリングします。