Entwicklung einer Fahrplanauskunft

[Furtbichler]

Zitat von NamenLozer:

Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“),

Das ist eine Verbindung. Der gleiche Bummelzug später wird ignoriert. Ein anderer Zug in die gleiche Richtung ist eine andere Verbindung => berücksichtigen.

Zitat:

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

Dafür sind die Algorithmen gedacht. Die sorgen schon dafür, dass das nicht passiert. Die besuchten Knoten werden nicht noch einmal besucht.

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.

[Namenloser]

Zitat von Furtbichler:

Zitat:

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

Dafür sind die Algorithmen gedacht. Die sorgen schon dafür, dass das nicht passiert. Die besuchten Knoten werden nicht noch einmal besucht.

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben.

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

[Furtbichler]

Zitat von NamenLozer:

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben.

Dann weißt Du ja mehr als ich

Zitat:

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

Nein. Lies meinen Ansatz genau. Eine Fahrt von A->B dauert 5 Minuten, Umsteigen bei B dauert 10 Minuten. Ergo ist fahren und umsteigen ein und dasselbe: Ein Übergang von A nach B, der X Minuten dauert.

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?

[Namenloser]

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

[Furtbichler]

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.

[Namenloser]

Zitat von Furtbichler:

Diese Kanten sind also fest und werden nicht mehr verändert.

Aber deine Wartezeiten hängen ja von der Uhrzeit ab und damit von deinem zurückgelegten Pfad. Die Kantengewichte in einem Graphen sind aber unabhängig vom Pfad.

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

[Der schöne Günther]

Also in der Praxis scheint die Not da auch erfinderisch zu machen. Mein Nahverkehrsunternehmen hat keine Hemmungen mich mit der Bahn von 2 bis 5 Uhr im Kreis fahren zu lassen bis endlich morgens wieder der erste Bus in das Zieldorf fährt.

Graphentheorie war nie mein Fall, mich würde vor allem die tatsächliche Kostenfunktion am Schluss interessieren: Wahrscheinlichkeit von Verspätungen, Wartezeit, Zeit zum Umsteigen...