Torre de Hanoi

La Torre de Hanoi es uno de los rompecabezas populares del siglo XIX . Se dan tres varillas, una de las cuales está ensartada con ocho anillos, y los anillos difieren en tamaño y el más pequeño se encuentra sobre el más grande. La tarea es transferir la pirámide de ocho anillos en el menor número de movimientos a otra barra. Solo puede llevar un anillo a la vez y no puede colocar un anillo más grande encima de uno más pequeño.

Historia del rompecabezas

Este juego fue inventado por el matemático francés Edouard Lucas en 1883 [1] , se vendía como un juguete divertido. Originalmente se llamaba "Profesor Claus of Li-Sou-Stian College" [1] , pero pronto se descubrió que el misterioso profesor de la desaparecida universidad no era más que un anagrama del nombre del inventor del juego, el profesor Luke (Lucas del Colegio San Luis.

Solución

Hay varios enfoques para la solución.

Solución recursiva

Resolvemos recursivamente el problema de "transferir una torre de n - 1 discos al segundo pin". Luego, movemos el disco más grande al tercer pin y resolvemos recursivamente el problema "transferir la torre de n - 1 discos al tercer pin".

Por lo tanto, por inducción matemática concluimos que el número mínimo de movimientos necesarios para resolver el rompecabezas es 2 n − 1, donde n es el número de discos [2] [3] .

En informática, los problemas basados en la leyenda de la Torre de Hanoi a menudo se consideran como un ejemplo del uso de algoritmos recursivos y su conversión a algoritmos no recursivos.

Solución "Triángulo"

Organizar los pines en forma de triángulo. Comencemos con el anillo más pequeño y muévalo a cualquier marca. En el futuro, este anillo debe moverse en la misma dirección que durante el primer cambio. Luego transferimos algunos de los anillos restantes (solo hay un movimiento de este tipo), después de lo cual transferimos nuevamente el anillo más pequeño, etc. (Es interesante notar que al volver a numerar los "anillos" en orden, lograremos un efecto inesperado : los anillos pares se moverán de un triángulo de vértice a otro en una dirección y los impares en la dirección opuesta).

Decisión cíclica

Denote con "1-2" tal acción: cambie el disco del primer pin al 2º, o del 2º al 1º, dependiendo de dónde sea más pequeño. Luego, para resolver un rompecabezas con un número par de discos, debe repetir los pasos muchas veces: 1-2, 1-3, 2-3. Si el número de discos es impar: 1-3, 1-2, 2-3.

Aplicación de código Gray para resolver

Código Gray , un código binario reflejo en notación binaria , en el que dos valores adyacentes difieren en un solo bit. El código Gray originalmente estaba destinado a proteger contra el funcionamiento falso de los interruptores electromecánicos. Hoy en día, los códigos Gray se utilizan ampliamente para simplificar la detección y corrección de errores en los sistemas de comunicación, así como en la formación de señales de retroalimentación en los sistemas de control. El código lleva el nombre del investigador de Bell Labs, Frank Gray. Él patentó (número 2632058) y usó este código en su sistema de comunicación por impulsos.

Los códigos grises se pueden aplicar al problema de las Torres de Hanoi.
Sea N el número de discos. Comencemos con un código Gray de longitud N, que consta de solo ceros (es decir, G 0 ), y nos moveremos a lo largo de los códigos Gray (desde G i vamos a G i+1 ). Asignemos cada i-ésimo bit del código Gray actual al i-ésimo disco (además, el bit menos significativo corresponde al disco más pequeño y el bit más significativo corresponde al más grande). Dado que cambia exactamente un bit en cada paso, podemos entender el cambio del bit i como el movimiento del i-ésimo disco. Tenga en cuenta que para todos los discos, excepto el más pequeño, hay exactamente un movimiento posible en cada paso (excepto las posiciones inicial y final). Para el disco más pequeño, siempre hay dos opciones para el movimiento, pero hay una estrategia para elegir el movimiento correcto: para N impar, la secuencia de movimientos del disco más pequeño f→t→r→f→t→r→… (donde f es la barra inicial, t es la barra final, r - barra restante), y para incluso f→r→t→f→r→t→… .

Implementaciones de algoritmos

Un ejemplo de un algoritmo de solución en C++ :

// Torres de Hanoi #include <iostream> utilizando el espacio de nombres estándar ; void hanoi_towers ( int cantidad , int desde , int hasta , int buf_peg ) // cantidad-número de anillos, desde la posición inicial de los anillos (1-3), hasta la posición final de los anillos (1-3) { // buf_peg - clavija intermedia (1-3) si ( cantidad != 0 ) { hanoi_towers ( cantidad -1 , desde , buf_peg , hasta ); cout << de << " -> " << a << endl ; hanoi_towers ( cantidad -1 , buf_peg , a , desde ); } } int principal () { setlocale ( LC_ALL , "rus" ); int start_peg , destination_peg , buffer_peg , plate_quantity ; cout << "Número de la primera columna:" << endl ; cin >> start_peg ; cout << "Número de columna final:" << endl ; cin >> destino_peg ; cout << "Número de columna intermedia:" << endl ; cin >> buffer_peg ; cout << "Número de discos:" << endl ; cin >> cantidad_plato ; torres_hanoi ( cantidad_placa , clavija_inicio , clavija_destino , clavija_búfer ); devolver 0 ; }

Un ejemplo de un algoritmo de solución en Pascal :

programa hanoibns ( entrada , salida ) ; varn : entero ; _ torre de procedimiento ( k : entero ; a , b , c : char ) ; empezar si k > 1 entonces torre ( k - 1 , a , c , b ) ; writeln ( 'desde' , a , 'hasta' , b ) ; si k > 1 entonces la torre ( k - 1 , c , b , a ) termina ; comenzar a leer ( n ) ; _ extremo de la torre ( n , 'A' , 'C' , 'B' ) .

Un ejemplo de un algoritmo de solución en Haskell :

hanoiSteps :: Int -> [( Int , Int )] hanoiSteps n = paso ( max 0 n ) 1 3 2 [] donde paso 0 _ _ _ resto = resto paso n f t s resto = paso ( n - 1 ) f s t $ ( f , t ) : paso ( n - 1 ) s t f resto

Un ejemplo de un algoritmo de solución en Python :

def Hanoi ( n , A , C , B ): if ( n != 0 ): Hanoi ( n - 1 , A , B , C ) print ( 'Mover la placa de' , A , 'a' , C ) Hanoi ( n - 1 , B , C , A )

Un ejemplo de un algoritmo de solución en Java :

public class Hanoi { public static void hanoiTowers ( int cantidad , int desde , int hasta , int buf_peg ) { if ( cantidad != 0 ) { hanoiTowers ( cantidad - 1 , desde , buf_peg , hasta ); sistema _ fuera _ println ( "" + de + " -> " + a ); hanoiTowers ( cantidad - 1 , buf_peg , a , desde ); } } public static void main ( String [] args ) { int start_peg = 1 , destination_peg = 2 , buffer_peg = 3 , plate_quantity = 4 ; hanoiTowers ( plate_quantity , start_peg , destination_peg , buffer_peg ); } }

Un ejemplo de un algoritmo de solución iterativa en C

#incluir <stdio.h> #incluir <matemáticas.h> void carryOver ( int , int , int ); principal () { número int , contarDisco , contador = 1 , contar ; printf ( "Ingrese el numero de discos:" ); /* Torre de Hanoi */ scanf ( "%d" , & numero ); while ( counter <= pow ( 2 , number ) - 1 ) { /* Inicia el ciclo de repetición */ if ( contador % 2 != 0 ) { /* En un giro impar, solo tocaremos el disco más pequeño */ printf ( "%3d %d" , contador , 1 ); carryOver ( número , contador , 1 ); /* Usando esta función, determinamos el movimiento de este disco */ } else { /* Determinar el disco que se moverá en un movimiento parejo */ cuenta = contador ; cuentaDisco = 0 ; while ( count % 2 == 0 ) { /* Disco a mover */ cuentaDisco ++ ; /* será el número de dividir el número de movimiento por 2 sin resto */ cuenta = cuenta / 2 ; } printf ( "%3d %d " , contador , contarDisco + 1 ); carryOver ( número , contador , contarDisco + 1 ); } contador ++ ; } devolver 0 ; } /* Funcion para detectar movimiento de discos */ void carryOver ( int n , int i , int k ) { int t , ejeX , ejeY , ejeZ ; if ( n % 2 == 0 ) { /* Determinar el orden de los ejes en función de la paridad */ ejeX = 1 ; /* y número de discos sin paridad */ eje Y = 2 ; eje Z = 3 ; } más { ejeX = 1 ; eje Y = 3 ; eje Z = 2 ; } /* El número de jugada se puede representar de forma única */ /* como producto de un número impar por una potencia de dos */ /* k sera el numero del disco que estamos moviendo */ t = (( yo / pow ( 2 , k - 1 )) - 1 ) / 2 ; if ( k % 2 != 0 ) { /* Determinar el movimiento del disco para un movimiento impar */ switch ( t % 3 ) { /* Selecciona el movimiento dependiendo de la condición dada */ caso 0 : printf ( "%d -> %d \n " , ejeX , ejeY ); romper ; caso 1 : printf ( "%d -> %d \n " , ejeY , ejeZ ); romper ; caso 2 : printf ( "%d -> %d \n " , ejeZ , ejeX ); romper ; } } else { /* Determinar el movimiento de los discos para un movimiento parejo */ cambiar ( t % 3 ) { caso 0 : printf ( "%d -> %d \n " , ejeX , ejeZ ); romper ; caso 1 : printf ( "%d -> %d \n " , ejeZ , ejeY ); romper ; caso 2 : printf ( "%d -> %d \n " , ejeY , ejeX ); romper ; } } }

Hay programas para visualizar la solución a este rompecabezas.

Opciones

Con cuatro o más varillas

Aunque la variante de tres varillas tiene una solución recursiva simple, la solución óptima para la Torre de Hanoi con cuatro varillas ha sido durante mucho tiempo un problema sin resolver.

Obviamente, para cualquier número de barras, hay un algoritmo para encontrar soluciones óptimas, es suficiente representar el rompecabezas como un gráfico no dirigido, haciendo coincidir los vértices con las ubicaciones del disco y los bordes con los movimientos, y usar cualquier algoritmo de búsqueda (por ejemplo, búsqueda en amplitud ) para encontrar la solución óptima. Sin embargo, no existe una estrategia eficiente para encontrar la solución óptima para una gran cantidad de discos: se desconoce el número de movimientos necesarios para resolver un rompecabezas con 10 varillas y 1000 discos.

Hay un algoritmo Frame-Stewart supuestamente óptimo desarrollado en 1941 [4] . La conjetura de Frame-Stewart relacionada establece que el algoritmo de Frame-Stewart siempre encuentra la solución óptima. La optimización del algoritmo de Frame-Stewart se ha verificado experimentalmente hasta 30 discos en 4 varillas [5] . En 2014, finalmente se demostró que para cuatro barras el algoritmo de Frame-Stewart es óptimo [6] .

Otras variantes de la solución de la Torre de Hanoi de cuatro barras se analizan en un artículo de revisión de Paul Stockmayer [7] .

Algoritmo de Frame-Stewart

El algoritmo de Frame-Stewart, que da una solución óptima para cuatro y una solución supuestamente óptima para más barras, se describe a continuación:

Sea el número de discos. $norte$
Sea el número de varillas. $r$
Definámoslo como el menor número de movimientos necesarios para transferir n discos usando r varillas. ${\ estilo de visualización T (n, r)}$

El algoritmo se puede describir recursivamente:

Para algunos , transferir los superiores al pivote i , que no es ni el pivote inicial ni el pivote final, gastando movimientos para esto. $k$ ${\ estilo de visualización 1 \ leq k <n}$ $k$ ${\ estilo de visualización T (k, r)}$
Sin usar la barra i , que ahora contiene los discos superiores , transfiera los discos restantes a la barra final, usando solo las barras restantes y gastando movimientos. $k$ $nk$ $r-1$ $T(nk,r-1)$
Por último, desplazar los discos superiores hasta el extremo de la varilla, gastando movimientos para ello. $k$ ${\ estilo de visualización T (k, r)}$

Todo el proceso requiere movimientos. El valor se elige de modo que el valor de esta expresión sea mínimo. En el caso de 4 varillas, el óptimo es , donde es la función del entero más cercano . [ocho] ${\ estilo de visualización 2T (k, r) + T (nk, r-1)}$ $k$ $k$ $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$ $\left\lfloor \cdot \right\rceil$

Leyendas

La leyenda inventada por el profesor Luca dice que en el Gran Templo de la ciudad de Benares , debajo de la catedral que marca la mitad del mundo , hay un disco de bronce en el que se fijan 3 varillas de diamantes, de un codo de altura y del grosor de una abeja. . Hace mucho tiempo, al principio de los tiempos, los monjes de este monasterio fueron culpables ante el dios Brahma. Enfurecido, Brahma erigió tres varas altas y colocó 64 discos hechos de oro puro en una de ellas. Y así, cada disco más pequeño descansa sobre uno más grande.

Tan pronto como los 64 discos se transfieran de la vara, en la que Brahma los colocó cuando creó el mundo, a otra vara, la torre junto con el templo se convertirán en polvo y el mundo perecerá bajo estruendosos repiques.

El número de turnos en función del número de anillos se calcula mediante la fórmula . $2^{n}-1$

El número de movimientos de disco que deben realizar los monjes es 18.446.744.073.709.551.615 . Si los monjes, trabajando día y noche, hicieran un movimiento del disco cada segundo, su trabajo continuaría durante casi 585 mil millones de años .

En la cultura

En el cuento de Eric Frank Russell "Your Move" (Now Inhale, en otra traducción - "The Game of Survival") [9] , para retrasar la ejecución por extraterrestres, el protagonista elige el juego de la Torre de Hanoi. con 64 discos como último juego. Las reglas anunciadas se han modificado para dos jugadores: los jugadores deben cambiar los discos uno a la vez, el ganador es el que hace el último movimiento. El héroe llama a este juego "arki-malarki" y jura que los "sacerdotes del templo de Benares" en la Tierra juegan este juego.

En la película El origen del planeta de los simios , la Torre de Hanoi se utiliza como prueba de inteligencia para los sujetos de prueba. El mono completa el rompecabezas de cuatro anillos en veinte movimientos.

La Torre de Hanoi es uno de los rompecabezas tradicionales en los videojuegos de la compañía canadiense BioWare , en particular, " Jade Empire ", " Star Wars: Knights of the Old Republic ", " Mass Effect " y "Dragon Age: Inquisition". . También se encuentran en la misión Leyenda de Kyrandia II.

Notas

↑ 1 2 Martin Gardner, Acertijos matemáticos y diversión
↑ Petkovic, Miodrag. Rompecabezas famosos de grandes matemáticos (neopr.) . - Librería AMS, 2009. - Pág. 197. - ISBN 0-8218-4814-3 .
↑ Graham, Ronald. Matemáticas concretas: una base para la informática . - Addison-Wesley , 1998. - Pág. 21. - ISBN 0201558025 .
↑ Solución al problema avanzado 3819, American Mathematical Monthly , 1941.
↑ Korf, Richard E. y Ariel Felner. Progreso reciente en la búsqueda heurística: un estudio de caso del problema de las torres de cuatro clavijas de Hanoi // IJCAI : diario. - 2007. - Pág. 2324-2329 . Archivado desde el original el 24 de septiembre de 2015.
↑ Bousch, T. La quatrieme tour de Hanoi (neopr.) // Bull. belga Matemáticas. soc. Simón Stevin. - 2014. - T. 21 . - S. 895-912 .
↑ Paul Stockmeyer. Variaciones sobre la torre de cuatro postes de Hanoi Puzzle (neopr.) // Congressus Numerantium. - 1994. - T. 102 . - S. 3-12 .
↑ Universidad de Toronto CSC148 Slog (5 de abril de 2014). Consultado: 22 de julio de 2015. (indefinido)
↑ Russel, Eric Frank. Tu jugada // Si . - 1994. - Abril. - S. 34-42 . (Ruso)

Véase también

Prueba de la Torre de Londres

Enlaces

secuencia A007664 en OEIS
Konstantin Knop. Torre de Hanoi . Elementos (22 de octubre de 2012). (indefinido)
Juego en línea Torres de Hanoi

sitios temáticos	Bomba gigante
diccionarios y enciclopedias	Britannica (en línea) Britannica (en línea)
En catálogos bibliográficos	NKC : ph1060364