このような事例を表現するアイデア

Question

私はフライトシミュレーションプログラムを設計していますが、私はこのような要件を正しく実装するためのアイデアを探しています

こんにちは私の写真を見てください。ポイントは場所を表します。

アイデアは、これは、私がきちんと最高

• 私はポイント1で午前、私はどこまで午前ようにJavaでこのようなシナリオ を表現するためのデータ構造を作成したいですポイント8である最後のポイントから？

  • ポイント2、3及び5は、点1から点8
  • から同じ距離にある、私はポイント6にポイント3に横切ることができ、次に7、次に8個の4つのステップに等しいであろう。

• Iが0点

  • にいるとき、私はまた、4つのステップに等しくなる点8に達し、その後7次いでポイント4に横切ることができました。

私はちょうど彼らが別のルートを見つけるためにユーザーを支援したいと考えました。

これは可能ですか、どのJavaデータ構造がこの要件に最も適していますか？また、どのようなデザインアイデアを実装する方法？

申し訳ありません私の質問があいまいな場合は、私はそのような要件を適切に処理できるほど多くの情報を取得しようとしています。

Answer 1

あなたが持っているものはweighted graphです。ここで重みはノード間の距離を表します（非常に一般的です）。あなたは簡単にこれを実装することができます（それは学ぶのに最適な方法です）が、そこにはJavaソースコードがたくさんあります。

もちろん、これはjavaデータ構造ではありません。誰もがどこでも使用している単なるデータ構造（または概念）です。

加重グラフを実装すると、ステップと距離の計算は非常に簡単です。

特に、ここには、Stackoverflowという膨大な量の文書があります。

Answer 2

これは、最短経路問題であり、一般的なグラフの問題です。データを表現する通常の方法は、偶然性リストまたはマトリックスです。

adjancency listはすべてのノードについて、すべての1ステップ到達可能な宛先を保持します。これはしばしばリンクリストとして実装されます。グラフが比較的まばらな場合（つまり、ノードあたりの送信先が少ない場合）は適切です。

adjancency matrixは（非常に）稠密なグラフに使用されます。基本的には、値のN×N行列（重み付け/コスト、またははい/いいえブール値）を保持します。そして、距離[i] [j]はiからjへの移動コストを表す。利用できない円弧のコストはINF（または何らかの誤差値）です。

問題自体は一般にDijkstra's Algorithmによって解決されます。