Bibliography | Ahmed, Aimn: Evaluation von Strategien für die Konstruktion von Contraction Hierarchies. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 59 (2020). 37 pages, german.
|
Abstract | 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.
|
Full text and other links | Volltext
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
Superviser(s) | Funke, Prof. Stefan, Rupp, Tobias |
Entry date | January 18, 2021 |
---|