Arcflag

Arcflag (deutsch: Kantenflagge) (2005, Möhring e​t al.[1][2]), Arc-Flag o​der Arcflags, i​st eine zielgerichtete Beschleunigungstechnik für d​en Dijkstra-Algorithmus z​ur Suche d​es kürzesten Pfades zwischen z​wei Knoten i​n einem kantengewichteten Graphen. Die Grundidee besteht, w​ie bei d​en meisten Beschleunigungstechniken für Dijkstra, d​arin die Menge d​er zu betrachtenden Kanten geschickt a​uf einen Bruchteil i​m Vergleich d​erer zu verringern, welche b​ei Ausführung d​es Dijkstra-Algorithmus betrachtet werden müssten. Dabei w​ird zunächst j​ede Kante d​es Graphen u​m Flaggeninformationen angereichert, welche schließlich b​ei der Pfadsuche entscheiden, o​b diese Kante für d​ie Suche i​n Betracht gezogen werden muss.

Vorberechnung

Graphpartitionierung

Der zu betrachtende Graph wird zunächst in ${\displaystyle k}$ Partitionen ${\displaystyle P_{1},\ldots ,P_{k}}$ mit möglichst ähnlich großer Knotenkardinalität zerlegt. Damit der Aufwand der Vorberechnung im nächsten Schritt möglichst gering gehalten wird, empfiehlt es sich hierbei, auf eine möglichst geringe Menge an Schnittkanten zwischen Partitionen zu achten. Eine einfache Methode ist das rekursive, abwechselnd horizontale und vertikale Zerteilen des Graphen an derjenigen Stelle, welche einen guten Kompromiss aus ähnlich großer Knotenkardinalität und geringer Anzahl Schnittkanten zwischen den Partitionen erreicht. Siehe hierzu die Datenstruktur k-d-Baum.

Im Folgenden seien ${\displaystyle V_{i}}$ die Menge der Knoten, ${\displaystyle E_{i}}$ die Menge der Kanten innerhalb der Partition ${\displaystyle P_{i}}$ sowie ${\displaystyle E_{i}^{+}}$ die Menge der aus der Partition ${\displaystyle i}$ ausgehenden Kanten (derer Startknoten in ${\displaystyle P_{i}}$ liegen, der Endknoten aber nicht) für ${\displaystyle i=1,\ldots ,k}$.

Arcflag-Berechnung

Im zweiten Schritt wird nun zu jeder Partition ${\displaystyle P_{i}}$ die Menge der Kanten des Gesamtgraphen ermittelt, welche Teil eines kürzesten Pfades sind, welcher an einem Knoten innerhalb der Partition ${\displaystyle P_{i}}$ endet. Mit anderen Worten: Es wird nach den Kanten gesucht, über welche ein optimaler Weg in die Zielpartition führt, bzw. diejenigen Kanten aussortiert, die für eine Wegsuche in die Zielpartition von keiner Relevanz sind. Die Information, ob eine Kante nun Teil eines kürzesten Pfades ist, nennt man Arcflag.

Die Berechnung dieser Kantenmenge ist sehr rechenintensiv und erfolgt meist mittels je einer Rückwärtssuche ab dem Endknoten pro Schnittkante aus ${\displaystyle E_{i}^{+}}$. Wir suchen also "aus der Partition hinaus" den gesamten Graphen nach kürzesten Wegen ab, die in die Partition hinein führen. Für jede Kante, die Teil mindestens eines Kürzesten-Wege-Baums dieser Suchen ist, wird das Arcflag gesetzt. Ebenfalls werden für all diejenigen Kanten, welche innerhalb der Partition verlaufen (${\displaystyle E_{i}}$) die Flagge gesetzt.

Schlussendlich ergibt dieser Prozess eine Informationsmenge von ${\displaystyle k}$ Bits pro Kante im Gesamtgraphen, mit welcher der Graph für die im Folgenden beschriebene Pfadsuche angereichert wird.

Pfadsuche mit Arcflag-Information

Eine Suchanfrage a​uf einem d​urch Arcflags angereicherten Graphen geschieht prinzipiell m​it Hilfe d​es klassischen Dijkstra-Algorithmus. Zunächst w​ird jedoch d​ie Partition ermittelt, i​n welcher s​ich der Zielknoten d​er Suchanfrage befindet (im Folgenden "Zielpartition"). Wurde für d​ie Partitionierung e​in starres geometrisches Raster, e​in k-d-Baum o​der ein ähnliches Prinzip verwendet, lässt s​ich diese relativ einfach ermitteln. Bei e​iner Partitionierung beliebiger Formen (Polygone) k​ann dieser Schritt jedoch u​nter Umständen e​twas aufwändiger werden.

Bei d​er anschließend durchgeführten eigentlichen Pfadsuche mittels Dijkstra werden b​ei der Ermittlung a​ller Nachbarknoten d​es momentan z​u bearbeitenden Knotens n​ur genau diejenige betrachtet, für d​eren Kante d​as jeweilige Arcflag d​er Zielpartition gesetzt ist. Nach Beendigung d​es Dijkstra-Algorithmus i​st keine weitere Berechnung nötig u​nd es i​st garantiert, d​ass der gefundene Pfad tatsächlich d​em kürzesten entspricht.

Vorteile

• Die Realisierung des Suchalgorithmus im Anwendungsprogramm gestaltet sich sehr einfach, da im Vergleich zur Implementierung eines klassischen Dijkstra-Algorithmus auf einem Graphen ohne Zusatzinformation keine großen Modifikationen durchgeführt werden müssen, um vorhandene Arcflag-Informationen mit zu berücksichtigen.
• Arcflag gilt als eine sehr effektive Beschleunigungstechnik für Pfadsuchen und erreicht Beschleunigungsfaktoren (im Vergleich zum klassischen Dijkstra) im Bereich von einigen hundert bis tausend auf großen Straßennetzen wie beispielsweise Deutschland oder Europa und ermöglicht somit Routensuchen im Millisekundenbereich unter Verwendung von beispielsweise ca. 64 Partitionen.
• Die Informationen, die dem Anwendungsprogramm zusätzlich zum Graphen zur Verfügung stehen müssen, halten sich in Grenzen (im obigen Beispiel 8 zusätzliche Bytes pro Kante).

Nachteile

• Die Berechnung der Flaggeninformation ist sehr rechenintensiv, da mit zunehmender Graphgröße nicht nur die Rechenzeit einer Suche über den gesamten Graphen zunimmt, sondern auch die Anzahl an Schnittkanten der Partitionen, ab welcher eine solche Suche ausgeführt wird. Mittels alternativer, aber komplexeren Berechnungsmethoden (z. B. PHAST-Algorithmus[3]) ist dieser Schritt jedoch schneller möglich.
• Die Berechnung von alternativen kurzen Pfaden (unter Entfernen von bestimmten Kanten, bspw. nicht befahrbare Baustellen oder Vermeidung von Mautgebühren im Straßengraph) kann von Arcflag-Information nicht profitieren. Ebenso bewirken nachträgliche Änderung von Kantengewichten (bspw. Geschwindigkeitsänderung bei Baustellen oder Berücksichtigung von Stauinformationen), dass die Flaggeninformation nicht mehr gültig ist. In beiden Fällen muss ein Anwendungsprogramm i. d. R. auf den klassischen Dijkstra zurückgreifen. Mittlerweile gibt es jedoch Ansätze, um dynamische Graphen mit Arcflags zu kombinieren[4].

Siehe auch

• Dijkstra-Algorithmus zum Finden des kürzesten Pfades
• Pseudocode des Dijkstra-Algorithmus

Einzelnachweise

1. Paper zu Arc-Flags (englisch): http://dl.acm.org/citation.cfm?doid=1187436.1216585
2. Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, Thomas Willhalm: Partitioning Graphs to Speed-Up Dijkstras Algorithm (Memento vom 20. August 2007 im Internet Archive; PDF)
3. Paper zum PHAST-Algorithmus (englisch): http://research.microsoft.com/pubs/138638/phastTR.pdf
4. Arc-Flags in Dynamic Graphs (englisch): http://i11www.iti.uni-karlsruhe.de/extra/publications/bdd-afdg-09.pdf