Aktuální číslo:

2017/12

Téma měsíce:

Kontakty

Hanojské věže

Interdisciplinární hádanka
 |  9. 9. 2010
 |  Vesmír 89, 544, 2010/9

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ý1) 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,2) 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 Simon3) 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ý prostor4) ú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í.5) 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.6)

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 2n – 1.7) Pro zadání se 4 disky existuje algoritmus,8) 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.

Poznámky

1) Ve skutečnosti hádanka pochází z 19. století a autorem je francouzský matematik Édouard Lucas. Nicméně tato legenda tvoří tradičně nedílnou součást zadání.

2) Čtenáři, který úlohu nezná, doporučujeme, aby si vyzkoušel úlohu vyřešit pro 4 disky. V případě nedostatku zlatých disků lze použít například mince.

3) Těžko zařadit Herberta Simona do jedné disciplíny. Kromě toho, že stál u základů umělé inteligence a věnoval se kognitivní psychologii, dostal třeba také Nobelovu cenu za ekonomii.

4) Stavový prostor zachycuje všechny možné konfigurace problému a přechody mezi nimi.

5) Výsledný fraktál například není – na rozdíl od vyplněného trojúhelníku, s nímž jsme začínali – dvourozměrný útvar, ale jednorozměrná křivka, která má navíc tu vlastnost, že protíná sama sebe v každém bodě.

6) Ian Stewart o tomto číslu říká, že by je každý měl mít na „seznamu čísel, která jsou důležitější, než vypadají“, společně s pí, e, zlatým řezem a dalšími.

7) Z čehož mimo jiné plyne, že s tím koncem světa to nebude až tak aktuální. I kdyby mniši přenesli 1 disk za vteřinu, tak se 64 disky dokončí úlohu za 580 miliard let, což je 40krát delší období než dosavadní stáří vesmíru.

8) Tzv. Frame-Stewartův rekurzivní algoritmus.

Ke stažení

OBORY A KLÍČOVÁ SLOVA: Matematika

O autorovi

Radek Pelánek

Mgr. Radek Pelánek, Ph.D., (*1980) vystudoval Fakultu informatiky Masarykovy univerzity v Brně. V současné době působí tamtéž jako odborný asistent a zkoumá mimo jiné to, jak lidé řeší problémy a jak jim v tom počítače mohou pomáhat (např. tím, že jim doporučí úlohu vhodné obtížnosti). V roce 2011 vycházejí dvě jeho nové knihy: Jak to vyřešit (Portál) a Modelování a simulace komplexních systémů (Nakladatelství MU).

Doporučujeme

Přemýšlej, než začneš kreslit

Přemýšlej, než začneš kreslit

Ondřej Vrtiška  |  4. 12. 2017
Nástup počítačů, geografických informačních systémů a velkých dat proměnil tvorbu map k nepoznání. Přesto stále platí, že bez znalosti základů...
Tajemná „Boží země“ Punt

Tajemná „Boží země“ Punt uzamčeno

Břetislav Vachala  |  4. 12. 2017
Mnoho vzácného zboží starověkého Egypta pocházelo z tajemného Puntu, kam Egypťané pořádali časté obchodní výpravy. Odkud jejich expedice...
Hmyz jako dokonalý létací stroj

Hmyz jako dokonalý létací stroj

Rudolf Dvořák  |  4. 12. 2017
Hmyz patří k nejdokonalejším a nejstarším letcům naší planety. Jeho letové schopnosti se vyvíjely přes 300 milionů let a předčí dovednosti všech...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné