Heuristiky pro cesty v mapách

• Název práce v češtině: Heuristiky pro cesty v mapách
• Název v anglickém jazyce: Heuristics for paths in maps
• Klíčová slova: hledání nejkratších cest, Dijkstrův algoritmus, heuristiky
• Klíčová slova anglicky: shortest path searching, dijkstra's algorithm, heuristics
• Akademický rok vypsání: 2015/2016
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Mareš, Ph.D.
• Řešitel: Bc. Lada Kudláčková - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.04.2016
• Datum zadání: 14.04.2016
• Datum potvrzení stud. oddělením: 22.04.2016
• Datum a čas obhajoby: 05.09.2019 10:00
• Datum odevzdání elektronické podoby: 20.07.2019
• Datum odevzdání tištěné podoby: 19.07.2019
• Datum proběhlé obhajoby: 05.09.2019
• Oponenti: RNDr. Miroslav Kratochvíl, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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/.