Comment cela marche-t-il? Tours étranges de Hanoi Solution

J’ai été perdu sur Internet quand j’ai découvert cette solution inhabituelle et itérative aux 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 message a également le code Delphi similaire dans l’une des réponses.

Cependant, pour la vie de moi, je n’arrive pas à trouver une bonne explication pour expliquer pourquoi cela fonctionne.

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

la solution récursive aux 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 la partie inférieure vers C, puis vous déplacez à nouveau N- 1 disques de B à C. En résumé,

 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 mouvements que 2 * hanoi (_, _, _, k-1) + 1. Donc le La longueur de la solution augmente dans l’ordre 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 vous obtenez

 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 vous obtenez

 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 vous prenez l’entrée du milieu sur les colonnes, les parties ci-dessus et ci-dessous sont des copies les unes des autres, mais les nombres sont permutés. C’est une conséquence évidente de l’algorithme lui-même qui n’effectue aucune arithmétique sur les numéros de peg mais qui ne les permute que. Dans le cas où N = 4, la rangée du milieu est à x = 4 (marquée de trois écanvass ci-dessus).

Maintenant, l’expression (X & (X-1)) désactive le bit le moins défini de X, par conséquent, elle mappe par exemple les nombres 1 à 7:

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

L’astuce est que parce que la ligne médiane est toujours à une puissance exacte de deux et a donc exactement un bit défini, la partie après la ligne médiane est égale à la partie avant lorsque vous ajoutez la valeur de la ligne médiane (4 dans ce cas) à la lignes (c.-à-d. 4 = 0 + 4, 6 = 2 + 6). Cela implémente la propriété “copy”, l’ajout de la ligne du milieu implémente la partie permutation. L’expression (X | (X-1)) + 1 définit le bit zéro le plus bas qui a des bits à sa droite, et efface ces derniers, de sorte qu’il a 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 

En ce qui concerne la raison pour laquelle ces séquences produisent réellement les numéros de peg corrects, considérons la colonne FROM. La solution récursive commence par hanoi (0, 2, 1, N), donc au niveau de la ligne du milieu (2 ** (N-1)), vous devez avoir moveisk (0, 2). Maintenant, à l’aide de la règle de récursivité, à (2 ** (N-2)), vous devez avoir déplacé moveisk (0, 1) et at (2 ** (N-1)) + 2 ** (N-2) moveisk ( 1, 2). Cela crée le motif “0,0,1” pour les pinces from 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 les versions permutées du même modèle).

Maintenant, de toutes les fonctions qui ont cette propriété qu’elles créent 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 difficile car il n’y a que 6 permutations possibles des trois nombres 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 ne doit pas l’être; il suffit qu’il ait la propriété de copier et qu’il produise les permutations correctes dans le bon ordre.

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

Première note: à l’étape intermédiaire x = 2 N-1 de cet algorithme, le pion “de” est 0, et le pion “à” est 2 N % 3. Cela laisse 2 (N-1) % 3 pour le ” pince de rechange Cela est également vrai pour la dernière étape de l’algorithme, nous voyons donc que l’algorithme des auteurs est un léger “sortingche”: ils déplacent les disques de peg 0 à peg 2 N % 3, plutôt qu’un pre, fixe -specified “to” peg. Cela pourrait être changé avec peu 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) 

En branchant “from” = 0, “to” = 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: Dans la ligne (c), les piquets sont exactement les piquets de hanoi (0, 2 N-1 , 2 N , N-1) décalés de 2 N-1 % 3, c’est-à-dire qu’ils sont exactement les piquets de la ligne (a) avec ce montant ajouté à eux .

Je prétends qu’il en résulte que lorsque nous exécutons la ligne (c), les chevilles “from” et “to” sont les chevilles correspondantes de la ligne (a) décalée de 2 N-1 % 3. Cela découle du lemme facile et plus général que dans hanoi(a+x, b+x, c+x, N) , les chevilles “from et” to “sont décalées exactement de x depuis 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 N , on a f (2 N – i) == f (2 N + i) + 2 N % 3, et g (2 N – i) == g (2 N + i) + 2 N % 3.

Les deux sont faciles à montrer.

Cela ne répond pas directement à la question, mais il était trop long de mettre un commentaire.

Je l’avais toujours fait en analysant la taille du disque que vous deviez déplacer ensuite. Si vous regardez les disques déplacés, il en ressort:

 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 la direction opposée des paires, dans l’ordre si les chevilles (0, 1, 2, répétez) ou (2, 1, 0, répétez).

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