2

いくつかの都市とそれらの間の距離を保存してから、最短経路を検索する必要があります。都市と距離はファイルから読み取られます。マトリックスの作成から始めましたが、スペースが多すぎる（2倍以上）ことがわかったので、リストに変更しました。各リスト項目には、point1、point2、およびそれらの間の距離の 3 つが格納されます。

たとえば、次のファイルがあります。

アテネ ストックホルム 34
ストックホルム プラハ 23

私が読んだとき、これは次のように配列に格納されます：

          _____0______ ______1______
point1   | Athens     | Stockholm   |
point2   | Stockholm  | Prague      |
distance | 34         | 23          |
          ------------ -------------

それから私はいくつかの疑問を抱きました..これは確かにスペースを節約しますが、通過するのにもっと時間がかかりますか? リストは配列ですが、接続（エッジ）は任意の方法で配置されているため、マトリックスを使用する場合よりも時間がかかる可能性があると考え始めました。

4

4 に答える 4

2

グラフの隣接リスト表現を調べることをお勧めします。これは、最短経路の問題に最も適した 2 番目のアイデアの修正版です。アイデアは、ノードごとに、そのノードからの出力エッジのリストを格納するノードのテーブルを持つことです。これにより、グラフ内のエッジの総数ではなく、ノードを離れるエッジの数に比例してノードを離れるすべてのエッジを反復処理できます (上記のマトリックス バージョンとリスト バージョンの両方にあるように)。このため、グラフ検索を行うための最も高速なアルゴリズムは、隣接リストを使用します。

彼の助けを願っています！

于 2011-03-18T19:48:12.443 に答える
2

名前を距離から分離します。都市名だけを含むリストを作成します。

          _____0______ ______1______ ______2______ 
city     | Athens     | Stockholm   | Prague      |
          ------------ ------------- -------------

次に、マトリックスを個別に作成します

     __0__ __1__ __2__ 
 0  | 0   | 34  | 0   |
     ----- ----- -----
 1  | 34  | 0   | 23  |
     ----- ----- -----
 2  | 0   | 23  | 0   |
     ----- ----- -----

たとえば、プラハからアテネまでのルートを検索したい場合は、プラハとアテネがリストのどこにあるかを見つけることから始めます...

  • プラハ: 2
  • アテネ: 0

次に、マトリックスを検索してパスを探します。

  • (2,1,23) -> (1,0,34)

最後に、リストを使用して都市に翻訳します

  • (プラハ、ストックホルム、23) -> (ストックホルム、アテネ、34)
于 2011-03-18T20:09:21.563 に答える
1

ここの補助リストは確かにここで最良の選択肢だと思います。後で、D/BFSやダイクストラなどのアルゴリズムに関して非常に役立ちます。

町と距離の両方を維持する方法がわからない場合は、いくつかの構造を使用して両方を一緒に維持してください。番号付きのインデックス付きタウンを使用できる場合は、単純なペア構造を使用します（また、最も簡単な実装は、ペアのn個のSTLベクトルです。

もちろん、STLを使用したくない場合は、使用したいポインターを使用して独自の構造体リストを実装してみてください。

于 2011-03-23T08:15:29.213 に答える
0

あなたのアプローチはうまく見えます。

心をリラックスさせるために、事前定義されたデータの単一の行/エントリを実際に検索するだけでよい場合は、単一のリスト/配列を解析する方が、2 つ (またはそれ以上) のリストを操作するよりも常に高速でリソースに優しいことを覚えておいてください。

物事を複雑にする必要はないと思うので、ここでの他の回答のいくつかに反対する傾向があります。いくつかのデータセルを検索し、それらのデータセルを組み合わせて結果のデータセットを生成する追加の必要性（いくつかの回答が提案されているように）は、データ行を取得するためにリストを一度だけ実行するよりも多くの手順を実行します. 現在使用しているデータは完全な結果のコレクションとして既に結合されていますが、複数のリストに分散されたデータセルを検索して結合する関数の場合、CPU サイクルとメモリ リソースを失うリスクがあるだけです。

Simpler は次のように述べています。現在持っているリスト/配列を簡単に概説するのは、速度に関しては勝てません。

于 2013-06-24T06:04:15.210 に答える