Věž v Hanoji

Hanojská věž je jedním z oblíbených hlavolamů 19. století . Jsou dány tři pruty, z nichž jeden je navlečen osmi kroužky a kroužky se liší velikostí a menší leží na větším. Úkolem je přenést pyramidu z osmi kroužků co nejmenším počtem tahů na jinou tyč. Najednou můžete nosit pouze jeden prsten a nemůžete umístit větší prsten na menší.

Historie hádanky

Tuto hru vynalezl francouzský matematik Edouard Lucas v roce 1883 [1] , prodávala se jako zábavná hračka. Původně se jmenovala „Profesor Claus z Li-Sou-Stian College“ [1] , ale brzy se zjistilo, že tajemný profesor ze zaniklé vysoké školy není nic jiného než anagram pro jméno vynálezce hry, profesora Luka ( Lucas ze Saint Louis College.

Řešení

Existuje několik přístupů k řešení.

Rekurzivní řešení

Rekurzivně řešíme problém "přenesení věže z n − 1 disků na 2. pin". Poté přesuneme největší disk na 3. kolík a rekurzivně vyřešíme problém „přenést věž z n − 1 disků na 3. kolík“.

Matematickou indukcí tedy docházíme k závěru, že minimální počet tahů potřebných k vyřešení hádanky je 2 n − 1, kde n je počet disků [2] [3] .

V informatice jsou problémy založené na legendě o Hanojské věži často považovány za příklad použití rekurzivních algoritmů a jejich převodu na nerekurzivní.

Řešení "trojúhelník"

Uspořádejte špendlíky do tvaru trojúhelníku. Začněme nejmenším kroužkem a přesuňte jej na libovolnou značku. V budoucnu musí být tento kroužek posunut stejným směrem jako při prvním řazení. Poté přeneseme některé ze zbývajících kroužků (takový tah je pouze jeden), načež opět přeneseme nejmenší kroužek atd. (Je zajímavé, že přečíslováním „kroužků“ v pořadí dosáhneme nečekaného efektu : sudé prstence se budou pohybovat z jednoho vrcholového trojúhelníku do druhého v jednom směru a liché v opačném směru.)

Cyklické rozhodnutí

Označte "1-2" takovou akci: přesuňte disk buď z 1. kolíku na 2., nebo z 2. na 1., podle toho, kde je menší. Poté, abyste vyřešili hádanku se sudým počtem disků, musíte kroky mnohokrát opakovat: 1-2, 1-3, 2-3. Pokud je počet disků lichý - 1-3, 1-2, 2-3.

Aplikace Grayova kódu k řešení

Gray kód , reflexní binární kód v binárním zápisu , ve kterém se dvě sousední hodnoty liší pouze v jednom bitu. Šedý kód byl původně určen k ochraně před falešným ovládáním elektromechanických spínačů. Dnes jsou Grayovy kódy široce používány pro zjednodušení detekce a opravy chyb v komunikačních systémech a také při vytváření zpětnovazebních signálů v řídicích systémech. Kód byl pojmenován po výzkumníkovi Bell Labs Franku Grayovi. Patentoval (číslo 2632058) a použil tento kód ve svém impulsním komunikačním systému.

Šedé kódy lze použít na problém Hanojských věží.
Nechť N je počet disků. Začněme s Grayovým kódem délky N, který se skládá pouze z nul (tedy G 0 ), a budeme se pohybovat podél Grayových kódů (od G i přejít na G i+1 ). Přiřaďme každý i-tý bit aktuálního Grayova kódu i-tému disku (navíc nejméně významný bit odpovídá nejmenšímu disku a nejvýznamnější bit odpovídá největšímu). Protože se v každém kroku změní přesně jeden bit, můžeme změnu bitu i chápat jako pohyb i-tého disku. Všimněte si, že pro všechny disky kromě toho nejmenšího je v každém kroku přesně jeden možný pohyb (kromě počáteční a konečné pozice). Pro nejmenší disk jsou vždy dvě možnosti pohybu, ale existuje strategie pro výběr správného pohybu: pro liché N sled pohybů nejmenšího disku f→t→r→f→t→r→… (kde f je počáteční tyč, t je koncová tyč, r - zbývající tyč) a pro sudé f→r→t→f→r→t→… .

Implementace algoritmů

Příklad algoritmu řešení v C++ :

// Hanojské věže #include <iostream> pomocí jmenného prostoru std ; void hanoi_towers ( int kvantita , int od , int do , int buf_peg ) //množství-počet prstenů, od počáteční pozice prstenů(1-3),do koncové pozice prstenů(1-3) { //buf_peg - mezilehlý kolík (1-3) if ( množství != 0 ) { hanoi_towers ( množství -1 , od , buf_peg , do ); cout << od << " -> " << do << endl ; hanoi_towers ( množství -1 , buf_peg , do , od ); } } int main () { setlocale ( LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Císlo prvního sloupce:" << endl ; cin >> start_peg ; cout << "Císlo konce sloupce:" << endl ; cin >> cílový_peg ; cout << "Číslo mezisloupce:" << endl ; cin >> buffer_peg ; cout << "Pocet disku:" << endl ; cin >> množství_plochy ; hanoi_towers ( plate_quantity , start_peg , destination_peg , buffer_peg ); návrat 0 ; }

Příklad algoritmu řešení v Pascalu :

program hanoibns ( vstup , výstup ) ; var n : celé číslo ; procedura věž ( k : celé číslo ; a , b , c : char ) ; begin if k > 1 then tower ( k - 1 , a , c , b ) ; writeln ( 'od ' , a , ' do ' , b ) ; if k > 1 then tower ( k - 1 , c , b , a ) end ; beginread ( n ) ; _ věž ( n , 'A' , 'C' , 'B' ) konec .

Příklad algoritmu řešení v Haskell :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = krok ( max 0 n ) 1 3 2 [] kde krok 0 _ _ _ odpočinek = klidový krok n f t s rest = krok ( n - 1 ) f s t $ ( f , t ) : krok ( n - 1 ) s t f zbytek

Příklad algoritmu řešení v Pythonu :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) tisk ( 'Přesunout desku z' , A , 'do' , C ) Hanoj ( n - 1 , B , C , A )

Příklad algoritmu řešení v Javě :

public class Hanoi { public static void hanoiVěže ( int množství , int od , int do , int buf_peg ) { if ( množství != 0 ) { hanoiVěže ( množství - 1 , od , buf_peg , do ); Systém . ven . println ( "" + od + " -> " + do ); hanoiTowers ( množství - 1 , buf_peg , do , od ); } } public static void main ( String [] args ) { int start_peg = 1 , destination_peg = 2 , buffer_peg = 3 , plate_quantity = 4 ; hanoiTowers ( množství_plochy , start_peg , destination_peg , buffer_peg ); } }

Příklad iterativního algoritmu řešení v C

#include <stdio.h> #include <math.h> void carryOver ( int , int , int ); hlavní () { int cislo , pocetDisk , pocitac = 1 , pocet ; printf ( "Zadejte počet disků: " ); /* Hanojská věž */ scanf ( "%d" , & číslo ); while ( counter <= pow ( 2 , číslo ) - 1 ) { /* Spusťte smyčku opakování */ if ( counter % 2 != 0 ) { /* Při lichém otočení se dotkneme pouze nejmenšího disku */ printf ( "%3d %d " , čítač , 1 ); carryOver ( číslo , čítač , 1 ); /* Pomocí této funkce určíme pohyb tohoto disku */ } else { /* Určete disk, který se má přesunout rovnoměrným pohybem */ počet = čítač ; pocetDisk = 0 ; while ( počet % 2 == 0 ) { /* Disk pro přesun */ countDisk ++ ; /* bude číslo dělení čísla tahu 2 beze zbytku */ počet = počet / 2 ; } printf ( "%3d %d " , čítač , countDisk + 1 ); carryOver ( číslo , čítač , početDisk + 1 ); } čítač ++ ; } návrat 0 ; } /* Funkce pro detekci pohybu disků */ void carryOver ( int n , int i , int k ) { int t , osaX , osaY , osaZ ; if ( n % 2 == 0 ) { /* Určete pořadí os v závislosti na paritě */ osa X = 1 ; /* a neparitní počet disků */ osa Y = 2 ; osa Z = 3 ; } jinak { osa X = 1 ; osa Y = 3 ; osa Z = 2 ; } /* Číslo tahu může být reprezentováno jedinečným způsobem */ /* jako součin nějakého lichého čísla krát mocnina dvou */ /* k bude číslo disku, který přesouváme */ t = (( i / pow ( 2 , k - 1 )) - 1 ) / 2 ; if ( k % 2 != 0 ) { /* Určení pohybu disku pro lichý pohyb */ switch ( t % 3 ) { /* Vyberte pohyb v závislosti na dané podmínce */ případ 0 : printf ( "%d -> %d \n " , osaX , osaY ); zlomit ; případ 1 : printf ( "%d -> %d \n " , osa Y , osaZ ); zlomit ; případ 2 : printf ( "%d -> %d \n " , osaZ , osaX ); zlomit ; } } else { /* Určete pohyb disků pro rovnoměrný pohyb */ přepínač ( t % 3 ) { případ 0 : printf ( "%d -> %d \n " , osaX , osaZ ); zlomit ; případ 1 : printf ( "%d -> %d \n " , osaZ , osa Y ); zlomit ; případ 2 : printf ( "%d -> %d \n " , osaY , osaX ); zlomit ; } } }

Existují programy pro vizualizaci řešení této hádanky.

Možnosti

Se čtyřmi nebo více tyčemi

Přestože varianta se třemi pruty má jednoduché rekurzivní řešení, optimální řešení pro Hanojskou věž se čtyřmi pruty bylo dlouho neřešeným problémem.

Je zřejmé, že pro libovolný počet tyčí existuje algoritmus pro nalezení optimálních řešení, stačí znázornit hádanku jako neorientovaný graf, přiřazovat vrcholy k umístění disku a hrany k tahům a použít libovolný vyhledávací algoritmus (např. prohledávání do šířky ), abyste našli optimální řešení. Neexistuje však účinná strategie pro nalezení optimálního řešení pro velký počet disků: počet tahů potřebných k vyřešení hádanky s 10 tyčemi a 1000 disky zůstává neznámý.

Existuje údajně optimální Frame-Stewartův algoritmus vyvinutý v roce 1941 [4] . Související Frame-Stewartův dohad uvádí, že Frame-Stewartův algoritmus vždy najde optimální řešení. Optimálnost Frame-Stewart algoritmu byla experimentálně ověřena až na 30 kotoučích na 4 tyčích [5] . V roce 2014 se konečně ukázalo, že pro čtyři pruty je optimální algoritmus Frame-Stewart [6] .

O dalších variantách řešení čtyřtyčové Hanojské věže pojednává přehledový článek Paula Stockmayera [7] .

Frame-Stewartův algoritmus

Algoritmus Frame-Stewart, který poskytuje optimální řešení pro čtyři a údajně optimální řešení pro více prutů, je popsán následovně:

Nechť je počet disků. $n$
Nechť je počet tyčí. $r$
Definujme to jako nejmenší počet pohybů potřebných k přenosu n disků pomocí r tyčí. $T(n,r)$

Algoritmus lze popsat rekurzivně:

Pro některé , , přeneste ty horní na pivot i , který není ani počáteční, ani konečný pivot, za to utrácejte tahy. $k$ $1\leq k<n$ $k$ $T(k,r)$
Bez použití tyče i , která nyní obsahuje horní disky, přeneste zbývající disky na finální tyč, použijte pouze zbývající tyče a utrácejte pohyby. $k$ $nk$ $r-1$ $T(nk,r-1)$
Nakonec přesuňte horní disky ke koncové tyči a utrácejte za to tahy. $k$ $T(k,r)$

Celý proces vyžaduje pohyby. Hodnota je zvolena tak, aby hodnota tohoto výrazu byla minimální. V případě 4 tyčí je optimální , kde je funkce nejbližšího celého čísla . [osm] $2T(k,r)+T(nk,r-1)$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Legendy

Legenda vynalezená profesorem Lucou říká, že ve Velkém chrámu města Benares , pod katedrálou označující střed světa , je bronzový kotouč, na kterém jsou upevněny 3 diamantové tyče, jeden loket vysoké a tlusté jako včela. . Kdysi dávno, na samém počátku času, byli mniši tohoto kláštera vinni před bohem Brahmou. Rozzuřený Brahma vztyčil tři vysoké tyče a na jednu z nich umístil 64 kotoučů z čistého zlata. A to tak, že každý menší disk leží na větším.

Jakmile se všech 64 kotoučů přenese z tyče, na kterou je Brahma při tvoření světa položil, na jinou tyč, věž spolu s chrámem se promění v prach a svět zahyne pod hromovým zvoněním.

Počet posunů v závislosti na počtu zazvonění se vypočítá podle vzorce . $2^{n}-1$

Počet pohybů disků, které musí mniši provést, je 18 446 744 073 709 551 615 . Pokud by mniši, pracující ve dne v noci, provedli jeden pohyb disku každou sekundu, jejich práce by pokračovala téměř 585 miliard let .

V kultuře

V povídce Erica Franka Russella „Your Move“ (Now Inhale, v jiném překladu – „The Game of Survival“) [9] , aby hlavní hrdina oddálil popravu mimozemšťany, zvolí si hlavní hrdina hru Hanojská věž. s 64 disky jako poslední hra. Oznámená pravidla byla upravena pro dva hráče – hráči musí po jednom přehazovat kotouče, vítězí ten, kdo udělá poslední tah. Hrdina nazývá tuto hru „arki-malarki“ a přísahá, že tuto hru hrají „kněží chrámu Benares“ na Zemi.

Ve filmu Rise of the Planet of the Apes je Hanojská věž použita jako test inteligence testovacích subjektů. Opice dokončí hádanku se čtyřmi kroužky za dvacet tahů.

Hanojská věž je jednou z tradičních hádanek ve videohrách kanadské společnosti BioWare – konkrétně „ Jade Empire “, „ Star Wars: Knights of the Old Republic “, „ Mass Effect “ a „ Dragon Age: Inquisition “. . Setkají se také v questu Legend of Kyrandia II.

Poznámky

↑ 1 2 Martin Gardner, Matematické hádanky a zábava
↑ Petkovic, Miodrag. Slavné hádanky velkých matematiků (neopr.) . - Knihkupectví AMS, 2009. - S. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Konkrétní matematika : základ pro informatiku . - Addison-Wesley , 1998. - S. 21. - ISBN 0201558025 .
↑ Řešení pokročilého problému 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. a Ariel Felner. Nedávný pokrok v heuristickém vyhledávání: případová studie problému čtyřkolíkových věží v Hanoji // IJCAI : deník. - 2007. - S. 2324-2329 . Archivováno z originálu 24. září 2015.
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. Belg. Matematika. soc. Simon Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variace na čtyřsloupovou Hanojskou věž Puzzle (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ University of Toronto CSC148 Slog (5. dubna 2014). Staženo: 22. července 2015. (neurčitý)
↑ Russell, Eric Frank. Váš tah // Pokud . - 1994. - Duben. - S. 34-42 . (Ruština)

Viz také

Test Tower of London

Odkazy

sekvence A007664 v OEIS
Konstantin Knop. Hanojská věž . Živly (22. října 2012). (neurčitý)
Online hra Towers of Hanoi

Tematické stránky	Obří bomba
Slovníky a encyklopedie	Britannica (online) Britannica (online)
V bibliografických katalozích	NKC : ph1060364