Bibliography | Hübl, Tobias: Android-Offline-Routenplaner mit Contraction Hierarchies. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 50 (2022). 55 pages, german.
|
Abstract | Contraction Hierarchies sind ein Ansatz zur Optimierung von Pfadsuch-Algorithmen, bei welcher eine Graphstruktur um zusätzliche Elemente erweitert wird. Inhalt dieser Arbeit ist die Implementierung einer Android-App zur Berechnung kürzester Pfade auf Teilgraphen unter Verwendung ebensolcher Contraction Hierarchies. Dabei wird unter anderem der Prozess der Extraktion eines Teilgraphen von einem um Contraction Hierarchies erweiterten Graphen auf potentielle Probleme untersucht. Die dabei entdeckten Probleme der Pfadkorrektheit und der Gewährleistung der Absenz ungültiger Kanten werden auf ihre Ursache analysiert und mögliche Lösungsansätze formuliert. Dem folgt eine Dokumentation der Umsetzung der Lösungsansätze in der implementieren Software. Ebenfalls Teil der Arbeit ist eine Untersuchung der Effizienz von einem für Contraction Hierarchies modifizierten Dijkstra-Algorithmus gegenüber einem unmodifizierten Dijkstra. Anhand der Messungen ergab sich eine signifikante Optimierung der Laufzeit des Algorithmus, wenn Contraction Hierarchies zum Einsatz kommen.
|
Full text and other links | Volltext
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
Superviser(s) | Funke, Prof. Stefan, Weitbrecht, Felix |
Entry date | October 27, 2022 |
---|