FYI.

This story is over 5 years old.

Tech

Dieser simple und elegante Algorithmus macht Google Maps erst möglich

Edsger W. Dijkstras erschuf in 20 Minuten die Lösung für ein extrem komplexes Problem.
​Edsger Dijkstra beim Rechnen. Bild: ​WikipediaAFBorchert | ​CC BY-SA 3.0

Algorithmen sind die Wissenschaft der Cleverness. Als eine natürliche Manifestation logischer Beweisführung—insbesondere ​bei ​vollständiger Induktion—ist ein guter Algorithmus wie ein flüchtiger Schnappschuss, der uns zur inneren Seele eines Problems führt. Ein Urwald voller Möglichkeiten und Beziehungen entwirrt sich zu einem einfachen wiederkehrenden Verhältnis, einem einzeiligen rekursiven Schritt, der grenzenlose Komplexität erschafft. Und zum Durchschauen von tiefgreifender Komplexität braucht man Cleverness.

Anzeige

Der Programmierer Edsger W. Dijkstra kam dem Geheimnis der Algorithmen als erster auf die Schliche, und der nach ihm benannte gehört zu den schlausten Erkenntnissen in der Computerwissenschaft. Der Mathematiker war überzeugt davon, dass jedes komplizierte Problem eine zugängliche Basis besitzt—also einen Weg, in seine Struktur einzudringen— und die richtigen mathematischen Werkzeuge würden diesen Weg weisen können.

​Google ist überall: Jetzt kannst du mit Google Street View durch den Regenwald klettern

Im Jahr 1956 arbeitete Dijkstra am Mathematischen Zentrum der Niederlande an dem Parallelrechner ​ARMAC. Er war der Nachfolger der ersten Computer des Landes, ARRA und ARRA II. Sein Job war es, die Maschinen zu programmieren, und als der ARMAC nach zwei Jahren konzentrierter Arbeit für seine erste öffentliche Präsentation bereit war, brauchte Dijkstra ein Problem, das der Computer lösen konnte.

„Bei einer Demonstration vor Leuten, die sich nicht mit Informatik auskennen, brauchst du eine Problemstellung, die Nicht-Informatiker verstehen können", erzählte Dijkstra 2002 in einem seiner letzten  ​Interviews. „Außerdem müssen sie auch die Antwort verstehen können. Ich entwarf also ein Programm, dass dir die kürzeste Strecke zwischen zwei Städten anzeigt. Dazu benutzte ich eine reduzierte Straßenkarte der Niederlande mit 64 ausgewählten Städten. Den Algorithmus für diese jeweils kürzeste Strecke entwarf in in ungefähr 20 Minuten."

Anzeige

„Was ist der kürzeste Weg, um von Rotterdam nach Groningen zu kommen?", sagte Dijkstra. „Den Algorithmus für diese jeweils kürzeste Strecke entwarf in in ungefähr 20 Minuten."

​Wie ein Postbote mit Algorithmen den größten Slum Brasiliens kartographierte

Heute nimmt sich Google Maps unseren Wegen an und wir haben eigentlich keine Ahnung, welch komplexer Rechenvorgang da wohl hinter steckt. Die Probleme der kürzesten Wege sind ein Hauptmerkmal der Graphentheorie, welche ein paar ziemlich offensichtliche Umsetzungen Anwendungen in unserem Alltag findet und unglaublich schnell in die Tiefe des Problems vordringt. Das Ergebnis ist allseits (informell) bekannt als  ​kombinatorische Explosion, was bedeutet, dass eine gewisse Anzahl verschiedener zu untersuchender Kombinationen bei einem Problem exponentiell ansteigt (auch der Zauberwürfel fällt beispielsweise unter das Phänomen der kombinatorischen Explosion).

Das Ergebnis solch einer Explosion ist, das Probleme wie das des kürzesten Weges extrem schnell anwachsen und durch die quasi unendliche Zeit, welche für den Lösungsvorgang benötigt wird, praktisch unberechenbar werden. Es reichen schon eine Handvoll Knotenpunkte auf einer Karte oder einer Graphik, um die Anzahl möglicher Kombinationen ins Milliardenfache steigen zu lassen, was gewaltige Mengen an Zeit in Anspruch nehmen würde.

Am einfachsten lässt sich Dijkstras Algorithmus wohl mit einem Beispiel erklären. In der Grafik unten stehen die Zahlen für die Gewichtung der jeweiligen Verbindungen. (Die Gewichtung kann eine einfache Distanz sein oder oder jede andere Verbindung, die zur Verkleinerung der vorhandenen Fläche beiträgt.) Wir wählen also s als unseren Ausgangspunkt aus, mit dem Wert 0. Wir benötigen 0 Meter (oder was auch immer) um dorthin zu kommen, denn das ist die Startposition. Als nächstes betrachten wir die benachbarten Knotenpunkte von s, welche wir als eine Art zu erforschende Grenzen ansehen könnten.

Anzeige
route.jpg

Im ersten Schritt widmen wir uns dem Knotenpunkt, der lediglich 1 Einheit entfernt ist. Wir weisen ihm die Kennzeichnung a zu und gehen weiter zu den nächsten Begrenzungspunkten und ihren jeweiligen Distanzen. b ist 1 entfernt (2 vom Anfang), c ist 2 entfernt (3 vom Anfang) und dann gibt es noch d, das ebenfalls 2 vom Anfang entfernt ist. Da wir nun nach der kürzesten Strecke vom Anfang suchen, sind wir gezwungen, uns von s nach d(2 vom Anfang) zu begeben und wir belegen d mit dem Wert 2. Im nächsten Schritt des Algorithmus gehen wir von d nach c, welches 10 entfernt ist (12 von s), doch wir sehen uns auch noch einmal unseren Außenposten a an und stellen fest, dass wir von dort auch nur 2 bis c benötigen (3 vom Anfang) und b in 1 (2 vom Anfang). Unseren nächsten Außenposten setzen wir dann bei b und kennzeichnen ihn mit 2 (2 Bewegungen vom Anfang).

Unser bei b positionierter Forscher ist enttäuscht. Der einzig mögliche Weg bis zu t ist 10 Einheiten lang (12 vom Anfang). Und das sind mehr als 2 Einheiten von a nach c (3 vom Anfang) und die selbe Strecke wie von s nach c über d, eine Möglichkeit die wir jetzt beruhigt ausschließen können (nachdem wir c schon in 3 Einheiten erreicht haben anstatt in 12 über d). Wenn wir uns jetzt also bei c befinden könnte das kompliziert aussehen, ist es aber gar nicht. Wir machen lediglich vorsichtige, tastende Schritte von Knotenpunkt zu Knotenpunkt während wir von dem Algorithmus permanent dazu gezwungen werden, den jeweils kürzesten Weg vom Start einzuschlagen.

Anzeige

Zum Schluss sehen wir uns noch einmal den Weg von b nach t an und stellen fest, dass die Gesamtstrecke 12 beträgt. Währenddessen benötigt der finale Sprung von c nur 1 kostet, was eine kürzeste Wegstrecke von 4 ergibt. So kann also ein unheimlich komplexes Problem ganz einfach, elegant und sogar intuitiv auf dem Papier gelöst werden.

Hier ein weiteres Beispiel:

Dijkstra_Animation.gif

Dijkstra erzählte, dass ihm dieses Prinzip auffiel als er auf einer Terrasse saß und an seinem Kaffee nippte. „Es wurde dann erst drei Jahre später, ​1959 veröffentlicht", erinnert er sich. „Die Publikation ist immer noch ganz hübsch. Ein Grund dafür ist, dass ich die Arbeit ohne Stift und Papier entworfen habe. Dadurch war ich gezwungen jede Art von Komplexität zu vermeiden. Zu meiner Verwunderung wurde dieser Algorithmus zu einem Grundstein meines Ruhms."

Auf dieser Grundidee beruht Google Maps. Nur durch diesen simplen Algorithmus ist das Austüfteln der kürzesten Route überhaupt möglich. Du brauchst nur genug Cleverness, um den eleganten mathematischen Weg zu finden.