La torre di Hanoi

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.
Sul primo di tali perni sono infilati 64 dischi d'oro, di dimensioni decrescenti, che formano una torre.
Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.
Per risolvere la questione si può utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l'opera il mondo sarà finito!

Algoritmo risolutivo

Siano D₁, D₂, ..., D_n le etichette dei dischi di una torre di Hanoi con n dischi.
Analizziamo la soluzione nei casi più semplici.

N=1

Il problema con un solo disco è banale

sposta il disco D₁ dalla 1° alla 3° torre

N=2

Se i dischi sono 2

Notice: Constant FLASH_DEFAULT_WIDTH already defined in /web/htdocs/www.valcon.it/home/p/actions/flash/flash.php on line 23

Notice: Constant FLASH_DEFAULT_HEIGHT already defined in /web/htdocs/www.valcon.it/home/p/actions/flash/flash.php on line 24

Notice: Constant FLASH_MAX_WIDTH already defined in /web/htdocs/www.valcon.it/home/p/actions/flash/flash.php on line 25

Notice: Constant FLASH_MAX_HEIGHT already defined in /web/htdocs/www.valcon.it/home/p/actions/flash/flash.php on line 26

sposta il disco D₁ dalla 1° alla 2° torre
sposta il disco D₂ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 3° torre

N=3

Se i dischi sono 3

sposta il disco D₁ dalla 1° alla 3° torre
sposta il disco D₂ dalla 1° alla 2° torre
sposta il disco D₁ dalla 3° alla 2° torre
sposta il disco D₃ dalla 1° alla 3° torre
sposta il disco D₁ dalla 2° alla 1° torre
sposta il disco D₂ dalla 2° alla 3° torre
sposta il disco D₁ dalla 1° alla 3° torre

N=4, 5, ...

Se i dischi sono 4, 5, ... si può riconoscere lo schema risolutivo

sposta i dischi D₁...D_n-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare D_n
sposta il disco D_n dalla 1° alla 3° torre
sposta i dischi D₁...D_n-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra D_n

Ad ogni passo è sufficiente specificare

il numero di dischi coinvolti, perché si parla sempre dei dischi in cima a una torre
il nome della torre di origine
il nome della torre di appoggio
il nome della torre di destinazione

allora l'algoritmo risolutivo per il problema

Hanoi(n, origine, appoggio, destinazione)

diventa

Hanoi(n-1, origine, arrivo, appoggio)
Hanoi(1, origine, appoggio, destinazione)
Hanoi(n-1, appoggio, origine, destinazione)

con l'accortezza che nel caso di torre con un solo disco è sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.

Pseudocodice

PROCEDURA Hanoi(INTERO n, INTERO origine, INTERO appoggio, INTERO destinazione)

INIZIO

   SE (n == 1) ALLORA

      SCRIVI("... " + origine + " ... " + destinazione + " ...")

   ALTRIMENTI

      INIZIO

         Hanoi(n-1, origine , arrivo , appoggio )

         Hanoi(1 , origine , appoggio, destinazione)

         Hanoi(n-1, appoggio, origine , destinazione)

      FINE

FINE

Applicazione Java

Applicazione Javascript

Complessità

Consideriamo il tempo di esecuzione come proporzionale al numero di spostamenti di dischi

T(1) = 1
T(2) = T(1)+T(1)+T(1) = 3
T(3) = T(2)+T(1)+T(2) = 7
T(4) = T(3)+T(1)+T(3) = 15
...
T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

2¹-1, 2²-1, 2³-1, 2⁴-1, 2⁵-1, 2⁶-1, 2⁷-1, ...

quindi (...)

T(n) = 2ⁿ-1

I tempi necessari per risolvere il problema sono

n	T(n) = 2ⁿ-1	Tempi
n	T(n) = 2ⁿ-1	1 Hz (uomo)	1 GHz (PC)
1	2¹-1 = 1	un secondo	10^-9 s
2	2²-1 = 3	3 secondi	3*10^-9 s
10	2¹⁰-1 = 1023	~17 minuti	~10^-6 s
20	2²⁰-1 = 1.048.575	~12 giorni	~10^-3 s
30	2³⁰-1 = 1.073.741.823	~34 anni	~1 s
64	2⁶⁴-1 = 18.446.744.073.709.551.615	~5*10¹¹ anni	~500 anni

Conclusioni

L'algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2ⁿ)
Non può esistere un algoritmo con complessità minore
Il problema della torre di Hanoi è un problema intrinsecamente esponenziale, intrattabile!

Prova a Programmare! : AlgoritmiHanoi