domingo, 14 de marzo de 2010
Torre de Hanói
Introducción
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas
Pseudocódigo
Pseudocodigo Algoritmo Recursivo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
Algoritmo recursivo
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
Algoritmos iterativos
Antes de buscar un algoritmo iterativo resaltemos de nuevo un detalle importante. Aunque estamos hablando de varios algoritmos, la solución óptima (la de menos movimientos, que como hemos visto antes, para n = 8 es de 255) es única. O sea, la serie de movimientos que resulta de aplicar un algoritmo (óptimo) cualquiera será siempre la misma.Una observación clave para encontrar un algoritmo iterativo es que el disco más pequeño se mueve una vez sí, una vez no.
El primer movimiento hay que hacerlo con el disco 1. Está claro que después de mover el disco 1 (en cualquier ocasión) se debe mover un disco distinto (si no queremos perder el tiempo moviendo el mismo disco varias veces). Este movimiento debe hacerse entre los dos postes que no contienen el disco 1. A continuación no nos quedan más que dos alternativas: deshacer el último movimiento, lo que no tiene sentido, o volver a mover el disco 1.
Además, cuando le toque le toque el turno a un disco distinto de 1, el movimiento estará perfectamente determinado ya que sólo intervendrán dos postes, y entre dos postes sólo hay un movimiento posible. Así que sólo puede haber duda cuando hay que mover el disco menor. Se sale de esta duda respetando una cualquiera de las siguientes reglas.
-El disco pequeño se debe mover siempre cíclicamente en el mismo sentido: hacia la derecha (de A a B, de B a C y de C a A) o hacia la izquierda (de A a C, de C a B y de B a A), según el número de discos sea par o impar respectivamente.
-El disco pequeño se debe colocar siempre, bien sobre un disco de número par, bien como único disco en el poste de destino (C) si el número de discos es impar o en el otro (B) si es par.
Teniendo en cuenta la primera regla se construye un algoritmo descubierto por Peter Buneman y Leon Levy.
1.-Si n es par, mueve el disco 1 hacia la derecha. Si es impar, muévelo hacia la izquierda.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.
Teniendo en cuenta la segunda regla, el algoritmo podría ser el siguiente.
1.-Si es posible, lleva el disco 1 sobre un disco de número par. Si no es posible, llévalo al poste B si n es par o a C si n es impar.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.
Para hacer este algoritmo más fácil de aplicar se pueden pintar los discos pares e impares de dos colores distintos. Incluso se puede pintar la base en tres trozos, como se ve en el dibujo (es como si los trozos de base fueran los discos n+1, n+2 y n+3).
Con esta versión del rompecabezas el último algoritmo se puede redactar así:Lleva el disco 1 sobre un disco (o trozo de base) que no sea de su mismo color. -Si todos los discos están en C, fin. Si no, mueve un disco distinto de 1 y vuelve al paso 1. - El disco más pequeño no es el único que no se coloca nunca sobre otro de distinto color, en ningún momento hay dos discos del mismo color juntos.
Suscribirse a:
Entradas (Atom)
