MLD

3. November 2013

Der Algorithmus von Dijkstra (ausgesprochen: Deikstra), 1959 veröffentlicht, ist eine klassische Methode für die Suche nach dem kürzesten Weg in einem Graphen. Er kann auf jedem Graphen mit nicht-negativen Kantengewichten angewendet werden. Auf dem Straßennetzwerk angewendet („Knoten“ sind die Kreuzungen, „Kanten“ sind die Wege dazwischen, und „Gewicht“ einer Kante entspricht der Fahrzeit) ist er unpraktisch langsam. Das Problem ist, wenn man den schnellsten Weg zwischen Karlsruhe und Berlin sucht (ungefähr sechs Stunden), muss der Algorithmus alle Stellen durchgehen, die ich in unter sechs Stunden erreichen kann. Das heißt, irgendwann sucht der Algorithmus in den Gassen von Paris, Amsterdam und Mailand nach einem geheimen Tunnel, durch den ich nach Berlin in unter einer Stunde komme. Klingt dumm, allerdings muss der Algorithmus auch mit Graphen umgehen können, bei denen solche Situationen möglich sind.

Durch Ausnutzen gewisser Eigenschaften des Straßennetzwerks ist es auf verschiedenen Arten möglich, die Suche zu beschleunigen (um Faktor einige Millionen). Die Idee ist, im Voraus Daten vorzuberechnen, die nachher bei der Suche benutzt werden um die Anfragen schneller beantworten zu können. Eine der Methoden ist MLD, steht für Multi-Level Dijkstra. Der Graph wird in einigen Teilen partitioniert, etwa nach den Landesgrenzen. Für jedes Land wird der schnellste Weg von jedem Grenzübergang zu jedem anderen berechnet. Bei der Anfrage werden die kürzeste Wege vom Start zu allen Grenzübergängen im Ausgangsland sowie von allen Grenzübergängen im Zielland zum Ziel ausgerechnet, und danach wird nur auf dem sehr viel kleineren Graphen gesucht, der nur die Grenzübergänge und die vorberechnete Pfade dazwischen enthält. Das kann auf mehreren Ebenen gemacht werden — die Länder werden nach Bundesländer oder Kreise geteilt usw. Ich gebe die Landesgrenzen als einfach verstãndliches Beispiel, eigentlich sind sie keine gute Trennlinien. Es sollen wenige Verbindungen zwischen verschiedenen Teilen bestehen, und die Teile sollen etwa gleich groß sein; Landesgrenzen genügen diese Anforderungen meistens nicht.

Als Teil meiner Diplomarbeit muss ich eine bestehende MLD-Implementierung anpassen, sodass sie auch etwas anderes machen kann als nach kürzesten Wegen zu suchen. Das Programm ist ziemlich kompliziert und ich arbeite seit mehreren Monaten an dieser Anpassung. Ich werde langsam verzweifelt und verärgert... so ein ekeliges Mischgefühl...