Arcflag
Arcflag (deutsch: Kantenflagge) (2005, Möhring et al.<ref>Paper zu Arc-Flags (englisch): http://dl.acm.org/citation.cfm?doid=1187436.1216585 </ref><ref>Rolf H. Möhring, Heiko Schilling, Birk Schütz, Dorothea Wagner, Thomas Willhalm: <templatestyles src="Webarchiv/styles.css" />{{#if:20070820043734
| {{#ifeq: 20070820043734 | *
| {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20070820043734}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20070820043734}} im Internet Archive{{#if: PDF | ; PDF }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF | ; PDF }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: PDF | ; PDF }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: PDF | ; PDF }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm | {{#invoke:WLink|getEscapedTitle|Partitioning Graphs to Speed-Up Dijkstras Algorithm}} | {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20070820043734|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf}}
|| {{#if: || }}
}}{{#if: Partitioning Graphs to Speed-Up Dijkstras Algorithm
| {{#if: {{#invoke:WLink|isBracketedLink|Partitioning Graphs to Speed-Up Dijkstras Algorithm}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch: PDF
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://arrival.cti.gr/uploads/Documents.0021/ARRIVAL-TR-0021.pdf }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}}</ref>), Arc-Flag oder Arcflags, ist eine zielgerichtete Beschleunigungstechnik für den Dijkstra-Algorithmus zur Suche des kürzesten Pfades zwischen zwei Knoten in einem kantengewichteten 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 verringern, 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 <math>k</math> Partitionen <math>P_1,\ldots,P_k</math> 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 <math>V_i</math> die Menge der Knoten, <math>E_i</math> die Menge der Kanten innerhalb der Partition <math>P_i</math> sowie <math>E_i^+</math> die Menge der aus der Partition <math>i</math> ausgehenden Kanten (derer Startknoten in <math>P_i</math> liegen, der Endknoten aber nicht) für <math>i=1,\ldots,k</math>.
Arcflag-Berechnung
Im zweiten Schritt wird nun zu jeder Partition <math>P_i</math> die Menge der Kanten des Gesamtgraphen ermittelt, welche Teil eines kürzesten Pfades sind, welcher an einem Knoten innerhalb der Partition <math>P_i</math> 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 <math>E_i^+</math>. 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 (<math>E_i</math>) die Flagge gesetzt.
Schlussendlich ergibt dieser Prozess eine Informationsmenge von <math>k</math> Bits pro Kante im Gesamtgraphen, mit welcher der Graph für die im Folgenden beschriebene Pfadsuche 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<ref>Paper zum PHAST-Algorithmus (englisch): http://research.microsoft.com/pubs/138638/phastTR.pdf</ref>) 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<ref>Arc-Flags in Dynamic Graphs (englisch): http://i11www.iti.uni-karlsruhe.de/extra/publications/bdd-afdg-09.pdf</ref>.
Siehe auch
- Dijkstra-Algorithmus zum Finden des kürzesten Pfades
- Pseudocode des Dijkstra-Algorithmus
Einzelnachweise
<references />