Montag, 1. Dezember 2008

Wie berechnet das Tool der SBB den Fahrplan?

Auf sbb.ch kann man ja mit jeglichem Konfort einen Fahrplan berechnen lassen. Nehmen wir ein einfaches Beispiel: Ich möchte am Wochenende von Zürich nach Flims fahren, um dort den Schnee zu genießen.
Man könnte naiverweise zwei Annahmen treffen:

  1. Das Programm »weiß« (hat es gespeichert), dass man von Zürich über Chur nach Flims fahren muss und sucht nur nach »Zürich - Chur« und »Chur - Flims«, wobei es jeweils direkte Verbindungen gibt.
  2. Das Programm sucht alle möglichen Verbindungen und wählt dann die kürzesten aus.
Annahme 2. kann schnell verworfen werden: Von Zürich nach Chur kann man auf fast unendlich viele Möglichkeiten gelangen. Das Programm »weiß« ja nicht per se, dass wir nicht nach Altstetten fahren und dort auf einen VBZ-Bus umsteigen wollen. Auch so könnte man nach Flims gelangen.
Die Annahme 1. wird die Basis des Algorithmus' sein. Der Algorithmus stützt sich aber weit gehend auf den Dijkstra-Algorithmus. Er funktioniert so:
  1. Es wird ein Netz erstellt, auf dem alle Wege von Zürich nach Flims eingetragen werden.
  2. Es wird eine geordnete Liste erstellt, in der immer die Destination am Anfang steht, die in der kürzesten Zeit zu erreichen ist.
  3. Diese Destination wird jeweils durch die Destinationen ersetzt, die von ihr aus zu erreichen sind.
  4. Es wird wieder geordnet und ersetzt.
  5. Am Schluss steht in der Liste nur noch das Ziel (der Weg über alle Destinationen hat zum Ziel geführt), alle anderen Destinationen können gelöscht werden.
  6. Es muss nun nur noch berechnet werden, über welchen Weg man am wenigsten Zeit gebraucht hat.

Keine Kommentare: