Welchen Algorithmus sollte ich verwenden, um den kürzesten Pfad in diesem Diagramm zu finden?

8

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.)

Nick ODell
quelle
1
Dijkstras Algo ist A * mit h = 0, bezogen auf die 'Pfadfindung'. Meinen Sie damit, dass Sie keine Möglichkeit haben, bessere Mindestkosten abzuschätzen?
jk.
1
Das Festlegen des Attributs für den kürzesten gefundenen Pfad jedes Scheitelpunkts bedeutet nicht, dass Sie eine Milliarde Mal "unendlich" schreiben müssen. Sie benötigen lediglich eine Funktion, die "unendlich" zurückgibt, wenn kein Wert festgelegt ist.
Kevin Cline

Antworten:

6

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.

Kris Van Bael
quelle
Wie überprüfen Sie die Mitgliedschaft in einer verknüpften Liste in weniger als O (n)? Das scheint ein großes Problem zu sein.
Nick ODell
Der Trick besteht darin, beide Listen gleichzeitig zu durchlaufen. Auf diese Weise können Sie in einem einzigen Sweep nach Doppelbildern suchen.
Kris Van Bael
Wird das Einfügen mit einer sortierten Liste nicht teuer? Ein Baum oder Hasch würde besser funktionieren.
Kevin Cline
Ein Baum könnte in der Tat besser sein. In beiden Fällen wird das Einfügen optimiert, indem alle Verbindungen eines Knotens vorsortiert werden.
Kris Van Bael
Oder besser gesagt ... Eine einzelne verknüpfte Liste ist vollkommen in Ordnung. Siehe Änderungen der Antwort.
Kris Van Bael
2

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)

user470365
quelle
0

"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.

Matschig
quelle
Ich bin verwirrt. Aus dem von Ihnen angegebenen Link geht hervor, dass der Floyd-Warshall-Algorithmus darauf abzielt, das Problem des kürzesten Pfades aller Paare zu lösen. Ist es auch der beste Weg, den Abstand zwischen einem einzelnen Paar zu finden?
Nick ODell
@NickODell Floyd-Warshall ist ein gieriger Algorithmus zum Auffinden kürzester Pfade in einem Diagramm. Es ist nur eines, einschließlich Dijkstra, das sehr beliebt ist, um kürzeste Wege vom Startknoten zu allen anderen Knoten zu finden. Denken Sie daran, dass Sie den kürzesten Weg von einem bestimmten Knoten zu allen anderen Knoten und nicht nur zu zwei Punkten finden.
Mushy