Název: Hledání cesty v mřížkových grafech
Překlad názvu: Grid-Based Path Planning
Autoři: Novella, Tomáš ; Balyo, Tomáš (vedoucí práce) ; Martínek, Vladislav (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2013
Jazyk: slo
Abstrakt: [eng] [cze]
This thesis deals with effective ways of pathfinding in grid-based graphs. In the first part we pointed out the most important approaches to finding the shortest path. In the second part we proposed an algorithm that improves the speed of pathfinding in some special cases of grid-based graph. In the end we proved it by providing a series of experiments. Powered by TCPDF (www.tcpdf.org) Práca sa zaoberá efektívnym hľadaním ciest medzi dvoma bodmi na mriežkových grafoch. Prvú čast práce tvorí prehľad najdôležitejších algoritmov slúžiacich na hľadanie najkratšej cesty. V druhej časti práce zavedieme koncept tzv. obdĺžnikovej dekompozície grafu. Na základe tohto konceptu sme navrhli algoritmus, pôvodne postavený na algoritme A*. Podľa experimentov tento algoritmus zrýchľuje hľadanie najkratšej cesty na špecifickom type mriežkových grafov. Experimenty sme uskutočnili na mriežkových grafoch, ktoré slúžia v praxi ako herné mapy. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: algoritmus A*; mriežkový graf; problém hľadania najkratšej cesty; A* search algorithm; grid-based graph; shortest path problem

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

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


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 > Bakalářské práce