Hanojské věže

Hanojské věže (původně Hanojská věž ) je logická hra, kterou si představil francouzský matematik Édouard Lucas a která spočívá v přemísťování disků různých průměrů z „odletové“ věže do „příletové věže“. věž, a to v minimu tahů, při respektování následujících pravidel:

Předpokládá se, že toto poslední pravidlo je respektováno také ve výchozí konfiguraci.

Původ problému

Matematický problém věží Hanoje vynalezl Édouard Lucas . Je vydáván ve svazku 3 jeho Récréations mathiques , publikovaném posmrtně v roce 1892 . Oznámil, že tento problém je způsoben jedním z jeho přátel, N. Clausem de Siamem ( anagramem Lucase d'Amiensa, jehož rodištěm je Amiens), údajným profesorem na vysoké škole Li-Sou-Stian (anagramem Saint Louis , střední škola, kde Lucas učil).

Pod názvem „  Brahmové padají  “ Lucas vypráví, že „N. Claus ze Siamu viděl na svých cestách za vydáním spisů proslulého Fer-Fer-Tam-Tama ve velkém chrámu v Benares , au pod kopulí, která označuje střed světa, tři diamantové jehly, zasazené do měděné desky, vysoké loket a velké jako tělo včely. Na jednu z těchto jehel navlékl Bůh na začátku století 64 kotoučů z čistého zlata, největší spočívající na mosazi, a ostatní, stále více úzké, navrstvené na vrchol. Je to posvátná věž Brahmâ . Ve dne v noci se kněží navzájem sledovali po schodech oltáře, zaneprázdněni přepravou věže z první jehly na třetí, aniž by se odchýlili od pevných pravidel, která jsme právě naznačili a která stanovila Brahma. Až bude po všem, věž a bráhmani padnou a bude to konec světů! " .

Jak je ukázáno níže, hra na 64 discích vyžaduje minimálně 264 -1 tahů. Za předpokladu, že přesunutí disku trvá 1 sekundu, což činí 86 400 tahů denně, by hra skončila přibližně po 213 bilionech dní, což je zhruba ekvivalent 584,5 miliardy let, což je 43násobek odhadovaného stáří vesmíru (13,7 miliardy podle některých zdrojů).

Počet uskutečněných cest

Je snadné demonstrovat indukcí, že pokud n je počet disků, k dosažení jeho konců je zapotřebí nejméně 2 n - 1 tahů, což je množství, které se s n velmi rychle zvyšuje . Nechť A, B a C jsou tři místa věží; označte x n počet přemístění disků potřebných k přemístění celé věže. Chcete-li přesunout věž n disků z A do C, provedeme tyto tři kroky:

Počet přemístění disků tak ověřuje vztah opakování:

což dává dobře

Můžeme ukázat, že zde popsaná metoda poskytuje optimální posloupnost (ta, která vyžaduje nejméně tahů) a že tato je jedinečná. Ve skutečnosti, abychom přesunuli věž n disků z A do C, musíme nutně najednou nebo později přesunout největší disk z A do C, abychom to mohli udělat, musíme mít naskládaných prvních záznamů n -1 v B .

Algoritmické rozlišení

Rekurzivní řešení

Problém věží Hanoji je vidět v algoritmické ( programování ), kde se nabízí příklad síly a čitelnosti rekurzivně definovaných programů (dalším příkladem toho, že strom třídění ). Metoda rozlišení, která byla vidět dříve, skutečně vede k rekurzivnímu algoritmu popsanému níže. Parametry postupu v Hanoji jsou:

procédure Hanoï(n, D, A, I) si n ≠ 0 Hanoï(n-1, D, I, A) Déplacer le disque de D vers A Hanoï(n-1, I, A, D) fin-si fin-procédure Zobecněný algoritmus v jakékoli poloze

Můžeme zobecnit rekurzivní rozlišení v případě, že jsou disky zpočátku uspořádány náhodně na třech místech, spíše než naskládány na první (počáteční poloha je libovolná). Cílem bude seskupit n disků v cílovém umístění A. Číslujeme n disků od 1 do n v pořadí zvětšující se velikosti a označíme P k pozici disku očíslovaného k . Začneme z následujícího pozorování: v určitém okamžiku bude nutně nutné přesunout největší disk z P n na A. Rekurzivní uvažování je pak podobné jako u předchozího:

  • skupina se první n -1 disky v mezilehlé poloze I (ten, který není ani ani P n );
  • přesunout největší disk z P n do A;
  • seskupit první n -1 disky v A.

Na rozdíl od výše popsaného konkrétního případu závisí výchozí umístění na uspořádání disků. Musíme také rozlišit případ, kdy je disk n již na správném místě (P n = A). V tomto případě by sledování předchozí metody nebylo optimální: druhý krok je zbytečný a první a třetí krok můžeme sloučit přímým seskupením prvních n -1 disků v A.

Zobecněný algoritmus se proto stává:

procédure Hanoï-généralisé(n, A) si n ≠ 0 si Pn = A Hanoï-généralisé(n-1, A) sinon Hanoï-généralisé(n-1, I) Déplacer le disque de Pn vers A Hanoï-généralisé(n-1, A) fin-si fin-si fin-procédure

Všimněte si, že poslední rekurzivní volání může být nahrazeno voláním Hanojské procedury konkrétního případu viděného dříve, protože všechny první disky n -1 jsou poté naskládány na I.

Se stejným uvažováním jako výše ukážeme, že tento algoritmus poskytuje jedinečnou optimální sekvenci. Počet zásahů můžeme vyjádřit jako funkci počtu n disků, jejich uspořádání a umístění A příjezdu: označíme to y n (A).

  • Pokud je disk n již dobře umístěn, pak je počet tahů y n-1 (A), protože jsme spokojeni s přesunem prvních n -1 disků v A;
  • jinak je počet tahů buď .

Proto máme následující relaci opakování:

Můžeme pak vyjádřit y n (A) jako součet mocnin 2, kde je termín přidán právě tehdy, když je odpovídající disk ztracen:

kde b k je 0, pokud je disk k dobře umístěn, 1 jinak.

V nejhorším případě jsou všechny disky ztraceny. Máme tedy . Je zajímavé poznamenat, že obvyklá počáteční situace je jedním z těch nejhorších případů.

Iterační řešení

Existuje také iterační postup, jak optimálně vyřešit problém věží v Hanoji. Spočívá v postupném provádění následujících dvou pohybů a označení tří zatáček (zleva doprava) A, B, C:

  • přesunout nejmenší disk z jednoho místa na další (například z A do B, z B do C, z C do A);
  • přesunout další disk;

a pokračovat v těchto dvou přemístěních iteračně, dokud není přemístěna celá věž, přičemž poslední přemístění je pak omezeno na nejmenší disk v horní části věže. Akce „přesunout další disk“ je jednoznačná, protože kromě nejmenšího disku je možný pouze jeden pohyb disku.

Na rozdíl od rekurzivního postupu iterativní postup nepoužívá žádné zapamatování stromu posunů, které má být provedeno, a vyžaduje pouze zapamatování, zda musíme pohybovat nejmenším diskem nebo ne, a ve kterém směru se provádějí posuny malého disku ... Rovněž umožňuje kdykoli se vrátit do původní situace: stačí obrátit směr, ve kterém se pohybuje nejmenší disk. Důvody, proč tento algoritmus řeší problém, jsou však méně zjevné než u rekurzivního algoritmu.

Můžeme to vysvětlit tím, že si všimneme, že v optimálním řešení nutně přesuneme nejmenší disk přesně jednou za dva, protože pohybovat dvakrát za sebou by nebylo optimální, a pohybovat také druhým diskem dvakrát za sebou. Jak přesuneme tento menší disk, zbývá určit.

Předpokládejme, že věž n disků je zpočátku na místě A a že ji chceme přesunout na místo C. Indukcí na n ukážeme , že iterace dvou výše popsaných pohybů produkuje optimální sekvenci, pokud směr, ve kterém menší disk je přesunut je A → B → C → A (zleva doprava) pro sudé n , nebo A → C → B → A (zprava doleva) pro liché n . Vskutku :

  • Pro n = 1 stačí přesunout jeden disk z A do C.
  • Předpokládejme vlastnost prokázanou pro posunutí n -1 disků. Stejně jako v rekurzivním případě přesuneme věž n disků přesunutím n -1 horních disků z A do B, poté velkým diskem z A do C, poté n -1 disků z B do C.
    • Pokud je n sudé, pak n -1 je liché a podle indukční hypotézy (výměnou rolí C a B) se při přesunu hromádky n -1 horních disků z A do B provede posun na dvou nejmenším diskem v pořadí A → B → C → A → ... → A → B. Poté přesuneme velký disk z A do C (posun, který následuje po posledním posunutí nejmenšího disku). Poté přesuneme n -1 disků z B do C, přičemž každé druhé posunutí provede menší disk, tentokrát v pořadí B → C → A → B → ... → B → C. Nakonec jsou následující pohyby malého disku bude A → B → C → A →… → B, pak B → C → A →… → C, nejmenší disk se bude přesouvat pokaždé.
    • Ověření je analogické, pokud n je liché.

Další iterativní řešení

Předpokládejme věže očíslované 1, 2 a 3.

Posun z věže č. I do věže č. J je zaznamenán i + j.

Posun 3 tedy označuje jak posun věže 1 směrem k věži 2, tak věže 2 směrem k věži 1, ale není zde žádná dvojznačnost: nejmenší disk bude umístěn na největší.

Podobně posun 4 označuje jak posun věže 1 směrem k věži 3, tak věže 3 směrem k věži 1.

A nakonec posun 5 označuje jak posun věže 2 směrem k věži 3, tak věže 3 směrem k věži 2.

Když je počet disků sudý, pohyby, které mají být provedeny, jsou 3,4,5,3,4,5,3,4,5 ... tolikrát, kolikrát je potřeba (posloupnost 3,4,5 se opakuje krát).

Pokud je počet disků lichý, je třeba provést posunutí 4,3,5,4,3,5, ... tolikrát, kolikrát je potřeba (sekvence 4,3,5 se opakuje, pak končí posunutí z věže 1 do věže 3).

Třetí iterativní řešení

Předpokládejme, že disky jsou střídavě zbarveny černě do bílé. Pro větší pohodlí se také předpokládá, že základny tří prutů jsou zbarveny černě nebo bíle. Základna, která podporuje počáteční věž, je zbarvena jinou barvou, než je barva největšího disku, aby respektovala střídání barev. Další dvě základny jsou jedna černá, druhá bílá. Disky jsou iterativně přesunuty podle následujících dvou pravidel:

  • Nikdy neprovedete pohyb, který přímo zruší poslední pohyb, který jste právě provedli.
  • Přesuneme jediný disk, který lze umístit na disk nebo na základnu jiné barvy.

Prohlídky Hanoje a Pascalova trojúhelníku

Můžeme reprezentovat hru Hanojských věží abstraktním grafem , přičemž každý vrchol grafu představuje možné uspořádání N disků na třech otáčkách, hrana spojující dva vrcholy, pokud existuje pohyb disku umožňující průchod z uspořádání, představované jedním z vrcholů, k druhému. Označení vrcholů je založeno na poloze disků v uspořádání, které představuje: čteme zleva doprava, do které věže každý disk patří, počínaje pozicí největšího disku.

Diagram ukazuje herní strom se třemi disky. Počáteční pozice je umístěna na jednom vrcholu trojúhelníku, například AAA, konečná poloha je na jiném vrcholu, BBB nebo CCC. Barva okrajů označuje disk, který se má pohybovat: červená pro nejmenší disk, žlutá pro mezilehlý disk a modrá pro velký disk.

Ukazujeme, že pro všechna N je graf věží Hanoje s N disky totožný s grafem získaným z Pascalského trojúhelníku řádu 2 N , kde spojíme liché binomické koeficienty hranou.

Aplikace

Úkol věže v Hanoji se používá ve výzkumu psychologie , zejména při řešení problémů . Používá se také jako neuropsychologický test .

Tento úkol je citlivý na frontální a prefrontální dysfunkce .

Tento test tedy umožňuje vyhodnocení výkonných funkcí , jako je plánování , pracovní paměť a inhibice .

Výkon na Hanojské věži závisí na schopnostech inhibice , pracovní paměti , procedurální paměti a inteligenční tekutině.

Avšak inhibice vyžaduje potlačení aktivity v primární motorické kůry , z na pravé dolní frontální mozkové kůry a motorového prostoru dodatečně. Pracovní paměť znamená dorso-boční část frontální mozkové kůry , která umožňuje účinnou manipulační a kontrolní informace. Stejně tak plánování koreluje s aktivací dorzální části prefrontální kůry , parietální a premotorické kůry a mozečku.

Chápeme, proč je Hanojská věž citlivá na frontální a prefrontální dysfunkce.

Tento test je blízký testu testu Tower of London i testu Toronto Towers.

Poznámky, reference a bibliografie

Poznámky

  1. Přesný název brožury Édouarda Lucase zněl: „Hanojská věž, skutečná annamská hádanka.“ Hra přivezená z Tonkina profesorem N. Clausem (ze Siamu), mandarínkou na Li-Sou-Stian College “ .
  2. Přesný počet potřebných sekund (18 446 744 073 709 552 000) se rovná počtu zrn pšenice požadovaných podle jiné indické legendy Brahmin Sissou od krále Belkiba jako odměna za to, že vynalezl šachovou hru , který se hraje na 64 polích.
  3. Chcete-li vyřešit obecnější problém, kolik tahů musí být provedeno k přesunutí n disků pomocí jiného počtu tahů než tři, viz JSFrame, BMStewart, Řešení měsíčního problému 3918 , Amer. Matematika. Měsíčně 48 (1941) 216-219.

Reference

  1. Édouard Lucas, Mathematical Recreations , svazek 3, (1892), přetištěno v knihkupectví Alberta Blancharda, (1979), str.  58
  2. Jean-Paul Delahay, Hanojské věže, více než dětská hra , Pour la Science, č. 457, (listopad 2015), s. 108-112
  3. AMHinz, Pascalův trojúhelník a věž v Hanoji , Amer. Matematika. Měsíc 9 (1992) 538-544
  4. (en) V. Goel a J. Grafman: „  Jsou frontální laloky zapojeny do plánovacích funkcí? Interpretace dat z Hanojské věže.  » , Neuropsychology , sv.  33, n o  5,1995, str.  623-642
  5. (in) DT Stuss a DF Benson, „  Neuropsychologické studie čelních laloků  “ , Psychological Bulletin , sv.  95, n o  1,1984, str.  3-28
  6. (in) Goldstein a Green FC, RC, „  Hodnocení řešení problémů a výkonných funkcí. Klinické neuropsychologické hodnocení: Kognitivní přístup.  » , Kritické problémy v neuropsychologii ,1995, str.  49–81
  7. (in) V. Goel, SD Pullara a Grafman J., „  Výpočtový model dysfunkce frontálního laloku: Pracovní paměť a úkol z Hanoje  “ , Cognitive Science , sv.  25, n O  22001, str.  287-313
  8. (in) Pennington, BF Bennetto, L., McAleer a O. Roberts Jr., Pozor, paměť a výkonná funkce: Výkonné funkce a pracovní paměť: Teoretické a měřící problémy , Baltimore,1996, 327–348  s.
  9. (in) MC Welsh, T. Satterlee Cartmell a Mr. Stine, „  Towers of Hanoi and London: Contribution of working memory and inhibition to performance  “ , Brain and Cognition , sv.  41, n O  21999, str.  231-242
  10. (v) SJ Handley Capon A. C. a Harper, "  Podmíněné uvažování a věž Hanoi: Role prostorové a verbální pracovní paměti  " , British Journal of psychologie , n O  932002, str.  501-518
  11. (in) A. Bagley, C. Welsh, P. a E. Retzlaff Bryan, „  Towers of Hanoi and London: Contribution of procedural learning and inhibition  “ , Journal of the International Neuropsychological Society , sv.  8, n O  22002, str.  229
  12. (in) S. Devine, MC Welsh, P. Retzlaff, pan Yoh a C. Adams, „  Explicitní a implicitní kognitivní procesy ovlivňující výkon Tower of Hanoi  “ , Journal of the International Neuropsychological Society , sv.  7, n O  22001, str.  250
  13. (en) Zandbelt B., M. Bloemendaal, J. Hoogendam, R. Kahn a M. Vink, „  Transkraniální magnetická stimulace a funkční MRI odhalují kortikální a subkortikální interakce během inhibice reakce stop-signál  “ , Journal of Cognitive Neuroscience , sv. .  25, n O  22013, str.  157-174 ( DOI  10.1162 / jocn_a_0030 )
  14. (in) EC Curtis, DH Zald a Pardo JV, „  Organisation of working memory dans le prefrontal cortex human: a PET study of self-ordered object working memory  “ , Neuropsychologia , sv.  38, n o  11,2000, str.  1503-1510
  15. (in) J. Rowe, A. Owen, I. a R. Johnsrude Passingham, „  Zobrazování mentálních komponent naplánovaného úkolu.  » , Neuropsychologia , sv.  39, n o  3,2001, str.  315-327
  16. (in) R. Parks a J. Cardoso, „  Paralelní distribuované zpracování a výkonné fungování: model neuronové sítě Tower of Hanoi u zdravých kontrol a pacienti opustili čelní lalok.  » , International journal of neuroscience , sv.  89, žádné kosti  3-4,1997, str.  217-240

Bibliografie

  • (en) Andreas M. Hinz, Sandi Klavžar a Uroš Milutinović, Hanojská věž - mýty a matematika , Basilej, Springer Science & Business Media,31. ledna 2013, 335  s. ( ISBN  978-3-0348-0237-6 , číst online ).
  • Jean-Paul Delahaye, "  Věže Hanoi, více než dětská hra  ", Pour la Science , n o  457,listopadu 2015, str.  108-112 a 114.

Podívejte se také

Související články