Comment cela fonctionne-t-il ? Solution pour les tours étranges de Hanoi

Question

J'étais perdu sur internet quand j'ai découvert ce inhabituelle et itérative des tours de Hanoi :

for (int x = 1; x < (1 << nDisks); x++)
{
     FromPole = (x & x-1) % 3;
     ToPole = ((x | x-1) + 1) % 3;
     moveDisk(FromPole, ToPole);
}

Ce poste a également un code Delphi similaire dans l'une des réponses.

Cependant, je ne parviens pas à trouver une bonne explication pour expliquer pourquoi cela fonctionne.

Quelqu'un peut-il m'aider à le comprendre ?

Answer 1

La solution récursive des tours de Hanoi fonctionne de telle sorte que si vous voulez déplacer N disques de la cheville A à C, vous déplacez d'abord N-1 de A à B, puis vous déplacez celui du bas à C, et enfin vous déplacez à nouveau N-1 disques de B à C. En substance,

hanoi(from, to, spare, N):
  hanoi(from, spare, to, N-1)
  moveDisk(from, to)
  hanoi(spare, to, from, N-1)

Clairement, hanoi( _ , _ , _ , 1) prend un coup, et hanoi ( _ , _ , _ , k) prend autant de coups que 2 * hanoi( _ , _ , _ , k-1) + 1. La longueur de la solution croît donc dans la séquence 1, 3, 7, 15, ... C'est la même séquence que (1 << k) - 1, ce qui explique la longueur de la boucle dans l'algorithme que vous avez posté.

Si vous regardez les solutions elles-mêmes, pour N = 1, vous obtenez

FROM   TO
          ; hanoi(0, 2, 1, 1)
   0    2    movedisk

Pour N = 2, on obtient

FROM   TO
          ; hanoi(0, 2, 1, 2)
          ;  hanoi(0, 1, 2, 1)
   0    1 ;   movedisk
   0    2 ;  movedisk
          ;  hanoi(1, 2, 0, 1)
   1    2 ;   movedisk

Et pour N = 3, on obtient

FROM   TO
          ; hanoi(0, 2, 1, 3)
          ;  hanoi(0, 1, 2, 2)
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk
   0    1 ;   movedisk
          ;   hanoi(2, 1, 0, 1)
   2    1 ;    movedisk
   0    2 ;  movedisk ***
          ;  hanoi(1, 2, 0, 2)
          ;   hanoi(1, 0, 2, 1)
   1    0 ;    movedisk
   1    2 ;   movedisk
          ;   hanoi(0, 2, 1, 1)
   0    2 ;    movedisk

En raison de la nature récursive de la solution, les colonnes FROM et TO suivent une logique récursive : si l'on prend l'entrée centrale des colonnes, les parties situées au-dessus et au-dessous sont des copies les unes des autres, mais avec des nombres permutés. Il s'agit d'une conséquence évidente de l'algorithme lui-même, qui n'effectue aucune opération arithmétique sur les nombres pairs, mais se contente de les permuter. Dans le cas de N=4, la rangée du milieu est à x=4 (marquée de trois étoiles ci-dessus).

Maintenant, l'expression (X & (X-1)) annule le bit le moins activé de X, de sorte qu'elle associe par exemple les nombres de 1 à 7 comme ceci :

   1 ->  0
   2 ->  0
   3 ->  2
   4 -> 0 (***)
   5 ->  4 % 3 = 1
   6 ->  4 % 3 = 1
   7 ->  6 % 3 = 0

L'astuce est la suivante : comme la rangée du milieu est toujours à une puissance exacte de deux et a donc exactement un bit activé, la partie après la rangée du milieu est égale à la partie avant lorsque vous ajoutez la valeur de la rangée du milieu (4 dans ce cas) aux rangées (c'est-à-dire 4=0+4, 6=2+6). Ceci met en œuvre la propriété de "copie", l'ajout de la ligne du milieu met en œuvre la partie de permutation. L'expression (X | (X-1)) + 1 définit le bit zéro le plus bas qui a des uns à sa droite, et efface ces uns, elle a donc des propriétés similaires à celles attendues :

   1 ->  2
   2 ->  4 % 3 = 1
   3 ->  4 % 3 = 1
   4 -> 8 (***) % 3 = 2
   5 ->  6 % 3 = 0
   6 ->  8 % 3 = 2
   7 ->  8 % 3 = 2

Pour savoir pourquoi ces séquences produisent effectivement les bons numéros de piquet, considérons la colonne FROM. La solution récursive commence avec hanoi(0, 2, 1, N), donc à la ligne du milieu (2 ** (N-1)) vous devez avoir movedisk(0, 2). Maintenant, par la règle de récursion, à (2 ** (N-2)) vous devez avoir déplacéisk(0, 1) et à (2 ** (N-1)) + 2 ** (N-2) déplacéisk (1, 2). Cela crée le motif "0,0,1" pour les chevilles de départ qui est visible avec différentes permutations dans le tableau ci-dessus (vérifiez les lignes 2, 4 et 6 pour 0,0,1 et les lignes 1, 2, 3 pour 0,0,2, et les lignes 5, 6, 7 pour 1,1,0, toutes des versions permutées du même motif).

Parmi toutes les fonctions qui ont cette propriété de créer des copies d'elles-mêmes autour des puissances de deux, mais avec des décalages, les auteurs ont sélectionné celles qui produisent modulo 3 les permutations correctes. Ce n'est pas une tâche trop difficile car il n'y a que 6 permutations possibles des trois entiers 0..2 et les permutations progressent dans un ordre logique dans l'algorithme. (X|(X-1))+1 n'est pas nécessairement lié au problème de Hanoi ou n'a pas besoin de l'être ; il suffit qu'il ait la propriété de copie et qu'il produise les permutations correctes dans l'ordre correct.

Answer 2

La solution d'antti.huima est essentiellement correcte, mais je voulais quelque chose de plus rigoureux, et c'était trop gros pour tenir dans un commentaire. C'est parti :

Première remarque : à l'étape intermédiaire x = 2 N-1 Dans cet algorithme, le point de départ est 0, et le point d'arrivée est 2. N % 3. Il reste donc 2 (N-1) % 3 pour la cheville "de réserve". Ceci est également vrai pour la dernière étape de l'algorithme, nous voyons donc qu'en fait l'algorithme des auteurs est une légère "tricherie" : ils déplacent les disques de la cheville 0 à la cheville 2. N % 3, plutôt qu'une valeur fixe, fixe et pré-spécifié de "à". Cela pourrait être modifié sans trop de travail.

L'algorithme original de Hanoi est :

hanoi(from, to, spare, N):
    hanoi(from, spare, to, N-1)
    move(from, to)
    hanoi(spare, to, from, N-1)

Branchement "de" = 0, "à" = 2 N % 3, "spare" = 2 N-1 % 3, on obtient (en supprimant les %3) :

hanoi(0, 2**N, 2**(N-1), N):
(a)   hanoi(0, 2**(N-1), 2**N, N-1)
(b)   move(0, 2**N)
(c)   hanoi(2**(N-1), 2**N, 0, N-1)

L'observation fondamentale ici est la suivante : Dans la ligne (c), les chevilles sont exactement les chevilles de hanoi(0, 2 N-1 , 2 N , N-1) décalé de 2 N-1 % 3, c'est-à-dire il s'agit exactement des chevilles de la ligne (a) auxquelles on a ajouté ce montant. .

Je prétends qu'il s'ensuit que lorsque nous exécutons la ligne (c), les chevilles "de" et "à" sont les chevilles correspondantes de la ligne (a), décalées de 2 %. N-1 % 3. Ce suit le lemme facile, plus général, selon lequel en hanoi(a+x, b+x, c+x, N) les chevilles "de" et "à" sont décalées d'exactement x de en hanoi(a, b, c, N) .

Considérons maintenant les fonctions
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3

Pour prouver que l'algorithme donné fonctionne, il suffit de montrer que :

• f(2 N-1 ) == 0 et g(2 N-1 ) == 2 N
• pour 0 < i < 2 N nous avons f(2 N - i) == f(2 N + i) + 2 N % 3, et g(2 N - i) == g(2 N + i) + 2 N % 3.

Ces deux éléments sont faciles à démontrer.

Answer 3

Ce n'est pas une réponse directe à la question, mais c'était trop long pour être mis dans un commentaire.

J'avais toujours fait cela en analysant la taille du disque à déplacer ensuite. Si vous regardez les disques déplacés, ça donne :

1 disk  : 1
2 disks : 1 2 1
3 disks : 1 2 1 3 1 2 1
4 disks : 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

Les tailles impaires se déplacent toujours dans le sens inverse des tailles paires, dans l'ordre si les chevilles (0, 1, 2, répétition) ou (2, 1, 0, répétition).

Si vous regardez le schéma, l'anneau à déplacer est le bit le plus élevé de l'ensemble xor du nombre de coups et du nombre de coups + 1.