Ich entwickle eine Reiseplaner-Website. Es gibt nur wenige Dinge, die in diesem Fall derzeit einfach sind. Im Moment wird die Webseite nur in der Lage sein, Busrouten zu planen, die Zeiten von Bussen sind derzeit nicht verfügbar. Das bedeutet, dass wir nur Busrouten in der DB gespeichert haben und da Bus-Timings nicht verfügbar sind, sind Wartezeiten für Reisende nicht relevant. Was verfügbar ist, ist die Zeit und die Entfernung zwischen zwei Haltestellen für einen einzelnen Bus.
Ich denke, dass die Verwendung eines ungerichteten gewichteten Graphen, der die Zeit- und Entfernungskosten jeder Bushaltestelle für jeden einzelnen Bus speichert, der richtige Weg wäre. Dann könnte ich den Dijkstra-Algorithmus verwenden, um den kürzesten Pfad zwischen zwei Orten zu berechnen, die vom Benutzer auf der Grundlage der Zeit oder der Entfernung je nach Benutzerpräferenz eingegeben wurden. Ich würde herausfinden, ob zwei oder drei Busse durch einfache C # -Funktionen erforderlich sind, wenn sich die Buslinien an den Haltestellen kreuzen und dann diese Kreuzungshaltestellen verwenden, damit der Reisende den Bus wechseln kann. Aber es würde für jeden Bus eine individuelle Grafik geben. Eine Alternative (nicht sicher, ob dies korrekt ist) wäre, ein Diagramm zu verwenden, das jede Bushaltestelle der Stadt als Knoten enthält, und dann diese Technik zu verwenden, um den Weg zwischen zwei Haltestellen zu finden. Welcher ist der richtige Ansatz? Soll ich anstelle von Dijkstra algo den A * -Algorithmus verwenden?
Ein paar allgemeine Punkte für das Design: Ich möchte, dass die App erweiterbar ist, damit ich später bei Bedarf weitere Transportmittel hinzufügen kann. Darüber hinaus könnten die Buszeiten auch später hinzugefügt werden, wenn dies ohne größere Änderungen auf der Website möglich ist. Ich habe hier einige Experten gesehen, die an sehr komplexen Transportprojekten gearbeitet haben. Also bitte helfen Sie mir mit der besten Möglichkeit, diese Funktionalität auf die skalierbarste, modulare und erweiterbare Art und Weise zu implementieren.
Ich habe letzten Sommer eine ähnliche Anwendung gestartet und nie beendet, aber ich habe ein paar Tipps zu diesem Diagramm und wie man seine Daten strukturiert.
Mein Plan war es, dass jeder Stopp als ein Knoten und ein Pfad zwischen jedem dieser Knoten für jedes Mal, wenn ein Bus durchging, angehalten wurde. Zum Beispiel, wenn ein Bus jede halbe Stunde über einen Zeitraum von 6 Stunden angehalten hat, dann würde es 12 Wege zwischen den zwei Knoten geben. Die Zeit war der Haupttreiber hinter den "Kosten" des Pfades, so dass normalerweise der kürzeste Weg gewählt wurde.
Vor dem Start der Anwendung würde die Datenbank für alle Pfade in den nächsten 5 Stunden abfragen (entsprechend anpassen). Es würde dann mit Dijkstra Algorithmus knirschen.
Andere Faktoren, die die Kosten berücksichtigen, sind die tatsächlichen Kosten der Strecke, Transfers (und deren Kosten), Stopps ohne Dächer (wenn Sie schlechtes Wetter haben), etc.
Dieser Plan hat gut für mich funktioniert. Ich lebe in einem Gebiet mit 3 Bussystemen.
Schließlich können Sie Ihre Daten auf ähnliche Weise wie die Google Transit-Feedspezifikation
Ich denke, die wichtigste Optimierung ist das Trennen von Stationen, wo Sie Routen und Stationen wechseln können, wo Sie nicht können. Dann müssen Sie nur Stationen berücksichtigen, bei denen Sie die Route als Zwischenstationen in Ihrem Diagramm ändern können. Dies sollte die Grafik so klein machen, dass Dijkstra in Ordnung ist.
Ich unterscheide Knoten mit nur zwei Kanten, indem ich sie einfach aus dem Graphen herausschneide und stattdessen ihre beiden Nachbarn mit einer Kante der hinzugefügten Länge verbinde. Dann gehe ich auf diesem reduzierten Graphen, der viel schneller sein sollte. d. h. nur Stationen in Betracht ziehen, an denen Routen gewechselt werden können.
Vielleicht können Sie einige Paddydubs für TransportDublin verwenden, die gefunden wurden auf github .
Ich habe einen solchen Algorithmus für eine Testanwendung codiert. Ich hatte für jeden Stopp ein Wörterbuch als Quelle und als Ziel. Der Algorithmus war rekursiv. Jeder Schritt der Rekursion war wie folgt: Bei gegebener Quelle und Ziel würde es eine Liste von Routen erzeugen, die ins Ziel gehen, eine Liste von Routen, die die Quelle verlassen. Wenn es gemeinsame Stopps gab, waren wir fertig, wir melden die Route. Wenn nicht, erzeuge ich benachbarte Stopps für die Quelle und rekursiere. Die nächste Rekursion erzeugt eine Liste von benachbarten Stopps für Sink, Recurse. Vor der Rekursion habe ich natürlich den vorherigen Pfad aufgezeichnet, und am Ende hätte ich eine Liste.
Ich erinnere mich, dass ich einige Cutoff-Bedingungen setzen musste, weil die Rekursion manchmal in bestimmten "schlechten" Regionen stecken bleiben würde.
Ich habe auch dieses Papier angeschaut:
www.citeulike.org/user/rchachan/article/819528
Ich bin interessiert, wenn es Ihnen gelungen ist, dieses Problem anders zu lösen.
Tags und Links algorithm c# graph-theory data-structures graph