Název:
Algoritmy pro řešení hry Sokoban
Překlad názvu:
Algorithms for solving the Sokoban game
Autoři:
Galajda, Martin ; Petříček, Martin (oponent) ; Surynek, Pavel (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2009
Jazyk:
slo
Abstrakt: [eng][cze] The task of this work is to bring a complete guide for solving a SOKOBAN game problem. The work follow subsequently issues of studies of problem complexity, its definition, selection of appropriate algorithms, as well as their implementation and testing. The study demonstratethe manifest, that problem belongs to a NP-hard set of problems as well as PSPACE-complete set of problems. Fundamental and also advanced techniques of state space searching are studied as means for solving defined problem, memory and time characteristics of these techniques are presented and derived. In order to gain statistical information about efficiency of demonstrated algorithms and heuristics, an aplication SokobanSolver was built. This program can solve many SOKOBAN problems automatically. We described principles of functional parts and main data structures of this program and also we discuss program SokobanGenerator, aplication that was built to supply SokobanSolver with many random built SOKOBAN problems. Techniques explained are tested by lately named programs, and results are discussed at the very end of the paper.Cieľom práce je priniesť uceleného sprievodcu problémom riešenia hry SOKOBAN. Práca sa zaoberá postupne problematikami definície problému, štúdiami jeho náročnosti, výberom vhodných algoritmov, a napokon aj ich implementáciou a testovaním. Štúdia demonštruje známe dôkazy NPzložitosti a PSPACE-úplnosti problému. Neskôr sa práca venuje výberu a charakteristike vhodných algoritmov na riešenie problému. V rámci práce tiež vznikol program SokobanSolver, riešiaci množstvo bludísk hry SOKOBAN automaticky. Ukážeme si, ako sa tento program používa a ako funguje. Pozrieme sa tiež na program SokobanGenerator, ktorý vznikol ako podpora programu SokobanSolver. Tento program vytvára veľké množstvo náhodných bludísk, ktoré slúžia ako zdroj problémov programu SokobanSolver. Na konci práce sú uvedené údaje získané programom SokobanSolver. Bolo porovnané veľké množstvo riešení bludísk. Výsledky sú graficky spracované a diskutované. Najzaujímavejšie výsledky sú zhrnuté v závere celej práce.