Ich habe ein Diagramm mit ungefähr einer Milliarde Eckpunkten, von denen jeder zufällig mit ungefähr 100 anderen Eckpunkten verbunden ist.
Ich möchte die Länge des kürzesten Weges zwischen zwei Punkten finden. Der tatsächlich verwendete Pfad ist mir egal.
Anmerkungen:
- Manchmal werden Kanten abgetrennt oder hinzugefügt. Dies geschieht etwa 500 Mal seltener als bei Suchvorgängen. Es ist auch in Ordnung, Kantenänderungen zu stapeln, wenn Sie dadurch eine bessere Leistung erzielen.
- Ich kann das Diagramm vorverarbeiten.
- Wenn es mehr als 6 Schritte dauert, können Sie einfach mit unendlich zurückkehren.
- Es ist akzeptabel, in 0,01% der Fälle falsch zu liegen, aber nur, wenn eine zu lange Länge zurückgegeben wird.
- Alle Kanten haben eine Länge von 1.
- Alle Kanten sind bidirektional.
Ich suche einen Algorithmus. Pseudocode, englische Beschreibungen und aktueller Code sind alle großartig.
Ich könnte A * verwenden, aber das scheint für die Pfadfindung optimiert zu sein.
Ich habe über die Verwendung des Dijkstra-Algorithmus nachgedacht , aber es gibt einen Schritt, bei dem das Attribut für den kürzesten gefundenen Pfad jedes Scheitelpunkts auf unendlich gesetzt werden muss
(Wenn Sie sich über den Anwendungsfall wundern, ist er für den Underhanded C-Wettbewerb gedacht.)
quelle
Antworten:
Grundlegender Algorithmus
Pflegen Sie zwei Sätze von Knoten, die Sie vom Start- und Endknoten aus erreichen können. Gehen Sie abwechselnd drei Schritte von beiden Seiten. Jedes Mal, wenn Sie Ihr Set durch Knoten ersetzen, können Sie einen weiteren Schritt ausführen. Nach jedem Schritt überprüfen Sie die beiden Sätze auf gemeinsame Knoten.
Optimierungen
Stellen Sie sicher, dass Sie die Mengen sortiert iterieren können, damit Sie in einem einzigen Sweep nach gemeinsamen Knoten suchen können: einer O (n + m) -Operation. Listen werden jeweils bis zu einer Million Knoten umfassen.
Um einen Satz um einen Schritt zu erweitern, müssen Sie alle Verbindungen der Knoten im ursprünglichen Satz abfragen und zu einem neuen sortierten Satz zusammenführen. Das Zusammenführen von 2 sortierten Listen kann wieder in einem einzigen Durchlauf erfolgen. Sie möchten also auch sicherstellen, dass Sie die Verbindungen eines Knotens sortiert abfragen können. (Dies könnte vorverarbeitet werden).
In den letzten beiden Schritten ist jeder neue Satz das Ergebnis der Zusammenführung von bis zu 10000 dieser Abfrageergebnisse. Es ist am besten, diese Zusammenführung adaptiv durchzuführen (Zusammenführen gleich großer Blöcke). Auf diese Weise kann die sortierte Satzdatenstruktur eine einfache verknüpfte Liste sein.
Auf diese Weise wird der gesamte Algorithmus zu O (6 * n + 6 * n * log n), wobei n max ist. 1.000.000.
quelle
Verwenden Sie einfach die Atemzugssuche (keine Notwendigkeit für Dijkstras Alge, da alle Kanten eine einheitliche Länge haben) (und führen Sie sie, wie Kris Van Bael sagte, von beiden Seiten aus)
quelle
"All edges have a length of 1"Dies ist ein Best-Case-Szenario, das den Dijkstra-Algorithmus zu einer perfekten Wahl für gierige Algorithmen macht. Selbst die Verwendung des Floyd-Warshall-Algorithmus mit schneller Matrixmultiplikation würde gut funktionieren.quelle