Neoptimální řešení permutačních hlavolamů rozkladem na podproblémy

• Název práce v češtině: Neoptimální řešení permutačních hlavolamů rozkladem na podproblémy
• Název v anglickém jazyce: Non-optimal solver of permutational puzzles using divide and conquer technique
• Akademický rok vypsání: 2005/2006
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: Mgr. Vladan Majerech, Dr.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 15.11.2005
• Datum zadání: 15.11.2005
• Datum a čas obhajoby: 18.09.2006 00:00
• Datum odevzdání elektronické podoby: 18.09.2006
• Datum odevzdání tištěné podoby: 18.09.2006
• Datum proběhlé obhajoby: 18.09.2006
• Oponenti: Mgr. Marta Vomlelová, Ph.D.

Zásady pro vypracování

Cílem práce je program, který z definice permutačního hlavolamu vytvoří algoritmus, řešící daný hlavolam z libovolné počáteční pozice (případně rozhodne, že hlavolam nemá řešení). Program by si měl poradit i s hlavolamy s nerozlišitelnými díly, i s blokačními hlavolamy (hlavolamy, kde je možnost provést pohyb vázaná na aktuální permutaci dílů).

Práce má navrhnout vhodný formát definice hlavolamu.

Vzhledem k počtu konfigurací netriviálních hlavolamů není šance řešit úlohu na grafu všech konfigurací. Typicky je ale možno díly permutačního hlavolamu rozdělit na vzájemně se neovlivňující skupinky. Nalezení posloupnosti P tahů, ovlivňující jednu ze skupinek a neovlivňující druhou vede k možnostem generovat tahy PQP'Q' řešící menší hlavolam (u permutačních hlavolamů předpokládáme, že ke každému tahu X existuje inverzní tah X').

Seznam odborné literatury

http://www.hlavolamy-puzzles.cz
http://www.geocities.com/jaapsch/puzzles/cube3.htm