Return to search

Sub-optimální algoritmy pro řešení úloh o přesouvání kamenů / Sub-optimal algorithms for solving sliding puzzles

Title: Sub-optimal algorithms for solving sliding puzzles Author: Petr Michalík Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D. Supervisor's e-mail address: Pavel.Surynek@mff.cuni.cz In the present work techniques for solving the so-called sliding tiles puzzles, which generate optimal or sub-optimal solution, are studied. This thesis focuses especially on a specific variant of the puzzle: the (n^2-1)-puzzle. This work shows and compares current methods for solving this type of problem. A choosen method is a subject to a close analysis of complexity and is also implemented so that theoretical and experimental results could be confronted. An alternative sub-optimal algorithm is proposed and its theoretical analysis is presented. This algorithm is implemented as well and is compared with the existing algorithm. Both the theoretical analysis and the test results show that better (shorter) solutions can often be obtained using this alternative algorithm.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:295925
Date January 2011
CreatorsMichalík, Petr
ContributorsSurynek, Pavel, Hric, Jan
Source SetsCzech ETDs
LanguageCzech
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0017 seconds