最短経路のA *（星型）検索アルゴリズム

Question

基本的に私はgps座標を含むノードのセットを持っていますが、このジオポイントを使ってA *検索をどのように実装すればよいのですか？ある点から他の点までの距離を割り当てることによって最短経路を見つける。

アップデート：私は、最短経路のルートを描くと述べたアルゴリズムにより、各ノードを通過することによって、これを達成すると、ノードの距離が最短経路を見つけるために横断比較しようとしています01/11/12

。別の問題は、Android/Javaで適切なA *検索の実装が見つからないことです。私の問題は今、次のとおりです。私は、配列やリンクリストに保存しなければならないように私は、道路の各交差点のgeopoint（ノード）を保存しますので

1. ？

2. 今は各ノードの距離を計算できましたが、動的には計算できませんでした。 A *検索を使用して最短ルートを計算する際にこれを使用するにはどうすればよいですか。二点間

Answer 1

ユークリッド距離（すなわち、直線距離）は、良好なヒューリスティック関数であってもよいです。

A *検索の詳細はWikipediaで検索してください。

実際には、の単一ソースの最短経路を見つけるためのダイクストラのアルゴリズムの検索が変更されています。唯一の違いは、A *検索はヒューリスティック関数を使用してガイドを検索し、不要な検索ツリーブランチを枝刈りすることです。良いヒューリスティック関数は、その値が任意の探索経路に沿って単調になるように設計されるべきである。 を過大評価しないでください。 2つの状態間の実際の距離。ユークリッド距離は2点間の最小可能距離であるため、2点間の距離を過大評価する機会はありません。

ユークリッド距離の詳細については、hereを参照してください。地理座標に適用する場合は、hereを参照してください。

Answer 2

あなたは正確に何を達成しようとしていますか？A *は発見的探索アルゴリズムである。次の「最良の」動きを見つけるためにゲームプレイで使用されます。すべてのノードを接続する最短経路を見つけようとしていますか？この場合は、 "旅行セールスマンの問題"のためのlook/google。

Answer 3

Hereはメモリ効率がよく、よくテストされたオープンソースで、A *の実世界での実装であり、Androidでも使用できます。距離の計算は簡単に置き換えることができます（デフォルトのものは高速なhaversineの実装です）