このウェブサイトのコードに基づいて、ダイクストラのアルゴリズムを実装しています。基本的に、多数のノード (たとえば 10000) があり、各ノードは他のノードへの接続を 1 ～ 3 つ持つことができます。
ノードは 3D 空間内でランダムに生成されます。接続もランダムに生成されますが、常に最初に最も近い近隣との接続を見つけようとし、ゆっくりと検索範囲を広げます。各接続には 1 の距離が与えられます。（これが問題になるとは思えませんが、それは単なる背景です）。
この場合、アルゴリズムは、開始点から他のすべてのノードまでの最短ホップ数を見つけるために使用されています。また、10,000 ノードでも問題なく動作します。私が抱えている問題は、ノードの数が増加すると、たとえば 200 万に近づくと、グラフを作成しようとすると、コンピューターのメモリをすべて使い果たしてしまうことです。
アルゴリズムを実装してメモリフットプリントを削減する別の方法を知っている人はいますか?または、メモリ使用量が少ない別のアルゴリズムがありますか?
上記のコメントによると、グラフのエッジを距離行列 long dist[GRAPHSIZE][GRAPHSIZE]で表しています。これにはO(n^2)メモリが必要であり、 の値が大きい場合には多すぎますn。また、少数のエッジしかない場合の実行時間の観点からも、適切な表現ではありません。データ構造によっては、潜在的に高速になる可能性がある場合に、ダイクストラのアルゴリズムにO(n^2)時間がかかります (はノードの数です)。n使用済み。
あなたの場合、各ノードは最大 3 つの他のノードにしか接続されていないと言ったので、このマトリックスを使用しないでください。代わりに、ノードごとに、接続されているノードのリストを保存する必要があります。次に、ノードの近隣を調べたい場合は、このリストを反復処理するだけです。
特定のケースでは、必要に応じてノードごとに計算できるため、このリストを保存する必要さえありません。たとえば、グラフがグリッドで、各ノードが隣接するグリッド ノードに接続されている場合、ノードの隣接ノードをその場で簡単に見つけることができます。
グラフ表現を最小化してもメモリが本当に余裕がない場合は、分割統治法を考慮して、ダイクストラのアルゴリズムのバリエーションを開発できます。
アイデアは、データを小さなチャンクに分割することです。そのため、チャンク内の各ポイントに対して、各チャンクでダイクストラのアルゴリズムを実行できます。
これらのマイナー チャンクで生成された各ソリューションについて、それを別のデータ チャンクへの一意のノードと見なし、そこからダイクストラの別の実行を開始します。
たとえば、次の点を考慮してください。
.B .C
.E
.A .D
.F .G
特定のノードに最も近いポイント (たとえば 2 ホップ以内) を選択し、そのソリューションを拡張されたグラフの一部として使用できます。これは、前のポイントをポイントの 1 つのセットのみと見なし、距離はその結果の距離に等しくなります。ダイクストラ ソリューション。
から始めるとしましょうD:
closest pointsto を選択します。Dnumber of hopsDます。Dと最短パスの最後のノードを直接リンクされたノードとして使用しDます。ここにはコストのかかる余分な処理がありますが、メモリの制限を超えることができます。また、他のマシンがあれば、プロセスを分散することもできます。
これはプロセスのアイデアにすぎないことに注意してください。ここで説明したプロセスが必ずしも最適な方法であるとは限りません。分散型ダイクストラのアルゴリズムを探していると、興味深いものが見つかるかもしれません。
私はboost::graphが大好きです。メモリ消費量は非常に少ないです (1,000 万ノードと 2Gb RAM の道路ネットワークで使用しました)。
ダイクストラの実装がありますが、自分で実装して理解することが目標である場合でも、グラフ表現 (隣接リストをお勧めします) を使用して、自分の結果と自分の結果を比較して、結果が正しいことを確認できます。
一部の人々は、他のアルゴリズムについて言及しました。これがメモリ使用量に大きな影響を与えるとは思いませんが、速度に影響を与える可能性が高くなります。2M ノード、トポロジが街路網に近い場合、実行時間は 1 つのノードから他のすべてのノードまで 1 秒未満になります。
http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html