algorithm - ¿Como funciona esto? Solución de las torres extrañas de Hanoi
language-agnostic bit-manipulation (3)
Esto no es responder directamente a la pregunta, pero fue demasiado largo para hacer un comentario.
Siempre lo hice analizando el tamaño del disco que debes mover a continuación. Si nos fijamos en los discos movidos, sale a:
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
Los tamaños impares siempre se mueven en la dirección opuesta a los pares, en orden si las clavijas (0, 1, 2, repetición) o (2, 1, 0, repetición).
Si observas el patrón, el anillo a mover es el conjunto de bits más alto del xor del número de movimientos y el número de movimientos + 1.
Me perdí en Internet cuando descubrí this solución inusual e iterativa de las torres de Hanoi:
for (int x = 1; x < (1 << nDisks); x++)
{
FromPole = (x & x-1) % 3;
ToPole = ((x | x-1) + 1) % 3;
moveDisk(FromPole, ToPole);
}
Esta publicación también tiene un código Delphi similar en una de las respuestas.
Sin embargo, por mi vida, parece que no puedo encontrar una buena explicación de por qué esto funciona.
¿Alguien puede ayudarme a entenderlo?
La solución de antti.huima es esencialmente correcta, pero quería algo más riguroso, y era demasiado grande para caber en un comentario. Aquí va:
Primera nota: en el paso medio x = 2 N-1 de este algoritmo, la marca "de" es 0, y la barra "a" es 2 N % 3. Esto deja 2 (N-1) % 3 para la " repuesto "clavija. Esto también es cierto para el último paso del algoritmo, por lo que vemos que en realidad el algoritmo de los autores es un "truco" leve: están moviendo los discos de la clavija 0 a la clavija 2 N % 3, en lugar de un pre -especificado "a" peg. Esto podría cambiarse sin mucho trabajo.
El algoritmo original de Hanoi es:
hanoi(from, to, spare, N):
hanoi(from, spare, to, N-1)
move(from, to)
hanoi(spare, to, from, N-1)
Al conectar "from" = 0, "a" = 2 N % 3, "spare" = 2 N-1 % 3, obtenemos (suprimiendo el% 3''s):
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)
La observación fundamental aquí es: En la línea (c), las clavijas son exactamente las clavijas de hanoi (0, 2 N-1 , 2 N , N-1) desplazadas en 2 N-1 % 3, es decir , son exactamente las clavijas de la línea (a) con esta cantidad añadida a ellos .
Afirmo que de ello se deduce que cuando ejecutamos la línea (c), las "desde" y "hasta" son las correspondientes líneas de la línea (a) desplazadas en 2 N-1 % 3. Esto se deduce del lema más sencillo y general. que en hanoi(a+x, b+x, c+x, N) , las clavijas "desde y" a "se desplazan exactamente x desde in hanoi(a, b, c, N) .
Ahora considera las funciones
f(x) = (x & (x-1)) % 3
g(x) = (x | (x-1)) + 1 % 3
Para probar que el algoritmo dado funciona, solo tenemos que demostrar que:
- f (2 N-1 ) == 0 y g (2 N-1 ) == 2 N
- para 0 <i <2 N , tenemos f (2 N - i) == f (2 N + i) + 2 N % 3, y g (2 N - i) == g (2 N + i) + 2 N % 3.
Ambos son fáciles de mostrar.
La solución recursiva a las torres de Hanoi funciona de modo que si desea mover N discos de la clavija A a C, primero mueva N-1 de A a B, luego mueva el inferior a C y luego mueva nuevamente N- 1 discos de B a C. En esencia,
hanoi(from, to, spare, N):
hanoi(from, spare, to, N-1)
moveDisk(from, to)
hanoi(spare, to, from, N-1)
Claramente, hanoi (_, _, _, 1) toma un movimiento, y hanoi (_, _, _, k, k) toma tantos movimientos como 2 * hanoi (_, _, _, k-1) + 1. Así que la longitud de la solución crece en la secuencia 1, 3, 7, 15, ... Esta es la misma secuencia que (1 << k) - 1, lo que explica la longitud del bucle en el algoritmo que publicó.
Si miras las soluciones en sí mismas, para N = 1 obtienes
FROM TO
; hanoi(0, 2, 1, 1)
0 2 movedisk
Para N = 2 obtienes
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
Y para N = 3 obtienes
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
Debido a la naturaleza recursiva de la solución, las columnas FROM y TO siguen una lógica recursiva: si toma la entrada central de las columnas, las partes arriba y abajo son copias de las demás, pero con los números permutados. Esta es una consecuencia obvia del algoritmo en sí mismo, que no realiza ninguna aritmética en los números de clavija, sino que solo los permuta. En el caso N = 4, la fila central está en x = 4 (marcada con tres estrellas arriba).
Ahora la expresión (X & (X-1)) desactiva el bit de X menos establecido, por lo que mapea, por ejemplo, los números del 1 al 7, de esta forma:
1 -> 0
2 -> 0
3 -> 2
4 -> 0 (***)
5 -> 4 % 3 = 1
6 -> 4 % 3 = 1
7 -> 6 % 3 = 0
El truco es que debido a que la fila del medio siempre tiene una potencia exacta de dos y, por lo tanto, tiene exactamente un bit establecido, la parte después de la fila del medio es igual a la parte anterior cuando se agrega el valor de la fila del medio (4 en este caso) a la filas (es decir, 4 = 0 + 4, 6 = 2 + 6). Esto implementa la propiedad "copiar", la adición de la fila central implementa la parte de permutación. La expresión (X | (X-1)) + 1 establece el bit cero más bajo que tiene unos a su derecha y los borra, por lo que tiene propiedades similares a las esperadas:
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 cuanto a por qué estas secuencias realmente producen los números de clavija correctos, consideremos la columna FROM. La solución recursiva comienza con hanoi (0, 2, 1, N), por lo que en la fila central (2 ** (N-1)) debe tener moveisk (0, 2). Ahora según la regla de recursión, en (2 ** (N-2)) necesita tener movedisk (0, 1) y en (2 ** (N-1)) + 2 ** (N-2) movedisk ( 1, 2). Esto crea el patrón "0,0,1" para los trazados desde, que es visible con diferentes permutaciones en la tabla anterior (verifique las filas 2, 4 y 6 para 0,0,1 y las filas 1, 2, 3 para 0,0 , 2, y filas 5, 6, 7 para 1,1,0, todas las versiones permutadas del mismo patrón).
Ahora, de todas las funciones que tienen esta propiedad, se crean copias de sí mismos en torno a potencias de dos, pero con compensaciones, los autores han seleccionado las que producen el módulo 3 con las permutaciones correctas. Esta no es una tarea abiertamente difícil porque solo hay 6 posibles permutaciones de los tres enteros 0..2 y las permutaciones avanzan en un orden lógico en el algoritmo. (X | (X-1)) + 1 no está necesariamente profundamente vinculado con el problema de Hanoi o no tiene que estarlo; es suficiente que tenga la propiedad de copia y que produzca las permutaciones correctas en el orden correcto.