Entwicklung einer Fahrplanauskunft

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

[Furtbichler]

Zitat von Der schöne Günther:

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.

Das ist der Unterschied zwischen Graphen-Theorie und Praxis.

[jobo]

Zitat von Der schöne Günther:

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.

3h im Kreis entspricht nach gängiger Praxis minimal ca 10 km Fußweg, es ist also anzunehmen, dass Du etwas außerhalb wohnst, sonst müsste das System ja Fußweg vorschlagen.

[Furtbichler]

Zitat von jobo:

3h im Kreis entspricht nach gängiger Praxis minimal ca 10 km Fußweg

Ein ICE fährt 300km/h, also währen das 900km Kreisumfang, oder ein Kreis mit dem Durchmesser von 286km. Da wir jedoch nicht wissen, wo der schöne Günther wohnt (obwohl sich das durch Recherche "Kreischender Frauenmob" durchaus herausfinden ließe), ist es müßig, darüber nachzudenken, ob er, anstatt im Kreis zu fahren, nicht doch einfach nach Hause hätte laufen können. Vielleicht macht es Spaß, 3 Stunden im ICE zu sitzen und sich zu überlegen, warum man das eigentlich mit sich machen lässt.

Mir fällt dabei ein Bekannter ein, der -als er noch als DJ arbeitete- morgens nach Hause wollte, nur um im Bus einzuschlafen und vom Busfahrer an der Endhaltestelle geweckt zu werden. Er fuhr also zurück, nur um wieder einzuschlafen und dann an der anderen Endhaltestelle wieder geweckt zu werden. Ein lustiges Schauspiel, das sich 5x wiederholte. Jedenfalls war er irgendwann fit genug, seine Haltestelle im Wachzustand zu erreichen und auszusteigen.

So, ich glaube, wir sollten uns wieder den Optimierungsproblemen zuwenden