2

私はフライトシミュレーションプログラムを設計しており、そのような要件を適切に実装する方法についてのアイデアを探しています。

下の私の写真をご覧ください。ポイントは場所を表します。

ここに画像の説明を入力してください

アイデアはこれです、私はJavaでそのようなシナリオを最もよく表すためにデータ構造を適切に作成したかったので

  • ポイント1にいるとき、最後のポイントであるポイント8からどれくらい離れていますか？

    • ポイント2、3、5はポイント8から同じ距離にあります
    • ポイント1から、ポイント3、ポイント6、7、8の順に移動できます。これは、4ステップに相当します。

  • ポイント0にいるとき

    • ポイント4、5、7の順に移動し、ポイント8に到達します。これも4ステップに相当します。

ユーザーが別のルートを見つけるのを手伝いたかっただけです。

これは可能であり、どのJavaデータ構造がこの要件に最適である必要がありますか？また、これを実装する方法の設計アイデアはありますか？

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

4

2 に答える 2

4

あなたが持っているのは、重みがノード間の距離を表す重み付きグラフです（これは非常に一般的です）。これは自分で簡単に実装できますが（学ぶのに最適な方法です！）、このためのJavaソースコードはたくさんあります。

もちろん、これはJavaデータ構造ではありません。これは、あらゆる場所のすべての人が使用する単なるデータ構造（または概念）です。

加重グラフを実装すると、歩数と距離の計算は非常に簡単になります。

特にここStackoverflowには、これらすべてに関する大量のドキュメントがあります。

于 2012-05-10T07:54:11.707 に答える
1

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

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

隣接行列は、（非常に）密なグラフに使用されます。基本的に、値のNxN行列（重み/コスト、またはyes / noブール値）を保持します。次に、distances [i] [j]は、iからjに移動するコストを表します。使用できないアークには、INF（またはエラー値）のコストがかかります。

問題自体は、通常、ダイクストラのアルゴリズムによって解決されます。

于 2012-05-11T14:11:54.807 に答える