Cómo resolver el problema de la Torre de Hanoi: Una guía ilustrada del algoritmo

Original article: How to Solve the Tower of Hanoi Problem - An Illustrated Algorithm Guide

Antes de empezar, hablemos de qué es el problema de la Torre de Hanoi. Bueno, este es un divertido juego de rompecabezas en el que el objetivo es mover una pila completa de discos desde la posición de origen a otra posición. Se siguen tres reglas simples:

1.Solo se puede mover un disco a la vez.
2.Cada movimiento consiste en tomar el disco superior de una de las pilas y colocarlo encima de otra pila. En otras palabras, un disco solo se puede mover si es el disco superior de una pila.
3.No se puede colocar un disco más grande encima de un disco más pequeño.

Ahora, intentemos imaginar un escenario. Supongamos que tenemos una pila de tres discos. Nuestro trabajo es mover esta pila del origen A al destino C. ¿Cómo hacemos esto?

Antes de que podamos llegar allí, imaginemos que hay un punto intermedio B.

Podemos usar a B como ayudante para terminar este trabajo. Ahora estamos listos para seguir adelante. Veamos cada uno de los pasos:

Mueve el primer disco de A a C
Mover el primer disco de A a B
Mueva el primer disco de C a B
Mueve el primer disco de A a C
Mueva el primer disco de B a A
Mueva el primer disco de B a C
Mueve el primer disco de A a C
¡Excelente! Hemos resuelto nuestro problema.

Puedes ver la imagen animada de arriba para una mejor comprensión.

Ahora, intentemos construir el algoritmo para resolver el problema. Espera, tenemos una nueva palabra aquí: "Algoritmo". ¿Qué es eso? ¿Alguna idea? No hay problema, vamos a ver.

¿Qué es un algoritmo?

Un algoritmo es uno de los conceptos más importantes para un desarrollador de software. De hecho, creo que no solo es importante para el desarrollo o la programación de software, sino para todos. Los algoritmos nos afectan en nuestra vida cotidiana. Veamos cómo.

Supongamos que trabaja en una oficina. Así que cada mañana haces una serie de tareas en secuencia: primero te levantas, luego vas al baño, desayunas, te preparas para la oficina, sales de casa, luego puedes tomar un taxi o un autobús o empezar a caminar hacia la oficina y, después de un tiempo determinado, llega a su oficina. Puedes decir que todos esos pasos forman un algoritmo.

En términos simples, un algoritmo es un conjunto de tareas. Espero que no hayas olvidado los pasos que hicimos para mover tres pilas de discos de A a C. También puedes decir que esos pasos son el algoritmo para resolver el problema de la Torre de Hanoi.

En Matemáticas y Ciencias de la Computación; un algoritmo es una especificación inequívoca de cómo resolver una clase de problemas. Los algoritmos pueden realizar tareas de cálculo, procesamiento de datos y razonamiento automatizado. —

Si observas esos pasos, puedes ver que estábamos haciendo la misma tarea varias veces: mover discos de una pila a otra. Podemos denominar a estos pasos como recursión.

Recursión

Recursion es estar llamando a la misma acción desde esa acción. Al igual que en la imagen de arriba.

Entonces, hay una regla para hacer cualquier trabajo recursivo: debe haber una condición para detener la ejecución de esa acción. Espero que entiendas los conceptos básicos sobre la recursividad.

Ahora, intentemos construir un procedimiento que nos ayude a resolver el problema de la Torre de Hanoi. Estamos tratando de construir la solución usando pseudocódigo. El pseudocódigo es un método para escribir código de computadora utilizando el idioma inglés.

torre(disco, origen, intermedio, destinacion)
{

}

Este es el esqueleto de nuestra solución. Tomamos el número total de discos como argumento. Luego, debemos pasar el origen, el lugar intermedio y el destino para que podamos entender el mapa que usaremos para completar el trabajo.

Ahora necesitamos encontrar un estado terminal. El estado terminal es el estado en el que ya no vamos a llamar a esta función.

IF disco is igual 1

En nuestro caso, este sería nuestro estado terminal. Porque cuando haya un disco en nuestra pila, entonces es fácil hacer ese paso final y luego nuestra tarea estará completa. No te preocupes si no te queda claro. Cuando lleguemos al final, este concepto será más claro.

Muy bien, hemos encontrado nuestro punto de estado terminal donde movemos nuestro disco al destino de esta manera:

mover disco desde el origen a nuestra destinación

Ahora volvemos a llamar a nuestra función pasando estos argumentos. En ese caso, dividimos la pila de discos en dos partes. El disco más grande (disco n) está en una parte y todos los demás discos (n-1) están en la segunda parte. Allí llamamos al método dos veces para -(n-1).

torre(disco - 1, origen, destinacion, intermedio)

Ahora pasaremos a un ejemplo de pseudocódigo más realista. Usaremos total_discos_on_stack — 1 como un argumento. Después de ello, procedemos a mover nuestro disco nuevamente de esta forma:

mover disco desde el origen a la destinación

Después de eso, volvemos a llamar a nuestro método así:

torre(disco - 1, intermedio, origen, destinacion)

Veamos el pseudocódigo:

torre(disco, origen, inter, dest)

IF disco is equal 1, THEN
       mover disco desde el origen a la destinación
   ELSE
       torre(disco- 1, origen, destinacion, intermedio)   // Step 1
       mover disco desde el origen a la destinación       // Step 2
       torre(disco - 1, intermedio, origen, destinacion)  // Step 3
   END IF
   
END

Este es el árbol para tres discos:

Este es el código completo en Ruby:

def tower(disk_numbers, source, auxilary, destination)
  if disk_numbers == 1
    puts "#{source} -> #{destination}"
    return
  end
  tower(disk_numbers - 1, source, destination, auxilary)
  puts "#{source} -> #{destination}"
  tower(disk_numbers - 1, auxilary, source, destination)
  nil
end

Empleamos tower(3, 'source','aux','dest')

Resultado:

source -> dest
source -> aux
dest -> aux
source -> dest
aux -> source
aux -> dest
source -> dest

Se necesitaron siete pasos para que tres discos llegaran al destino. A esto lo llamamos un método recursivo.

Cálculos en la complejidad del tiempo y el espacio

Complejidad Temporal

Cuando ejecutamos código o una aplicación en nuestra máquina, lleva tiempo: ciclos de CPU. Pero no es lo mismo para todas las computadoras. Por ejemplo, el tiempo de procesamiento de un core i7 y de un dual core no es el mismo. Para resolver este problema existe un concepto utilizado en informática llamado complejidad temporal.

La complejidad del tiempo es un concepto en informática que se ocupa de la cuantificación de la cantidad de tiempo que tarda un conjunto de código o algoritmo en procesarse o ejecutarse en función de la cantidad de entrada.

En otras palabras, la complejidad del tiempo es esencialmente eficiencia, o cuánto tarda una función de programa en procesar una entrada determinada.

La complejidad temporal de los algoritmos se expresa más comúnmente utilizando la Cota superior asintótica. Una notación asintótica para representar la complejidad del tiempo.

Ahora, el tiempo requerido para mover n discos es T(n). Hay dos llamadas recursivas para (n-1). Hay una operación de tiempo constante para mover un disco desde el origen hasta el destino, sea m1. Por lo tanto:

T(n) = 2T(n-1) + m1    ..... eq(1)

Y también:

T(0) = m2, a constant   ...... eq(2)
From eq (1)
T(1) = 2T(1-1) + m1
     = 2T(0)+m1
     = 2m2 + m1 ..... eq(3) [From eq 2]
T(2) = 2T(2-1) + m1
     = 2T(1) + m1
     = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)]
T(3) = 2T(3-1) + m1
     = 2T(2) + m1
     = 8m2 + 4m1 + 2m1 + m1  [From eq(4)]

A partir de estos patrones, eq(2) hasta el último, podemos decir que la complejidad temporal de este algoritmo es O(2^n) u O(a^n) donde a es una constante mayor que 1. Por lo tanto, tiene una exponencial complejidad del tiempo. Para el aumento único del tamaño del problema, el tiempo requerido es el doble del anterior. Esto es computacionalmente muy costoso. La mayoría de los programas recursivos toman un tiempo exponencial, y por eso es muy difícil escribirlos iterativamente.

Complejidad Espacial

Después de la explicación del análisis de la complejidad del tiempo, creo que ahora puedes adivinar qué es esto... Este es el cálculo del espacio requerido en RAM para ejecutar un código o una aplicación.

En nuestro caso, el espacio para el parámetro de cada llamada es independiente de n, lo que significa que es constante. Que sea J. Cuando hacemos la segunda llamada recursiva, la primera ha terminado. Eso significa que podemos reutilizar el espacio después de terminar el primero. Por eso:

Por tanto:

T(n) = T(n-1) + k .... eq(1)
T(0) = k, [constant] .... eq(2)
T(1) = T(1-1) + k
     = T(0) + k
     = 2K
T(2) = 3k
T(3) = 4k

Entonces la complejidad del espacio es O(n).

Después de estos análisis, podemos ver que la complejidad temporal de este algoritmo es exponencial, pero la complejidad espacial es lineal.

Conclusión
A partir de este artículo, espero que ahora puedas entender el rompecabezas de la Torre de Hanoi y cómo resolverlo. Además, traté de brindarle una comprensión básica sobre los algoritmos, su importancia, recursividad, pseudocódigo, complejidad temporal y complejidad espacial.