Arcflag

Arcflag (eng. Kantenflagge) (2005, Möhring et al.^[1]), Arc-Flag oder Arcflags, ist eine zielgerichtete Beschleunigungstechnik für den Dijkstra-Algorithmus zur Suche des kürzesten Pfades zwischen zwei Knoten in einem gewichteten Graphen. Die Grundidee besteht, wie bei den meisten Beschleunigungstechniken für Dijkstra, darin die Menge der zu betrachtenden Kanten geschickt auf einen Bruchteil im Vergleich derer zu veringern, welche bei Ausführung des Dijkstra-Algorithmus betrachtet werden müssten. Dabei wird zunächst jede Kante des Graphen um Flaggeninformationen angereichert, welche schließlich bei der Pfadsuche entscheiden, ob diese Kante für die Suche in Betracht gezogen werden muss.

Vorberechnung

Graphpartitionierung

Der zu betrachtende Graph wird zunächst in k Partitionen P₁, ..., 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 V_i die Menge der Knoten, E_i die Menge der Kanten innerhalb der Partition P_i sowie E+_i die Menge der aus der Partition i ausgehenden Kanten (derer Startknoten in P_i liegen, der Endknoten aber nicht) für i = 1, ..., k.

Arcflag-Berechnung

Im zweiten Schritt wird nun zu jeder Partition P_i die Menge der Kanten des Gesamtgraphen ermittelt, welche Teil eines kürzesten Pfades sind, welcher an einem Knoten innerhalb der Partition 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 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 Parition verlaufen (E_i) die Flagge gesetzt.

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

Pfadsuche mit Arcflag-Information

Eine Suchanfrage auf einem durch Arcflags angereicherten Graphen geschieht prinzipiell mit Hilfe des klassischen Dijkstra-Algorithmus. Zunächst wird jedoch die Partition ermittelt, in welcher sich der Zielknoten der Suchanfrage befindet (im Folgenden "Zielpartition"). Wurde für die Partitionierung ein starres geometrisches Raster, ein k-d-Baum oder ein ähnliches Prinzip verwendet, lässt sich diese relativ einfach ermitteln. Bei einer Partitionierung beliebiger Formen (Polygone) kann dieser Schritt jedoch unter Umständen etwas aufwändiger werden.

Bei der anschließend durchgeführten eigentlichen Pfadsuche mittels Dijkstra werden bei der Ermittlung aller Nachbarknoten des momentan zu bearbeitenden Knotens nur genau diejenige betrachtet, für deren Kante das jeweilige Arcflag der Zielpartition gesetzt ist. Nach Beendigung des Dijkstra-Algorithmus ist keine weitere Berechnung nötig und es ist garantiert, dass der gefundene Pfad tatsächlich dem 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^[2]) 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^[3].

Siehe auch

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

Fußnoten

1. ↑ Paper zu Arc-Flags (englisch): http://dl.acm.org/citation.cfm?doid=1187436.1216585 bzw. http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf
2. ↑ Paper zum PHAST-Algorithmus (englisch): http://research.microsoft.com/pubs/138638/phastTR.pdf
3. ↑ Arc-Flags in Dynamic Graphs (englisch): http://i11www.iti.uni-karlsruhe.de/extra/publications/bdd-afdg-09.pdf