Bakalářská práce

Rychlé hledání cesty v obřích grafech

Route-planning in huge graphs

Ondrej Moriš, učo 172887
Abstract

In this thesis we are concerned with route-planning in huge graphs representing real-world road maps: for a given pair of vertices of a road map we want to very effectively find optimal path between them. The application area of this are car GPS navigation systems. Our work introduces a completely new promising approach based on a branch-decomposition and bidirectional search. The main focus of our …více

Klíčová slova
bidirectional search branch-decomposition Dijkstra's algorithm GPS navigation systems graph theory reach route-planning scope
Zadání práce
Ačkoliv k hledání nejkratší cesty v grafu existuje velmi rychlý Dijkstrův algoritmus (v inženýrských aplikacích známý také jako A*), na tak obrovské grafy jako třeba grafy cestní sítě celé Evropy je nedostačující. Přitom takové hledání nejkratší cesty musí každodenně řešit GPS navigační přístroje, které mají mnohem slabší výpočetní možnosti než stolní počítače.

Náplní práce je teoreticky i experimentálně zkoumat možnosti nového přístupu k plánování cest v obrovských grafech za použití vhodného preprocesingu. Přístup by měl využívat vhodnou větvenou dekompozici celého grafu cest Evropy (již poskytla DP Mgr. Martina Juránka). Na této dekompozici (stromu) bude využívat dynamické programování ve směru od listů (elementárních buněk cest) ke kořeni. Cílem je vyvinout prakticky použitelné rychlé algoritmy a experimentálně na PC otestovat jejich výkon a výhody oproti stávajícím algoritmům. Vedle toho student vypracuje nástin směrů dalšího vývoje a budoucí produkční implementace v GPS navigaci.

Administrativní informace
Práce zkontrolována:
11. 10. 2008 13:01, (IS automaticky)
Plný text práce
1,7 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
23. 6. 2008
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

doc. Mgr. Jan Obdržálek, PhD., učo 1552
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce
 
Název
Vložil
Vloženo
Práva
 
examples exs/3
Moriš, O.
18. 5. 2008
Složky
complete-boundary-graphs cbg/11
Moriš, O.
18. 5. 2008
pbd-trees pbd/11
Moriš, O.
18. 5. 2008
query-comparisons cmp/6
Moriš, O.
18. 5. 2008
Soubory

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.