Mir ist bewusst, dass der Dijkstra-Algorithmus den Mindestabstand zwischen zwei Knoten finden kann (oder im Falle einer Metro-Station). Meine Frage betrifft jedoch die Suche nach der minimalen Anzahl von Übertragungen zwischen zwei Stationen. Außerdem möchte ich von allen minimalen Übertragungswegen diejenige mit der kürzesten Zeit.
Um nun einen minimalen Übertragungsweg zu finden, verwende ich ein spezialisiertes BFS, das auf U-Bahn-Linien angewendet wird, aber es garantiert nicht, dass der gefundene Pfad der kürzeste unter allen anderen minimalen Übertragungswegen ist.
Ich dachte, dass es vielleicht helfen könnte, den Dijkstra-Algorithmus zu modifizieren - indem man für jede Übertragung heuristisch Gewicht (Zeit) hinzufügt, so dass der Algorithmus davon abgehalten wird, auf eine andere Linie zu übertragen. Aber in diesem Fall müsste ich die Übertragungsgewichte empirisch finden.
Zusätzlich zur Frage:
Mir wurde empfohlen, jedes Mal eine "Strafe" hinzuzufügen, wenn der Algorithmus auf eine andere U-Bahnlinie umsteigen möchte. Hier erkläre ich einige meiner Bedenken darüber.
Ich habe dieses Problem für ein paar Tage verschoben und bin heute wieder dazu gekommen. Wenn man sich das Problem erneut anschaut, sieht es so aus, als würde man den Dijkstra-Algorithmus auf Stationen ausführen und herausfinden, wo die Übertragung stattfindet, ist es nicht so offensichtlich, wie man vielleicht denkt.
Hier ist ein Beispiel:
Wenn ich hier ein Teildiagramm (nur 4 Stationen) und ihre U-Bahn Linien habe: A (rot), B (rot, blau), C (rot), D (blau). Lass die Station A die Quelle sein.
Und die Verbindungen sind:
---- D (blau) - B (blau, rot) - A (rot) - C (rot) -----
Wenn ich dem Dijkstra-Algorithmus folge: Zuerst setze ich A in die Warteschlange, entziehe dann A in der 1. Iteration und schaue auf seine Nachbarn: B und C aktualisieren I ihre Abstände entsprechend den Gewichten A-B und A-C. Jetzt, obwohl B zwei Linien verbindet, weiß ich an dieser Stelle nicht wenn ich bei B eine Überweisung machen muss, dann füge ich die "Strafe" für eine Überweisung nicht hinzu. Nehmen wir an, dass der Abstand zwischen A-B & lt; A-C, die bei der nächsten Iteration bewirkt, dass B aus der Warteschlange entfernt wird. Sein Nachbar ist D und nur hier Punkt Ich sehe, dass die Übertragung bei B gemacht werden musste. Aber B wurde bereits verarbeitet (aus der Warteschlange). S
Ich bin mir also nicht sicher, wie diese "Verzögerung" bei der Bestimmung des Übertragungsbedarfs die Integrität des Algorithmus beeinflussen würde. Irgendwelche Gedanken?
Sie können jeder Ihrer Gewichte ein Paar machen: (# of transfers, time) . Sie können diese Gewichte auf die naheliegende Weise hinzufügen und sie in lexikographischer Reihenfolge vergleichen (vergleiche # Anzahl der Übertragungen zuerst, benutze die Zeit als Tiebreaker).
Natürlich, wie andere bereits erwähnt haben, erzeugt die Verwendung von K * (# of transfers) + time für einige K, die groß genug sind, den gleichen Effekt, solange Sie die maximale Zeit a priori kennen und Ihnen die Bits in Ihrem Gewichtsspeicher nicht ausgehen.
Ich werde meine Lösung mit dem A * -Algorithmus beschreiben , die ich für eine Erweiterung (und eine Verbesserung - bitte erschieß mich nicht) des Dijkstra-Algorithmus halte, der einfacher zu verstehen ist. Die Grundlagen davon gehen so:
Anstatt Ihr Gewicht einfach Distanz-so-weit + Mindest-Distanz zum Ziel zu machen, könnten Sie zwei Gewichte verwenden: Stopps und Distanz / Zeit, verglichen auf diese Weise:
Grundsätzlich zu vergleichen:
Und sortiere deine Warteschlange auf diese Weise.
Wenn du jemals Mario Party gespielt hast, denke an Stops als Sterne und Entfernung als Münzen. In der Mitte des Spiels wird eine Person mit zwei Sternen und zehn Münzen über jemandem mit einem Stern und fünfzig Münzen stehen.
Dies garantiert, dass der erste Knoten, den Sie aus Ihrer Prioritätswarteschlange nehmen, die Ebene ist, die die geringste Anzahl von Stopps hat.
Sie haben die richtige Idee, aber Sie müssen die Übertragungsgewichte nicht wirklich empirisch finden - Sie müssen nur sicherstellen, dass das Gewicht für eine einzelne Übertragung größer ist als das Gewicht für die längste mögliche Reisezeit. Sie sollten ziemlich sicher sein, wenn Sie einer Übertragung ein Gewicht geben, das ungefähr einem Jahr der Reisezeit entspricht.
Wie Amadan in einem Kommentar bemerkt hat, geht es nur darum, ein rechtes Diagramm zu erstellen. Ich werde es nur ausführlicher beschreiben.
Betrachten Sie zwei Scheitelpunkte (Stationen) als Kante, wenn sie sich in einer einzigen Linie befinden. Mit diesem Graph (und den Gewichten 1) finden Sie eine minimale Anzahl von Übergängen mit Dijkstra.
Nehmen wir nun an, dass die maximale Reisezeit immer weniger als 10000 ist (verwenden Sie Ihre Konstante). Dann ist das Gewicht der Kante AB (A und B sind auf einer Linie) ein time_to_travel_between(A, B) + 10000 .
Das Ausführen von Dijkstra in einem solchen Graphen garantiert, dass eine minimale Anzahl von Übergängen verwendet wird und an zweiter Stelle die minimale Zeit erreicht wird.
update bei Kommentar
Lass es uns "beweisen". Es gibt zwei Lösungen: mit 2 Transfers und 40 Minuten Fahrzeit und mit 3 Transfers und 25 Minuten Fahrzeit. Im ersten Fall reisen Sie auf 3 Linien, so dass das Pfadgewicht 3 * 10000 + 40 beträgt. In der Sekunde: 4 * 10000 + 25. Die erste Lösung wird ausgewählt.
Ich hatte das gleiche Problem wie du, bis jetzt. Ich habe Dijkstra benutzt. Die Strafen für Transfers sind in der Tat eine sehr gute Idee und ich benutze sie schon seit einer Weile. Das Hauptproblem ist, dass Sie es nicht direkt im Gewicht verwenden können, da Sie zuerst die Übertragung identifizieren müssen. Und ich wollte den Algorithmus nicht ändern.
Also, was ich gemacht habe, ist, dass jedes Mal und Sie eine Übertragung finden, löschen Sie den Knoten, fügen Sie ihn mit dem Strafgewicht hinzu und führen Sie den Graphen erneut aus.
Aber auf diese Weise habe ich herausgefunden, dass Dijkstra nicht funktionieren wird. Und hier habe ich Floyd-Warshall ausprobiert, das im Gegensatz zu Dijkstra alle möglichen Pfade durch den Graphen zwischen jedem Knotenpaar vergleicht.
Es hat mir bei meinem Problem geholfen, zu Floyd-Warshall zu wechseln. Hoffe es hilft dir auch. Es ist einfacher zu programmieren und viel einfacher zu implementieren.