Probleme – Les tours de Hanoï : le compte, la borne, la pile

1. La fonction.

(* hanoi n a b c affiche les deplacements amenant les n disques du
   piquet a au piquet c, en se servant de b comme intermediaire.
   Precondition : n >= 0, et a, b, c deux a deux distincts. *)
let rec hanoi n a b c =
  if n > 0 then begin
    hanoi (n-1) a c b;                        (* les n-1 petits : a --> b *)
    Printf.printf "disque %d : %s -> %s\n" n a c;   (* le grand : a --> c *)
    hanoi (n-1) b a c                         (* les n-1 petits : b --> c *)
  end

Pour $n=3$, mesuré : 1:A->C, 2:A->B, 1:C->B, 3:A->C, 1:B->A, 2:B->C, 1:A->C, soit sept déplacements.

Le point de méthode est le saut de confiance de la méthode du cours : on ne déroule pas les appels, on suppose donnée la solution pour $n-1$ disques et l'on s'en sert deux fois. La légalité est immédiate : pendant que les $n-1$ petits voyagent, le disque $n$ est le plus grand et ne gêne personne ; quand il bouge, les deux autres piquets utiles sont libres.

2. Le compte. Soit $D(n)$ le nombre de déplacements. La fonction en fait $D(n)=2D(n-1)+1$ avec $D(0)=0$. En posant $E(n)=D(n)+1$, il vient $E(n)=2E(n-1)$ et $E(0)=1$, donc $E(n)=2^n$ et

$$D(n)=2^n-1.$$

Mesuré : $1,3,7,15,31,63$ pour $n=1\dots 6$, puis $1023$ pour $n=10$ et $1048575$ pour $n=20$ — soit exactement $2^n-1$ à chaque fois.

3. La borne inférieure. Soit $M(n)$ le nombre minimal de déplacements, toutes stratégies confondues. Pour amener le disque $n$ de $A$ sur $C$, il faut qu'à cet instant $A$ ne porte que lui et que $C$ soit vide : les $n-1$ autres sont donc tous sur $B$. Il a donc fallu au préalable amener $n-1$ disques de $A$ à $B$, ce qui coûte au moins $M(n-1)$ ; puis au moins un déplacement pour le disque $n$ ; puis amener les $n-1$ disques de $B$ à $C$, encore au moins $M(n-1)$. D'où $M(n)\ge 2M(n-1)+1$, et par récurrence $M(n)\ge 2^n-1$. Comme l'algorithme atteint cette valeur, il est optimal et $M(n)=2^n-1$.

Ce raisonnement mérite d'être savouré : il ne parle d'aucun algorithme, seulement de ce que la règle du jeu impose. C'est la première borne inférieure du livre, et le chapitre chap:diviser en donnera d'autres.

4. La pile. L'arbre des appels est binaire, complet, de hauteur $n$ : il a $2^n-1$ nœuds internes, mais sa hauteur est $n$. La profondeur de pile est donc $\Theta (n)$, et le temps $\Theta (2^n)$.

Non, ce ne sont pas la même grandeur, et c'est le point du problème. Pour $n=40$, la machine ouvre au plus $40$ blocs d'activation — dérisoire — et fait $10^{12}$ déplacements — plusieurs heures. La mémoire n'est jamais le problème de Hanoï ; le temps l'est toujours. La confusion inverse est fréquente : on croit qu'un algorithme exponentiel en temps l'est aussi en mémoire. Le cours le dit en une phrase que ce problème illustre : la hauteur de l'arbre donne l'espace, le nombre de nœuds donne le temps.