![]() |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Ich mach mich jetzt mal dran, das Liniennetz umzusetzen :) Und ja, es gibt keine isolierten Linien, so dass man von jeder Haltestelle zu jeder Haltestelle kommt und das Problem schon mal nicht auftritt… Zitat:
Es gibt Apps wie Tube 2 für Windows Mobile (ja, das alte Windows Mobile), die genau so funktioniert haben und mangels echtem Fahrplan immer einen Pauschalwert für Umstiege (5-10 Minuten) veranschlagt haben… |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Der Graph enthält alle Bus/Bahnlinien. Die Kosten einer Fahrt sind je Kante konstant (wenn man Baustellen, Staus etc. mal ignoriert). Die Wartezeiten an den Knoten beim Umsteigen sind abhängig von der Ankunftszeit, die jedoch beim Traversieren des Knotens bekannt ist, denn man sucht ja immer den kürzesten Weg bei Abfahrt zu einem bestimmten Zeitpunkt. Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs. Deswegen kann man (zumindest bei der Bahn) auch angeben, wie lange man mindestens am Umsteigebahnhof warten will. Denn dann wird ggf. nicht die nächste Verbindung genommen, sondern die Übernächste. Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel). Das ist aber kein Showstopper. Zitat:
Implementiere einen Optimierungsalgorithmus deiner Wahl (Djikstra wurde bereits genannt) und modelliere dabei Haltestellen und Umsteigeaktionen als einzelne Knoten. Die Verbindungen zwischen den Knoten sind Fahrt- bzw. Umsteigezeiten. Für beides schreibst Du jeweils eine Funktion
Delphi-Quellcode:
Function FahrtZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;
Function WarteZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer; |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Man müsste nochmal genau am Algorithmus nachvollziehen, ob es da keine Probleme gibt. Da die Gesamtfahrzeit nie größer werden kann, wenn man früher als über einen anderen Weg zu einem Knoten kommt, könnte es mit Dijkstra klappen. Das passt ja ziemlich gut zu den Invarianten. |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Vielleicht wolltest du darauf hinaus, dass man nur so lange wartet, bis man alle Linien, die überhaupt über die aktuellen Haltestelle fahren, einmal durch hat? Das wäre dann im Falle von Zug- oder Busverbindungen auch mein Ansatz gewesen, um das Problem zu lösen. Aber da ich nicht wusste, ob es evilboy wirklich um Zug-/Busfahrpläne geht oder ob er das Szenario nur zur Veranschaulichung gewählt hat, wollte ich es erst mal möglichst allgemein lassen. Hätte ja z.B. sei können, dass der „Fahrplan“ nicht konstant ist... Er wollte ja auch nur einen Denkanstoß; mir fallen zu Zug-/Bahnrouten noch einige andere Details ein... z.B. sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte... Wie BUG schon schrieb: Zitat:
|
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Zitat:
Ausnahme: Eine Kantengewichtung ist negativ, wenn man z.B. mit einem Warp-Antrieb fährt, vergeht die Zeit rückwärts. Dann würde der Djikstra-Algorithmus passen. Wenn man also Busse hat, die ankommen, bevor sie abgefahren sind, muss man den Bellman-Ford Algorithmus verwenden. ;-) Du hast noch nicht verstanden, wie diese shortest-path Algorithmen funktionieren. Aber wenn 'Die Bahn' so einen Algorithmus umgesetzt hat, *kann* es nicht schwer sein. |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension... |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Zitat:
Also: Fahrplan: Bus 1 fährt von A-10->B-20->C Bus 2 fährt von B-10->C Wenn A an B ankommt, fährt #2 3 minuten später ab. Ich führe einen neuen Knoten ein (B1) Bus 2 fährt dann nicht von B ab, sondern von B1 -> C (10 Minuten) Eine neue Kante: Umsteigen von B->B1 (3 minuten). Also hast Du wieder einen simplen gerichteten Graphen. Nix mit Dimension. Nur eben die Funktion, die die Fahrt/Wartezeit von A nach B ausrechnet, benötigt die Ankunftszeit bei 'A'. Bei uns wäre das also: Abfahrt bei A um 15:10 nach B. Ankunft bei B um 15:20 Bus #2 fährt um 15:23 ab also bekommt die Kante B->B1 den Wert 3 (Minuten) Wenn wir bei A um 15:00 losfahren würden, kämen wir bei B um 15:10 an. Dann bekommt die Kante B->B1 den Wert 13 (Minuten) verstanden? |
AW: Entwicklung einer Fahrplanauskunft
Dein Algorithmus ist im Prinzip derselbe wie meiner, nur du hast es etwas anders dargestellt als ich. Was du machst, ist halt kein reiner Dijkstra-Algorithmus, weil bei Dijkstra die Kantengewichte fest sind. Was du also eigentlich machst, wenn du das Gewicht einer Kante „dynamisch berechnest“, ist, dass du einen neuen Knoten im Graphen erzeugst (der vorher nie berührt wurde, deshalb hätte er auch genau so gut schon immer da sein können. Man könnte auch sagen, du „entdeckst“ den Knoten), der über eine Kante mit genau diesem Gewicht mit dem aktuellen Knoten verbunden ist. Wenn du also bei dir „einen“ Knoten markierst, markierst du in Wirklichkeit eine ganze Knotenmenge... Das ist dann das gleiche, wie wenn ich sage „Man muss sicherstellen, dass eine bestimmte Haltestelle nur einmal angefahren wird“.
|
AW: Entwicklung einer Fahrplanauskunft
Also ich kann den Djikstra-Algorithmus nehmen (glaube ich zumindest). Ausgehend vom Startknoten weiß ich genau, wie lange ich zur nächsten Station oder zum nächsten Umsteigen brauche. Diese Kanten sind also fest und werden nicht mehr verändert.
Interessantes Problem, jedenfalls. |
AW: Entwicklung einer Fahrplanauskunft
Zitat:
Der Graph, den du dir mit deinem Dijkstra anschaust, ist eigentlich ein Teilgraph. Das funktioniert mit Dijkstra, aber z.B. mit Bellman-Ford würde es nicht funktionieren, weil dort alle Knoten/Kanten bekannt sein müssen. Zugegeben, bei mir wäre es ohne einen Quantencomputer allerdings auch ein bisschen schwierig, weil es ja unendlich Knoten gibt, aber man könnte den Graphen ja zumindest zeitlich beschränken, wie von BUG zuerst vorgeschlagen. Dann kann man sogar mit zeitreisenden Bussen umgehen ;) Edit: Jetzt krieg ich fast schon Lust, das zu implementieren, die Idee von einem Zeitreisen-Busunternehmen hat irgendwie was :) |
Alle Zeitangaben in WEZ +1. Es ist jetzt 02:20 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz