Original title:
Procházky v časově proměnlivém grafovém modelu
Translated title:
Walks in time-dymanic graph model
Authors:
Beliš, Marek ; Pangrác, Ondřej (advisor) ; Böhm, Martin (referee) Document type: Bachelor's theses
Year:
2015
Language:
slo Abstract:
[eng][cze] Orienteering with moving control points can be represented as a graph model with ranked vertices and oriented edges. The rank of vertex depends on the actual time. Searching for the most optimised walk through this graph is exponentially difficult problem which can be in real-time solved only with limiting conditions and using of heuristics. SMIK solver software provides implemented heuristics for searching the best walk in several ways. In the thesis we can find description of the problem and algorithms, programming documentation with description of used methods and comparation of results to the real competition. Powered by TCPDF (www.tcpdf.org)Orientační běh s migrujícími kontrolami můžeme reprezentovat grafovým modelem s ohodnocenými vrcholy a orientovanými hranami, kde ohodnocení vrcholů je proměnlivé v čase. Hledání optimální cesty představuje exponenciálně složitý problém, který je v reálnem čase řešitelný jen pomocí omezujících podmínek a heuristik. Program SMIK solver pomocí naimplementovaných heuristik hledá optimální cestu vícero způsoby. V práci najdeme popis problému a algoritmů, programátorskou dokumentaci s popisem metod výpočtu a porovnání výsledků programu s reálnými závody. Powered by TCPDF (www.tcpdf.org)
Keywords:
heuristics; optimization; walks in graphs; heuristiky; optimalizace; procházky v grafech
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/63603