AE 2010: 5. Vorlesung (18. Mai)
Kürzeste Wege Suche in Straßennetzwerken
- Dijkstra's Originalpaper von 1959 zu seinem SSSP-Algorithmus
- Der bidirektionale Dijkstra wurde im Buch Linear Programming and Extensions von Dantzig vorgestellt.
- Straßennetzwerke, die im Rahmen der 9. DIMACS Implementation Challenge zur Verfügung gestellt wurden (u.a. Europe von der PTV AG).
A*-Suche
- im Umfeld von KI: Doran & Michie (1966)
- Originalartikel: Hart, Nilsson & Raphael (1968)
Überblick zu Speedup-Techniken
- Übersichtsartikel von Delling, Sanders, Schultes & Wagner (2009)
- auch interessant: Folien von Goldberg zu klassischen und aktuellen Techniken
- Multilevel-Methoden: Schulz, Wagner & Weihe (1999)
- Reach-basiertes Routing: Gutman (2004)
- Highway-Hierarchies: Sanders & Schultes (2005)
- fortgeschrittenes Reach-basiertes Routing: Goldberg, Kaplan & Werneck (2006)
- Highway-Node-Routing: Schultes & Sanders (2007)
- Contraction-Hierarchies: Geisberger et al. (2008)
- Entfernungstabellen: Sanders & Schules (2006)
- Kanten-Label: Schulz, Wagner & Weihe (1999)
- SHARC: Bauer & Delling (2008)
- Landmark A*: Goldberg & Harrelson (2005), Technical Report