Název: Efektivní hledání nejkratších cest v sítích hromadné přepravy osob
Překlad názvu: Efficient shortest path search in the public transportation networks
Autoři: Martínek, Vladislav
Typ dokumentu: Rigorózní práce
Rok: 2012
Jazyk: cze
Abstrakt: [cze] [eng]
Hledání nejkratší cesty je jeden z nejstudovanějších grafových problémů; má mnoho zajímavých aplikací v nejrůznějších odvětvích. Jedním z odvětví je hromadná přeprava osob, kde délka cesty závisí na jízdních řádech spojů realizujících cestu. Cílem této práce je najít efektivní algoritmus pro hledání nejkratší cesty v sítích hromadné dopravy a implementovat jej v knihovně, která bude použitelná i na přenosných zařízeních. V průběhu implementace budou prozkoumány možnosti předzpracování jízdních řádů a využití heuristik pro urychlení hledání cesty. The search for the shortest path is one of the most studied graph problems with interesting applications in various elds. One such eld is human mass transportation, where the path length depends on the time tables of the tra c relations, which implements the path. Goal of this study is to nd efficient algorithm for the shortest path search in human mass transportation network and implement it in the library, which will be also useable on portable devices. The possibilities of time tables preprocessing and use of heuristics on search acceleration will be explored during implementation.
Klíčová slova: hledání nejkratší cesty; pěší navigace; redukce grafu; síť hromadné dopravy; network reduction; pedestrian navigation; public transport network; shortest path search

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/53209

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-438971


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Rigorózní práce