OSM データを入力として使用して、A から B への最短経路 (A* アルゴリズム) を計算するプログラムを作成しようとしています。プログラムは Android Java で動作するはずです。OSM のデータを使用し、osm_2po で変換します (OSM xml ファイルを SQL ファイルOSM2POに変換するアプリケーションです)。) データを PostGIS データベースに入れます。私のデータベースには次のエントリがあり、正しく理解している限り、次の変数が必要です: source_id、target_id、x1、y1、x2、y2、コスト、逆コスト。source_id は、OSM データに基づくソース ノードの ID です。(長い) target_id は、OSM データに基づくターゲット ノードの ID です。(long) ここで、x1、y1 はソース ノードの座標 (緯度と経度) です。(float) ここで、x2、y2 はターゲット ノードの座標 (緯度と経度) です。(float) cost は、ソースからターゲットまでに生成されたコストです。(float) リバース コストは、ターゲットからソースまで生成されたコストです (float)。私の Java プログラムには、データベース エントリを格納するための次の構造にノードを格納するデータ クラス ノードがあります: ソース、ターゲット、コスト、x、y、x2、y2 データ クラス ノード自体は、x1、y1、x2、y2、bool 訪問済み、sourcenode、targetnode、cost、g、h、および f を格納できます。これは2回保存されます。src -> target に対して 1 回、およびその逆。入力の構造は次のとおりです: 開始ノード: ソース = 0、ターゲット = 選択された開始点、他のすべての変数は 0 に設定されます。 宛先ノード: ソース = 選択された宛先ポイント、および他のすべての変数は 0 に設定されます。
ユーザーが開始したいノードだけがあり、それ以上のものはありません。アルゴリズムは、次のノードが何であるかを見つけて、それぞれ展開する必要があります。実装に使用した疑似コードは、ドイツのウィキペディアWikipediaからのものです。openlist は優先キューで、closedlist は ArrayList です。アルゴリズムでは、マンハッタン距離を使用して H を計算します。
私の質問/問題は次のとおりです。私のデータ構造はそのような実装に適していますか? または、ノードのすべての先行ノードと後続ノードを格納する構造を使用する必要がありますか? データベースからデータを取得して h を設定する必要がありますか? はいの場合、どのように h を計算できますか? 先行ノードから次のノードまでの頂点のコストですか?