Hanojské věže

Hanojské věže jsou zdánlivě jednoduchý dřevěný hlavolam vhodný pro trénink myšlení dětí. Ovšem málokterý hlavolam se dostane do učebnic, natožpak do učebnic dvou tak odlišných oblastí, jako je psychologie a programování. A málokterý hlavolam, který se vyskytuje v základních učebnicích, skrývá nevyřešené matematické problémy. Ale vezměme to od začátku, nebo v tomto případě spíše od konce, tedy od konce světa.

Kdesi v horách nedaleko Hanoje prý¹⁾ od dávných věků stojí chrám, ve kterém je velká místnost, v ní jsou tři kolíky a na nich je nasazeno celkem 64 zlatých disků různých velikostí. Mniši přesouvají tyto zlaté disky podle posvátných pravidel, a až se jim podaří přemístit všechny disky z prvního kolíku na třetí, nastane konec světa.

Pravidla jsou jednoduchá. Disky je povoleno přesouvat pouze po jednom a vždy můžeme vzít pouze horní disk z některého kolíku a přemístit jej na jiný kolík, přičemž nikdy nesmíme položit větší disk na menší (obr. 1). Postup řešení zde nebudeme detailně rozebírat,²⁾ raději se podíváme na mezioborové souvislosti této úlohy.

Jak lidé myslí

První oblastí, kde hrají Hanojské věže důležitou roli, je kognitivní věda. Herbert Simon, jeden z průkopníků této oblasti, nabízí následující srovnání: „Pokud šachy hrají v kognitivním výzkumu podobnou roli jako Drosophila v genetice, Hanojské věže představují analogii E. coli, poskytující další standardizovaný model, kolem kterého se mohou kumulovat vědomosti.“

Hanojské věže se využívají pro zkoumání toho, jak lidé řeší problémy. Zkoumá se zlepšování dovedností vlivem tréninku, přenos znalostí mezi úlohami či myšlení pacientů s poškozením mozku. Konkrétně se například studuje vliv formulace zadání na způsob a obtížnost řešení problému. K tomu se využívají „izomorfní zadání“, ve kterých vystupují skákající akrobati, čajové rituály, vrstvy nátěrů barvy na nábytku nebo příšery měnící velikost koulí (viz rámeček „Příšery a glóbusy“). Ve všech případech je zadání formulováno tak, že problém je izomorfní původnímu zadání Hanojských věží, tj. když odhlédneme od „příběhové omáčky“, je stavový prostor platných tahů stejný jako stavový prostor klasických Hanojských věží (obr. 2). Pro lidi však není úplně snadné tento izomorfismus odhalit a obtížnost jednotlivých zadání se výrazně liší. Úloha uvedená v rámečku trvá lidem průměrně šestnáckrát déle než základní zadání. Proč? Roli hraje způsob, jak lidé přemýšlejí o problémech, využívají omezenou pracovní paměť a další faktory – prostě úloha poskytuje dostatek podkladů pro zajímavý kognitivní výzkum.

Experimenty s izomorfními zadáními bychom však mohli dělat s ledajakou úlohou. Čím jsou zrovna Hanojské věže zajímavé? Především svým „zanořeným“ charakterem. Podobně jako matrjoška, kterou otevřeme, abychom našli další matrjošku, zjistíme při řešení Hanojských věží pro n disků, že potřebujeme vyřešit Hanojské věže pro n – 1 disků. Abychom mohli přesunout spodní disk, musíme nejdřív přesunout disky nad ním, což vlastně odpovídá trochu jednodušší verzi zadání. Při řešení využíváme takzvanou „analýzu prostředků a cílů“, což je jeden z obecných způsobů, jakým lidé řeší problémy. Příklad ze života: chci jet lyžovat (cíl), na hory se mohu dostat vlakem (podcíl), abych mohl jet vlakem, musím na nádraží (podpodcíl), na které se dostanu tramvají (prostředek). Exaktně studovat, jak lidé přemýšlejí o cestě na hory, je ovšem náročné, a tak psychologové rádi sáhnou po Hanojských věžích.

Ovšem nejen psychologové. Techniku „analýza prostředků a cílů“ uvedli do obecného povědomí dva průkopníci umělé inteligence: již zmíněný Herbert Simon³⁾ spolu s Allanem Newellem. Tuto techniku využili jako základ svého programu General Problem Solver, což byl jeden z prvních vážnějších pokusů o vybudování umělé inteligence v padesátých a šedesátých letech. Hanojské věže byly jedním z problémů, na kterých byl tento program vyvíjen, testován a srovnáván s lidmi.

Rekurze aneb Volání sebe sama

Tím se dostáváme k informatice a programování – informatický termín pro zmíněnou zanořenou strukturu problému je rekurze (což znamená „volání sebe sama“). Řešení úlohy pro n disků totiž můžeme zapsat programem na 5 řádků pomocí rekurzivního volání téhož programu pro n – 1 disků, a právě díky tomuto jednoduchému elegantnímu zápisu se Hanojské věže často používají při výuce programování. Stejně jako řešení úlohy má i stavový prostor⁴⁾ úlohy rekurzivní charakter (obr. 2).

Stavový prostor tvoří spojnici k matematice a k dalším strukturám, které jsou definovány rekurzivně. S rostoucím počtem disků začíná obrázek stavového prostoru nápadně připomínat Sierpińského fraktál (obr. 3), což je geometrický útvar, který vzniká rekurzivní procedurou. Začneme s plným trojúhelníkem, rozdělíme ho na 4 identické malé trojúhelníky, prostřední vyřízneme a na zbylé tři aplikujeme rekurzivně stejný postup. Obrázek ilustruje první 4 kroky tohoto postupu. Sierpińského fraktál vznikne po provedení nekonečného počtu uvedených rekurzivních kroků. To sice není úplně praktický postup, nicméně z matematického pohledu je výsledek takové operace dobře definovaný a výsledný objekt má mnoho zajímavých vlastností.⁵⁾ Souvislost mezi stavovým prostorem Hanojských věží a Sierpińského fraktálem není jen na úrovni podobně vypadajících obrázků – lze ji přesně popsat, a dokonce můžeme i dokázat vlastnosti jednoho z těchto objektů pomocí druhého. Tak například s využitím této analogie bylo dokázáno, že průměrná vzdálenost dvou bodů v Sierpińského fraktálu se základnou 1 je 466/885.⁶⁾

Jinou zajímavou a nečekanou souvislostí je známý Pascalův trojúhelník (obr. 4). Ten lze také vyjádřit pomocí rekurzivního vztahu a právě tato rekurze tvoří spojovací můstek se stavovým prostorem Hanojských věží a Sierpińského fraktálem. Pokud si totiž v Pascalově trojúhelníku obarvíme lichá čísla, dostaneme opět povědomý obrázek. Čím víc řádků obarvíme, tím bude podobnější Sierpińského fraktálu.

Problém, který stojí za útok

Kromě uvedených známých matematických výsledků a spojitostí však Hanojské věže skrývají i matematické problémy, jejichž řešení stále není známo. Co se stane, když místo tří kolíků použijeme čtyři? Vyřešit úlohu je pak samozřejmě jednodušší, protože prostě máme více volnosti při řešení. Jenomže správného matematika nezajímá jenom řešení úlohy, ale nejlepší řešení. Kolik nejméně tahů potřebujeme na vyřešení úlohy s n disky? Pro zadání s 3 kolíky je odpověď známá – optimálního výsledku dosahuje základní rekurzivní řešení a potřebný počet tahů je 2ⁿ – 1.⁷⁾ Pro zadání se 4 disky existuje algoritmus,⁸⁾ o kterém si většina matematiků myslí, že dává optimální řešení, nikdo to však neumí dokázat. Zatím bylo pouze pomocí systematického počítačového prohledávání ověřeno řešení pro 30 a méně disků. Paul Erdős, jeden z největších matematiků 20. století, prohlásil: „Problémy, které stojí za útok, prokážou svoji cenu tím, že útok opětují.“ Hanojské věže, i přes svou jednoduchost, svoji cenu rozhodně prokázaly.