Home | Sitemap | Kontakt | english  | Impressum | Datenschutz | KIT
Veranstaltungen
Freitag, 14.Dec 2018
CoderDojo
Montag, 17.Dec 2018
SDQ Winter Day 2018
Donnerstag, 20.Dec 2018
Informatik-Sonderkolloquium: "Predictability and Security for Cyber-Physical Systems"
Freitag, 11.Jan 2019
CoderDojo

Weitere Veranstaltungen...
Informatik mit Profil.
Instagram  

Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche

Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche
Ansprechpartner:

Tobias Columbus

Starttermin:

2009

Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche

  • Stipendienempfänger: Tobias Columbus
  • Projekt: »Vorberechnungstechniken in der Punkt-zu-Punkt-Kürzeste-Wege-Suche «

 

Projektbeschreibung

Die Frage nach dem kürzesten Weg zwischen zwei gegebenen Punkten in einem Straßennetzwerk, ist eines der klassischen Probleme der Informatik, welches bereits 1959 von Edsgar Dijkstra studiert und teilweise gelöst wurde. Das von Dijkstra entwickelte Verfahren ist zwar theoretisch zufriedenstellend, jedoch in manchen Anwendungen, wie zum Beispiel der Routenplanung, nicht performant genug. In der Praxis kommen deshalb oftmals Heuristiken zum Einsatz, die zwar mehr als beeindruckende Ergebnisse erzielen, deren Erfolg man sich aber nur teilweise oder unzureichend erklären kann. Insbesondere gab es zu Beginn meiner Arbeiten auf diesem Gebiet kaum theoretische Resultate, die tatsächlich belegen, dass diese Heuristiken besser, d.h. schneller, als die klassische Lösung von Dijkstra sind.

Während der Förderung durch die Begabtenstiftung Informatik habe ich aufbauend auf meiner Studienarbeit eine solche Vorberechnungstechnik, sogenannte Contraction Hierarchies, genauer unter die Lupe genommen und versucht eine theoretische Erklärung für die Performanz dieses Verfahrens zu finden. Für bestimmte Arten von Netzwerken konnte dieses Ziel teilweise erreicht werden, indem ich ein theoretisches Modell von Contraction Hierarchies entwickelt und mit einem älteren Problem, welches bereits eingehend studiert wurde, verglichen habe. Auf diesem Weg konnte ich zeigen, dass die Berechnung von kürzesten Wegen in Contraction Hierarchies tatsächlich weniger Knoten, d.h. Straßenkreuzungen, berücksichtigt als Dijkstra's Algorithmus. Während der Förderung durch die Begabtenstiftung Informatik habe ich diese Resultate für einige Beispiele und eingeschränkte Klassen von Netzwerken bewiesen und danach im Rahmen meiner Diplomarbeit weiter ausgebaut und verallgemeinert. Leider konnten und können diese Resultate momentan noch nicht in obere Schranken für die tatsächliche Laufzeit des Verfahrens übersetzt werden.
Ein Teil dieser Ergebnisse erschien auch als Konferenzbeitrag "Search Space Size in Contraction Hierarchies" auf der Konferenz ICALP2013. Dieser Artikel kann als Endergebnis des von der Begabtenstiftung geförderten Projektes gewertet werden.

 

Zur Person

  • 2012 Abschluss des Informatikstudiums (Diplom)
  • 2012 - heute Promotion am Institut für Algebra und Geometrie