Original title: Hledání cesty v mřížkových grafech
Translated title: Grid-Based Path Planning
Authors: Novella, Tomáš ; Balyo, Tomáš (advisor) ; Martínek, Vladislav (referee)
Document type: Bachelor's theses
Year: 2013
Language: slo
Abstract: [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)
Keywords: A* search algorithm; grid-based graph; shortest path problem; algoritmus A*; mriežkový graf; problém hľadania najkratšej cesty

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/56469

Permalink: http://www.nusl.cz/ntk/nusl-497084


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses