Heuristiky pro cesty v mapách

• Thesis title in Czech: Heuristiky pro cesty v mapách
• Thesis title in English: Heuristics for paths in maps
• Key words: hledání nejkratších cest, Dijkstrův algoritmus, heuristiky
• English key words: shortest path searching, dijkstra's algorithm, heuristics
• Academic year of topic announcement: 2015/2016
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: Mgr. Lada Kudláčková - assigned and confirmed by the Study Dept.
• Date of registration: 14.04.2016
• Date of assignment: 14.04.2016
• Confirmed by Study dept. on: 22.04.2016
• Date and time of defence: 05.09.2019 10:00
• Date of electronic submission: 20.07.2019
• Date of submission of printed version: 19.07.2019
• Date of proceeded defence: 05.09.2019
• Opponents: RNDr. Miroslav Kratochvíl, Ph.D.

Guidelines

Cílem práce je prozkoumat různá heuristická vylepšení Dijkstrova algoritmu pro hledání nejkratší cesty a jejich vhodnost k prohledávání silničních map. Mezi tyto heuristiky patří mimo jiné použití geometrických dolních odhadů (algoritmus A*), předpočítaných vzdáleností k landmarkům, nebo předpočítaných orákul pro aproximaci vzdálenosti. Součástí práce by měla být implementace různých heuristik a jejich srovnání na reálných datech, například z projektu OpenStreetMap. Vhodným měřítkem je například závislost velikosti prohledané části grafu na složitosti nejkratší cesty.

References

Goldberg, Kaplan, Werneck: Better Landmarks Within Reach, in WEA 2007, Volume 4525 of the series Lecture Notes in Computer Science pp. 38-51., 2007.

Wulff-Nilsen: Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff, arXiv:1601.00839.

Projekt OpenStreetMap: Online na http://www.openstreetmap.org/.