java - 500以上のウェイポイント/ノードの最短経路アルゴリズム（例：ダイクストラ法）？

Question

（私の状況を理解するために、この質問と同様にその質問を読んでください。）

ダイクストラ最短経路アルゴリズムは、私が必要とすることを実行できるようです。ただし、ルートマップには約500〜1000のノードがあります。

これまでに見た実装では、ノードの数が50未満に制限されていました。私の質問は、ダイクストラ最短経路アルゴリズムを使用する必要があるのか、それとも代替手段を使用するのかということです。Javaに実装はありますか？

score 5 · Accepted Answer

試してみるまでわかりません。

1000 ノードはそれほど多くありません。ダイクストラのアルゴリズムは、エッジの数が線形の複雑さを持ち、エッジの数はノードの数で最悪でも 2 次です。グラフの説明から、エッジの数を判断するのは困難ですが、完全な 1.000.000 でさえそれほど大きくありません。

主な関心事は、優先キューを使用して適切に実装することです。

編集: Russell & Norvigの第 2 版では、第 3 章と第 4 章で一連の汎用検索アルゴリズムについて説明しています。彼らが一様コストグラフ検索と呼んでいるものは、本質的にダイクストラのアルゴリズムです。彼らの指示に従えば、必要に応じてアルゴリズムを A* 検索に簡単に拡張できます。

score 2 · Accepted Answer

メトリック 2D の世界での最短経路の検索は、A* アルゴリズムの教科書的な例です。ヒューリスティック関数は、各ウェイポイントからターゲットまでの直線距離でなければなりません。

score 0 · Accepted Answer

dijkestra アルゴリズムは prim または kruskal ではなく、後者がエッジのみを使用する場合、全体で mst を計算しています。他にどのアルゴリズムを考えていますか?

3 に答える 3