Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-9678
Autor(en): Rupp, Tobias
Titel: Contraction Hierarchies für kontinuierliche Graphsimplifizierung mit Qualitätsgarantien
Erscheinungsdatum: 2016
Dokumentart: Abschlussarbeit (Master)
Seiten: 101
URI: http://elib.uni-stuttgart.de/handle/11682/9695
http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-96951
http://dx.doi.org/10.18419/opus-9678
Zusammenfassung: Moderne Navigationsdienste können kürzeste Pfade berechnen und diese dann auf Straßenkarten anzeigen. Als zugrunde liegende Datenstruktur für beide Aufgaben kann eine Contraction Hierarchy verwendet werden. Ursprünglich waren Contraction Hierarchies dazu konzipiert, die Suche nach kürzesten Pfaden zu beschleunigen. In dieser Arbeit wurde untersucht, wie sich Contraction Hierarchies aufbauen lassen, sodass sie sich besser für kontinuierlich vereinfachte Darstellungen eignen. Dazu sollten vor allem die groben Straßenverläufe erhalten bleiben und topologische Inkonsistenzen wie Überschneidungen vermieden werden. Diese Anforderungen wurden formalisiert und in heuristischen Vereinfachungsalgorithmen zum Aufbau von Contraction Hierarchies umgesetzt. Für kleine Eingaben wurden mithilfe ganzzahliger linearer Programme garantiert optimale Lösungen berechnet. Damit konnten in empirischen Vergleichen auf dem Deutschlandgraphen Qualitätsgewinne nahe dem Optimum für vereinfachte Darstellungen von Contraction Hierarchies nachgewiesen werden. Außerdem mussten keine längeren Berechnungszeiten für kürzeste Pfade hingenommen werden.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
ausarbeitung.pdf5,68 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.