2

さて、私はJavaを初めて使用します。これに対処するためのより簡単な方法があり、経験豊富な人々が私にいくつかの指針を与えることができると確信しているので、この質問をしています。

私はそれらの間のパスの長さを持つ都市のグラフを持っています。Javaを使用して、出発地から目的地までの最短経路を見つけるアルゴリズムを構築しようとしています。各都市には名前と地図の座標があります。より具体的には、A *アルゴリズムを使用しますが、それは（おそらく）私の質問にとって重要ではありません。

私の問題は、ノードとノード間のパスを長さで表す良い方法を見つけようとしていることです。

私が考える最も簡単な方法は、各都市がインデックスで表される巨大な2次元の正方形の配列を作成することでした。ここで、接続する都市は、配列内で交差する場所で表すことができます。各都市にインデックス番号を割り当てました。配列の値では、0は接続がない場所に移動し、距離は接続がある場所に移動します。

また、「index」属性を持つcityサブクラスがあり、そのインデックスの値が配列に含まれています。これの欠点は、どの都市に接続があるかを把握することです。配列内の都市のインデックスを検索するための追加の手順が必要です。また、どの接続都市に接続インデックスがあるかを検索する必要があります。

これを表現するためのより良い方法はありますか？

4

2 に答える 2

2

別の方法は、隣接するノードへのすべてのポインターを格納する Node 構造を持つことです。

例えば

データ構造にこのようなものがある場合

   A   B   C

A  /   0   1

B  0   /   1

C  1   1   /

新しい構造では

A: [C]
B: [C]
C: [AB]

2D 配列アプローチと比較して、この方法では 2 つのノードが接続されているかどうかを確認するのに時間がかかりますが、使用するスペースは小さくなります

于 2012-06-08T04:19:14.953 に答える
1

検討...

class Node {
  List<Link> link;
  String cityName;
}
class Link {
  Node destinationCity;
  Long distance;
}
于 2012-06-08T05:06:14.850 に答える