Ermitteln des minimalen Radwegs in einem dynamisch gerichteten Graphen
Ich bin kürzlich auf etwas gestoßendies (Edit: Problem A) Interessantes Problem der Hacker-Herausforderung von Spotify zu Beginn dieses Jahres, bei der das Umschalten an Zug-LKW-Kreuzungen zur Rückführung eines Zuges zum Ausgangspunkt festgelegt wird. Der Zug muss in die gleiche Richtung wie links eintreffen und der Zug darf auf den Gleisen niemals rückwärts fahren.
Soweit ich weiß, kann das Problem als ungerichteter (?) Graph modelliert werden, bei dem wir den kürzesten Zyklus von einem bestimmten Scheitelpunkt finden müssen oder feststellen müssen, dass kein solcher Zyklus existiert. Der interessante Teil ist jedoch, dass für einen Scheitelpunkt v die zu v benachbarten Scheitelpunkte von dem zu v genommenen Pfad abhängen, so dass der Graph in gewissem Sinne als gerichtet betrachtet werden könnte, obwohl diese Richtung wegabhängig ist.
Mein erster Gedanke war, jeden Knoten als drei separate Eckpunkte A, B und C zu modellieren, wobei A <-> B und A <-> C und dann eine Breitensuche zu verwenden, um einen Suchbaum zu erstellen, bis wir das Original finden Scheitelpunkt, dies wird jedoch durch die obige Einschränkung erschwert, dass die Adjazenzen für einen bestimmten Scheitelpunkt von dem zuvor besuchten Scheitelpunkt abhängen. Dies bedeutet, dass Knoten in unserem BFS-Baum mehrere Eltern haben können.
Offensichtlich reicht eine einfache BFS-Suche nicht aus, um dieses Problem zu lösen. Ich weiß, dass es Algorithmen gibt, um Zyklen in einem Graphen zu erkennen. Ein Ansatz könnte darin bestehen, alle Zyklen zu ermitteln und dann für jeden Zyklus zu ermitteln, ob der Pfad gültig ist. (d. h. dreht die Richtung nicht um)
Hat jemand andere Einblicke in Lösungsansätze für dieses Problem?
AKTUALISIEREN: Ich folgte dem Ansatz, den @Karussell in den Kommentaren vorgeschlagen hatte.
Hier ist meine Lösung für Github.
Der Trick bestand darin, die Situation mit einem kantenbasierten Diagramm zu modellieren, nicht mit einem herkömmlichen vertexbasierten Diagramm. Die im Wettbewerb bereitgestellte Eingabedatei ist bereits in Form von Kanten angegeben, sodass diese Datei problemlos zum Erstellen einer kantenbasierten Grafik verwendet werden kann.
Das Programm verwendet zwei wichtige Klassen: Road und Solver. Eine Straße hat zwei ganzzahlige Felder, j1 und j2. j1 repräsentiert den Quellübergang und j2 repräsentiert den Zielübergang. Jede Straße ist eine Einbahnstraße, dh Sie können nur von j1 nach j2 fahren. Jede Straße enthält auch eine verknüpfte Liste benachbarter Straßen und eine übergeordnete Straße. Die Road-Klasse enthält auch statische Methoden zum Konvertieren zwischen den in der Eingabedatei verwendeten Zeichenfolgen und Ganzzahlindizes, die die Punkte A, B und C an jeder Kreuzung darstellen.
Für jeden Eintrag in der Eingabedatei fügen wir einer HashMap zwei Straßen hinzu, eine Straße für jede Richtung zwischen den beiden Kreuzungen. Wir haben jetzt eine Liste aller Straßen, die zwischen Kreuzungen verlaufen. Wir müssen nur die Straßen an den Kreuzungen durch die Schalter A, B und C miteinander verbinden. Wenn eine Straße an der Kreuzung.A endet, suchen wir die Straßen, die an der Kreuzung.B und der Kreuzung.C beginnen, und fügen diese Straßen als Nachbarschaften hinzu. Die Funktion buildGraph () gibt die Straße zurück, deren Zielverzweigung (j2) "1A" == Index 0 ist.
Zu diesem Zeitpunkt ist unser Diagramm erstellt. Um den kürzesten Weg zu finden, habe ich einfach ein BFS verwendet, um den Graphen zu durchlaufen. Wir lassen die Wurzel unmarkiert und beginnen damit, die Nachbarschaften der Wurzel in eine Warteschlange zu stellen. Wenn wir eine Straße finden, deren Zielkreuzung "1A" (Index 0) ist, haben wir den kürzesten Zyklus durch den Startpunkt gefunden. Sobald wir den Pfad unter Verwendung der übergeordneten Eigenschaft jeder Straße rekonstruiert haben, ist es eine triviale Angelegenheit, die Schalter entsprechend den Anforderungen des Problems festzulegen.
Vielen Dank an Karussell, der diesen Ansatz vorgeschlagen hat. Wenn Sie Ihren Kommentar mit einer kurzen Erklärung in das Antwortformular aufnehmen möchten, werde ich ihn akzeptieren. Danke auch an @Origin. Ich muss zugeben, dass ich der Logik Ihrer Antwort nicht vollständig gefolgt bin, aber das heißt sicherlich nicht, dass es nicht korrekt ist. Wenn jemand dieses Problem mit Ihrer Lösung löst, wäre ich sehr interessiert, es zu sehen.