Dijkstra-Algorithmus: Speicherverbrauch

Question

Ich habe eine Implementierung von Dijkstra-Algorithmus, basierend auf dem Code auf this website. Grundsätzlich habe ich eine Anzahl von Knoten (sagen wir 10000) und jeder Knoten kann 1 bis 3 Verbindungen zu anderen Knoten haben.

Die Knoten werden zufällig innerhalb eines 3D-Raums generiert. Die Verbindungen werden auch zufällig erzeugt, jedoch versucht sie immer zuerst Verbindungen mit ihren nächsten Nachbarn zu finden und erhöht langsam den Suchradius. Jede Verbindung hat einen Abstand von eins. (Ich bezweifle, dass irgendetwas davon zählt, aber es ist nur Hintergrund).

In diesem Fall wird der Algorithmus nur verwendet, um die kürzeste Anzahl von Hops vom Startpunkt zu allen anderen Knoten zu finden. Und es funktioniert gut für 10.000 Knoten. Das Problem, das ich habe ist, dass, wenn die Anzahl der Knoten zunimmt, sagen wir in Richtung 2 Millionen, ich benutze alle meine Computer Speicher beim Versuch, das Diagramm zu erstellen.

Kennt jemand eine alternative Methode zur Implementierung des Algorithmus, um den Speicherbedarf zu reduzieren, oder gibt es einen anderen Algorithmus, der weniger Speicher benötigt?

Answer 1

Entsprechend Ihrem obigen Kommentar repräsentieren Sie die Kanten des Graphen mit einem distance matrixlong dist[GRAPHSIZE][GRAPHSIZE]. Dies dauert O(n^2) Speicher, der für große Werte von n zu viel ist. Es ist auch nicht eine gute Darstellung in Bezug auf die Ausführungszeit, wenn Sie nur eine kleine Anzahl von Kanten haben: Es wird Dijkstra Algorithmus O(n^2) Zeit (wo n ist die Anzahl der Knoten) zu nehmen, wenn es möglicherweise schneller sein könnte, abhängig von der Datenstrukturen verwendet.

Da Sie in Ihrem Fall angegeben haben, dass jeder Knoten nur mit bis zu 3 anderen Knoten verbunden ist, sollten Sie diese Matrix nicht verwenden: Stattdessen sollten Sie für jeden Knoten eine Liste der Knoten speichern, mit denen er verbunden ist. Wenn Sie dann über die Nachbarn eines Knotens gehen wollen, müssen Sie nur über diese Liste iterieren.

In bestimmten Fällen müssen Sie diese Liste nicht einmal speichern, da sie bei Bedarf für jeden Knoten berechnet werden kann. Wenn der Graph beispielsweise ein Gitter ist und jeder Knoten mit den benachbarten Gitterknoten verbunden ist, ist es einfach, die Nachbarn eines Knotens im laufenden Betrieb zu finden.

Answer 2

Wenn Sie wirklich nicht Gedächtnis leisten können, auch mit minimizations auf Diagrammdarstellung, können Sie eine Variation des Dijkstra-Algorithmus entwickeln, eine divide Berücksichtigung und Methode erobern.

Die Idee ist Split-Daten in kleinere Stücke, so dass Sie Dijkstra-Algorithmus in jedem Stück für jeden der Punkte darin durchführen können.

Für jede Lösung, die in diesen kleineren Blöcken erzeugt wird, betrachten Sie sie als einen eindeutigen Knoten für einen anderen Datenblock, von dem aus Sie eine weitere Ausführung von Dijkstra starten.

Betrachten wir zum Beispiel die folgenden Punkte:

.B  .C 
        .E 
.A   .D 
     .F     .G 

Sie können die nächsten Punkte zu einem bestimmten Knoten auszuwählen, sagen wir, innerhalb von zwei Sprüngen, und dann die Lösung als Teil des Diagramms verwenden verlängert, wenn man bedenkt das frühere Punkte als nur eine Menge von Punkten, mit einem Abstand gleich der resultierenden Entfernung der Dijkstra-Lösung.

Sagen Sie bitte aus D starten:

• wählen Sie die closest points zu D innerhalb eines gegebenen number of hops;
• Verwenden Sie den Dijkstra-Algorithmus für die ausgewählten Einträge, beginnend mit ;
• Verwenden Sie die Lösung als Grafik mit dem zentralen Knoten und die letzten Knoten auf den kürzesten Wegen als Knoten direkt verbunden mit D;
• Erweitern Sie die Grafik und wiederholen Sie den Algorithmus, bis alle Knoten berücksichtigt wurden.

Obwohl es eine teure zusätzliche Verarbeitung ist hier, würden Sie in der Lage zu übertreffen Speicherbegrenzung, und, wenn Sie einige andere Maschinen haben, können Sie sogar die Prozesse verteilen.

Bitte beachten Sie, dies ist nur die Idee des Prozesses, der Prozess, den ich beschrieben habe, ist nicht unbedingt der beste Weg, es zu tun. Vielleicht finden Sie etwas Interessantes auf der Suche nach verteilten Dijkstra-Algorithmus.

Answer 3

Ich mag Boost :: Graph eine Menge. Es ist Speicherverbrauch sehr anständig (ich habe es auf Straßennetzwerken mit 10 Millionen Knoten und 2 GB RAM verwendet).

Es hat eine Dijkstra-Implementierung, aber wenn es das Ziel ist, es selbst zu implementieren und zu verstehen, können Sie immer noch ihre Graphendarstellung verwenden (ich schlage eine Adjazenzliste vor) und das Ergebnis mit dem Ergebnis vergleichen.

Einige Leute erwähnten andere Algorithmen. Ich denke nicht, dass dies eine große Rolle bei der Speichernutzung spielen wird, sondern eher in der Geschwindigkeit. 2M Knoten, wenn die Topologie in der Nähe eines Straßennetzwerks ist, wird die Laufzeit von einem Knoten zu allen anderen weniger als eine Sekunde betragen.

http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/index.html