La torre di Hanoi

Il problema

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!

Analisi

Siano D₁, D₂, …, D_n le etichette dei dischi di una torre di Hanoi con n dischi.

1	Il problema con un solo disco è banale il disco è sinistra sposta il disco D1 dalla 1° alla 3° torre
2	Se i dischi sono 2 le mosse sono 3 i dischi sono a sinistra sposta il disco D1 dalla 1° alla 2° torre sposta il disco D2 dalla 1° alla 3° torre sposta il disco D1 dalla 2° alla 3° torre
3	Se i dischi sono 3 le mosse sono 7 i dischi sono a sinistra sposta il disco D1 dalla 1° alla 3° torre sposta il disco D2 dalla 1° alla 2° torre sposta il disco D1 dalla 3° alla 2° torre sposta il disco D3 dalla 1° alla 3° torre sposta il disco D1 dalla 2° alla 1° torre sposta il disco D2 dalla 2° alla 3° torre sposta il disco D1 dalla 1° alla 3° torre
…	Se i dischi sono 4, 5, … si può riconoscere lo schema risolutivo i dischi sono a sinistra sposta i dischi D1…Dn-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare Dn sposta il disco Dn dalla 1° alla 3° torre sposta i dischi D1…Dn-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra Dn

Algoritmo

• 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

diventa

1. Hanoi(n-1, origine , arrivo  , appoggio    )
2. Hanoi(  1, origine , appoggio, destinazione)
3. 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.

Procedure Hanoi(n, origine, appoggio, destinazione: Byte);
Begin
   If(n = 1) Then
      WriteLn(origine, ' - ', destinazione)
   Else
      Begin
         Hanoi(n-1, origine , destinazione, appoggio    );
         Hanoi(  1, origine , appoggio    , destinazione);
         Hanoi(n-1, appoggio, origine     , destinazione);
      End;
End;

Var num: Byte:
Begin
    Write('Numero dischi? ');
    Readln(num);
    Hanoi(num, 1, 2, 3);
    Readln;
End.

---

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi

Numericamente si tratta della successione

cioè

quindi

I tempi necessari per risolvere il problema sono

n	T(n) = 2n-1	1 Hz (uomo)	1 GHz (PC)
1	21-1 = 1	un secondo	10-9 s
2	22-1 = 3	3 secondi	3*10-9 s
10	210-1 = 1023	~17 minuti	~10-6 s
20	220-1 = 1.048.575	~12 giorni	~10-3 s
30	230-1 = 1.073.741.823	~34 anni	~1 s
64	264-1 = 18.446.744.073.709.551.615	~5*1011 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
• Il problema della torre di Hanoi è un problema intrattabile!