Algorithmen im Alltag (2/12)
Der Routenplaner

"Eines Tages war ich in Amsterdam mit meiner Verlobten einkaufen. Wir setzten uns auf die Terrasse eines Cafés und ich begann nachzudenken und da entwickelte ich den Algorithmus für den kürzesten Weg. Es war eine 20-Minuten-Erfindung, sie wurde 1959 veröffentlicht. Eine recht gute Veröffentlichung. Ein Grund, warum sie so gut ist, ist die Tatsache, dass ich alles ohne Stift und Papier entwickelt habe. Erst später habe ich gelernt: Ohne Stift und Papier zu arbeiten, zwingt Dich dazu, alle vermeidbaren Komplexitäten auch wirklich zu vermeiden." Das hat der inzwischen verstorbene, niederländische Computerpionier Edsger W. Dijkstra einmal in einem Interview erzählt.

Der Algorithmus, den er vor nunmehr 60 Jahren erfunden hat, war ein Routenplaner. Er berechnet den besten Weg von A nach B in einem Straßennetz. Oder besser gesagt, in einer vereinfachten Form des Straßennetzes. Der Algorithmus betrachtet nämlich nur einen Graphen. So ein Graph ist sozusagen ein Netz aus Knoten – das sind die Kreuzungen des Straßennetzes – und aus Kanten – das sind die Straßenabschnitte zwischen den Kreuzungen.
"Die Kanten sind gewichtet. Das heißt, ich habe an den Kanten die Entfernung oder die Zeit, die ich brauche, irgend eine Maßzahl, die ich minimieren möchte. In diesem Sinne ist der Graph dann abstrakter als meine tatsächliche Situation", erklärt der Mathematiker Ulrich Trottenberg.

Man könnte sagen, die Fahrzeit oder die Strecke zwischen zwei Knoten ist in dem Graphen durch die Länge der Kante zwischen ihnen dargestellt. Dass der Graph nur eine abstrakte Abbildung der tatsächlichen Straßenkarte ist, ist der Schlüssel zu allem. Denn nur so kann der Navigationshelfer schnell den besten Weg von A nach B berechnen, nachdem er mit den Eingangsdaten gefüttert wurde.

"Der Input ist der Graph, der die Situation beschreibt, und die Aufgabenstellung: Von wo gehe ich und wo will ich hin?" Das sind der Start und der Endpunkt der Route. Nach ihrer Eingabe beginnt der Algorithmus verschiedene Optionen durchzuspielen. "Er fängt an mit dem Ausgangsknoten und guckt sich sämtliche Knoten an, die von diesem Ausgangsknoten direkt erreicht werden können. Und unter den Knoten nimmt er denjenigen, der die kürzeste Entfernung hat. Dann geht er von diesem Knoten aus und macht den gleichen Prozess in die weiteren Knoten."
So hangelt sich der Navigationshelfer Stück für Stück durchs Straßennetz. Dabei kann es durchaus passieren, dass er über einen Umweg wieder an einen Knoten kommt, an dem er schon war. Und dieser Umweg könnte sogar schneller sein, als der direkte Weg. Im echten Leben wäre das etwa eine Baustelle, die man umfahren muss. "Wenn er das feststellt, dann ersetzt er den direkten Weg durch diesen Umweg." So rechnet er schrittweise immer weiter, bis er schließlich den Zielknoten erreicht hat und das Ergebnis ausgibt.

"Der Output ist der optimale Weg." Ulrich Trottenberg setzt sich dafür ein, algorithmisches Denken an Schulen zu fördern. Edsger Dijkstras Algorithmus findet der Mathematiker dafür bestens geeignet. Weil er so schlank und elegant ist.

"Dass es gelingt, mit einem vergleichsweise unaufwändigen Algorithmus die optimale Lösung zu finden. Tatsächlich ist der Algorithmus nicht nur von der Idee her simpel, sondern auch schnell. Der Rechenaufwand steigt nur quadratisch mit der Anzahl der Knoten – was für komplexe Kalkulationen ein passabler Wert ist. Dennoch wäre der Aufwand bei kompletten Straßennetzen mit ihren Millionen Kreuzungen zu groß.

Navigationssysteme helfen sich damit, dass sie sich etwa an der Luftlinie zwischen Start und Ziel orientieren und Autobahnen bevorzugen – so entgeht ihnen zwar manchmal ein günstiger Schleichpfad, aber sie finden schnell eine gute Lösung. Dabei nehmen sie dem Fahrer viel Denkarbeit ab. Was aber nicht nur positiv ist.

"Wenn man es ins Psychologische bringt, ist es sicher so, dass durch die Navigationssysteme die eigene Phantasie und Kreativität, den richtigen Weg zu finden, begrenzter wird."
Tatsächlich haben kleine Studien gezeigt: Fahrer, die sich auf ihr Navi verlassen, bekommen weniger von ihrer Umgebung mit und lernen die Routen nicht so gut wie Fahrer, die sich selbst orientieren müssen. Für Ulrich Trottenberg überwiegen dennoch die Vorteile der algorithmischen Navigation. Aber zu sehr sollte man sich eben nicht darauf verlassen.
Bei dem LKW-Fahrer, der 2011 in den Rhein fuhr und starb, war wahrscheinlich das Navigationssystem der Auslöser: Es hatte den Mann im Bereich eines Fähranlegers ins Wasser gelenkt. Dass der Routenplaner den LKW-Fahrer in die Irre führte, war wohl eine Folge der algorithmischen Abstraktion. Die Fährverbindung war wahrscheinlich als Kante in dem Graphen eingetragen, der das lokale Straßennetz repräsentierte. Das Navigationssystem, das nur den Graphen kennt, konnte sie somit nicht von einer Straße unterscheiden.