Bachelorarbeit BCLR-2020-59

Bibliograph.
Daten
Ahmed, Aimn: Evaluation von Strategien für die Konstruktion von Contraction Hierarchies.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 59 (2020).
37 Seiten, deutsch.
Kurzfassung

Eine altbewährte Lösung des shortest-path-problem liefert der Dijkstra-Algorithmus. In den vergangenen 20 Jahren wurden dennoch diverse Techniken zur Verbesserung der Effizienz entwickelt. Eine dieser Techniken stellen die Contraction Hierarchies dar, welche auf einer Vorverarbeitung des Graphen basieren. Auf sehr dichten Graphen, beispielsweise bei realen Straßennetzwerken, stellte sich der Dijkstra als ineffizient heraus. Mithilfe dieser Voerverarbeitungstechnik Contraction Hierarchie kann eine Suchanfrage um ein Vielfaches schneller beantwortet. Eine weitere bekannte Technik, zur Verschnellerung solcher Anfragen, stellen Hub-Labels dar. Es kann dadurch ein Distanzorakel aufgebaut werden, sodass die Antwortzeit auf eine kürzeste Distanzanfrage im Bereich weniger Mikrosekunden liegt. Die vorliegende Bachelorarbeit stellt verschiedene Strategien zur Erstellung einer Contraction Hierarchie vor und bemisst ihre Qualität an der Menge der berechneten Hub-Labels. In einem experimentellen Vergleich, wurden verschiedene Strategien vorgestellt, evaluiert und miteinander verglichen. Dabei wurde der ”Tradeoff”zwischen der Berechnungszeit und der gemessenen Qualität ebenfalls berücksichtigt.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik
BetreuerFunke, Prof. Stefan, Rupp, Tobias
Eingabedatum18. Januar 2021
   Publ. Informatik