2

特定のソースと宛先のマップ関連データを取得する必要があるプロジェクトに取り組んでいます。将来のリクエストのそれぞれで、キャッシュされているこのすでにフェッチされた情報が使用されます。ただし、ソースまたは宛先のいずれかが変更された場合、古いソースと宛先を含むマップが再構築されます。

私の質問のいくつかは次のとおりです。

  1. 検索が簡単で、ソースと宛先の間のすべての中間ノードを簡単かつ効率的に見つけることができるように、どのデータ構造を使用するか。

  2. メモリ リソースが限られているため、メモリ内に非常に大きな DSC を持つという贅沢は不可能です。

ソースと目的地の間のルートデータをリストとして保存することを検討していますが、これにより検索が線形検索になる可能性があり、どうしても避けたいと考えています。経路情報を格納するための構造を構築するためのオーバーヘッドがいくらかあっても問題ありませんが、検索は迅速かつ簡単でなければなりません。プログラミング言語としてJavaを使用しています。

事前に助けてくれてありがとう

4

1 に答える 1

1

マップをグラフとして表す必要があります。各場所には、すぐに到達できるすべての場所のリストがあります。このようにして、ソースと宛先が与えられたときに、DFS または BFS を実行して、ソースから宛先に移動するすべてのパスとすべての中間ノードを決定できます。

特定の送信元と送信先の間のルートがキャッシュされているため、次に別の送信元または送信先のデータを構築するときに、キャッシュされたデータを試して利用することができます。

于 2013-02-08T08:48:16.667 に答える