[SER222] Recurrences (3/7): Solving Towers of Hanoi

Summary

El video explica el algoritmo para resolver el problema de las Torres de Hanoi. Se discute la estrategia de mover los discos más pequeños primero, luego los más grandes y finalmente los restantes más pequeños. Se presenta el pseudocódigo para resolver el rompecabezas con 'n' discos, incluyendo la función 'move' para trasladar un disco de un poste a otro. El vídeo detalla los pasos del algoritmo: mover 'n-1' discos al poste temporal, trasladar el disco más grande al poste final y, por último, mover los 'n-1' discos restantes al poste final. La explicación termina con la pregunta de cuántas movimientos se necesitan para resolver el rompecabezas.

Takeaways

• 🧩 El algoritmo de Torres de Hanoi resuelve el problema mediante la descomposición en subproblemas más pequeños.
• 📜 El pseudo código dado tiene cuatro parámetros: Start (inicio), Temp (temporal), End (final) y n (tamaño de la torre).
• ⚙️ Move es una función encapsulada que realiza la operación básica de mover un disco de una varilla a otra.
• 🧱 El caso base ocurre cuando n es igual a 1, lo que significa que solo hay un disco para mover, resolviéndose sin recurrencia.
• 🔁 Para n mayor que 1, se necesita aplicar tres pasos que involucran la recursividad para mover los discos.
• 🔀 Primero, se mueve el subgrupo de discos n-1 desde Start a Temp usando End como espacio temporal.
• ➡️ Luego, el disco más grande se mueve de Start a End directamente.
• 🔄 Finalmente, se mueve el subgrupo de discos n-1 desde Temp a End para completar el problema.
• 🎯 El algoritmo sigue tres pasos principales: mover una torre pequeña, mover el disco más grande, y mover la torre pequeña nuevamente.
• ⏱️ Al final, la solución busca determinar cuántos movimientos requiere este método para resolver el problema completo.

Q & A

¿Cuál es el propósito del algoritmo de las Torres de Hanói presentado en el video?

El propósito del algoritmo es resolver el problema de las Torres de Hanói para una cantidad 'n' de discos, moviéndolos de una torre inicial a una torre final utilizando una torre temporal.

¿Qué representa la variable 'n' en el pseudocódigo?

'n' representa el tamaño de la torre, es decir, el número de discos que se desea mover de la torre inicial a la torre final.

¿Qué sucede cuando 'n' es igual a 1 en el pseudocódigo?

Cuando 'n' es igual a 1, el problema se reduce a un caso base, donde solo se necesita mover un disco directamente de la torre inicial a la torre final sin necesidad de recurrir a más pasos.

¿Cuáles son los cuatro parámetros principales en el pseudocódigo?

Los cuatro parámetros son: 'Start', la torre de inicio; 'Temp', la torre temporal; 'End', la torre final; y 'n', que indica el número de discos en la torre.

¿Cuál es el rol de la torre temporal en la solución?

La torre temporal ('Temp') se utiliza como espacio intermedio para mover discos mientras se transfiere el resto desde la torre inicial a la torre final.

¿Qué representa la función 'move' en el algoritmo?

La función 'move' encapsula la acción de mover un disco de una torre a otra. Es una operación básica dentro del algoritmo.

¿Cómo se divide el problema cuando 'n' es mayor que 1?

Cuando 'n' es mayor que 1, el problema se divide en tres pasos: primero, mover 'n-1' discos de la torre inicial a la torre temporal; luego, mover el disco más grande a la torre final; y finalmente, mover los 'n-1' discos desde la torre temporal a la torre final.

¿Qué acción se realiza después de mover el disco más grande a la torre final?

Después de mover el disco más grande a la torre final, se mueve la torre de tamaño 'n-1' que estaba en la torre temporal a la torre final.

¿Cuántos movimientos realiza el algoritmo para resolver el problema?

El número total de movimientos realizados por el algoritmo depende de la cantidad de discos 'n'. El video plantea esta pregunta, pero no proporciona una respuesta exacta en este momento.

¿Por qué es importante el uso de la recursión en el algoritmo?

La recursión es crucial en el algoritmo porque permite descomponer el problema en subproblemas más pequeños, moviendo torres parciales de discos hasta que se alcanza el caso base con 'n=1'.

Outlines

00:00

🔍 Introducción a la solución del problema de las Torres de Hanoi

Ruben Acuña presenta el tema del video: la solución algorítmica para el problema de las Torres de Hanoi. Se refiere al concepto general de mover torres más pequeñas, luego discos más grandes, y finalmente una torre más pequeña para resolver el rompecabezas. También introduce el pseudocódigo que explica cómo resolver el problema para un número 'n' de discos y menciona que los movimientos entre varillas ya están modelados en una estructura de datos preexistente.

📜 Explicación del pseudocódigo para las Torres de Hanoi

Se presenta el pseudocódigo para resolver las Torres de Hanoi, que incluye cuatro parámetros principales: 'Start' (varilla inicial), 'Temp' (varilla temporal), 'End' (varilla final), y 'n' (tamaño de la torre). Ruben describe cómo se configuraría el problema inicialmente, con los discos comenzando en la primera varilla, usando la varilla del medio como temporal, y moviéndolos al final en la tercera varilla.

🔢 Caso base del algoritmo

El caso base del algoritmo se activa cuando 'n' es igual a 1, lo que significa que solo hay un disco por mover. En este escenario, el único paso necesario es trasladar el disco de la varilla inicial a la varilla final sin recurrir a recursión, ya que el problema es trivial con un solo disco.

↪️ Descomposición recursiva del problema

Cuando 'n' es mayor que 1, el problema se vuelve más complejo y requiere tres pasos. El primero es mover 'n-1' discos desde la varilla inicial a la varilla temporal, usando la varilla final como apoyo. En este caso, por ejemplo, se moverían dos discos desde la varilla 1 a la varilla 2, dejando el disco más grande en la varilla inicial.

⬆️ Movimiento del disco más grande

Una vez que los discos más pequeños se han movido a la varilla temporal, el disco más grande que queda en la varilla inicial se puede trasladar directamente a la varilla final, que es su destino.

🔄 Completar el rompecabezas

En el último paso, los discos en la varilla temporal se mueven a la varilla final para completar el rompecabezas. Ruben muestra cómo estos tres pasos se corresponden con las líneas de pseudocódigo, y al final del proceso, todos los discos se trasladan de la varilla inicial a la varilla final, resolviendo el rompecabezas.

Keywords

💡Torres de Hanoi

Las Torres de Hanoi es un rompecabezas matemático que consiste en mover un conjunto de discos de diferentes tamaños de una varilla a otra, siguiendo reglas específicas. En el video, se utiliza como un ejemplo práctico para explicar un algoritmo recursivo. El objetivo es mover todos los discos de una varilla inicial a una varilla final utilizando una varilla temporal, lo que refleja la estructura de muchos problemas de computación.

💡Recursividad

La recursividad es un concepto clave en el video, que se refiere a la técnica de resolución de problemas donde una función se llama a sí misma para resolver subproblemas más pequeños. En el contexto de las Torres de Hanoi, se usa para dividir el problema en partes más manejables: mover un subconjunto de discos, luego mover el disco más grande, y finalmente mover el subconjunto restante.

💡Caso base

El caso base es una parte fundamental de un algoritmo recursivo que define la condición en la que la recursión deja de llamarse a sí misma. En el video, el caso base ocurre cuando 'n' es igual a 1, es decir, cuando solo hay un disco para mover, lo que se puede hacer directamente sin recurrir a subproblemas.

💡Algoritmo

Un algoritmo es una secuencia de pasos o instrucciones para resolver un problema. En este caso, el video describe un algoritmo que resuelve el problema de las Torres de Hanoi para 'n' discos, utilizando un enfoque recursivo. El pseudo código presentado ilustra cómo realizar estos pasos de manera sistemática.

💡Varillas

Las varillas representan los tres lugares donde se pueden colocar los discos en el problema de las Torres de Hanoi. Son las posiciones 'Inicio', 'Temporal' y 'Final'. En el video, se hace referencia a cómo se mueven los discos entre estas varillas, siendo la varilla temporal un espacio de almacenamiento intermedio.

💡Discos

Los discos son los objetos que se deben mover entre las varillas en el rompecabezas de las Torres de Hanoi. En el video, se explica cómo el número de discos ('n') afecta la complejidad del problema y cómo el algoritmo los maneja mediante movimientos secuenciales y recursivos.

💡Pseudo código

El pseudo código es una representación informal de un algoritmo que no utiliza un lenguaje de programación específico. En el video, se presenta el pseudo código para resolver el problema de las Torres de Hanoi, lo que facilita la comprensión del proceso lógico detrás del algoritmo sin necesidad de enfocarse en detalles de sintaxis.

💡Función mover

La función 'mover' encapsula la operación básica de mover un disco de una varilla a otra. En el video, se menciona que esta función es fundamental para el algoritmo, ya que cada llamada recursiva se reduce finalmente a una serie de movimientos de discos entre las varillas.

💡Complejidad del algoritmo

La complejidad del algoritmo se refiere a cuántos pasos se necesitan para resolver el problema, especialmente en función del número de discos ('n'). En el video, se plantea la pregunta sobre cuántos movimientos totales son necesarios para completar el rompecabezas, lo que depende de la cantidad de discos y la estructura recursiva del algoritmo.

💡Descomposición del problema

La descomposición del problema es una estrategia clave en el video, que se refiere a dividir un problema grande en subproblemas más pequeños. En el contexto de las Torres de Hanoi, se descompone el problema en mover una torre más pequeña, mover el disco más grande, y luego mover de nuevo la torre más pequeña.

Highlights

Introduction to the Towers of Hanoi algorithm

Explanation of the general strategy for solving the puzzle

Pseudo code for an algorithm to solve Towers of Hanoi with 'n' disks

Assumptions about the data structure for rods and disks

Encapsulation of the move functionality

The importance of the move operation in the algorithm

Parameters of the Towers of Hanoi pseudo code

Role of Start, Temp, and End rods in the algorithm

Explanation of the tower size variable 'n'

Base case for a tower of size one

Recursive steps for towers greater than one disk

First recursive step: Moving n-1 disks to the temp rod

Second recursive step: Moving the largest disk to the end rod

Third recursive step: Moving the n-1 disks from temp to end

Mapping the recursive steps to the pseudo code

Completion of the puzzle by moving all disks to the end rod

Question about the number of moves required by the algorithm

Transcripts

- [Ruben Acuña] In this video, I want to discuss

the actual algorithm for solving Towers of Hanoi.

So, as previously discussed,

there is kind of this general notion

of how we can move smaller towers and then larger disks

and then a smaller tower again,

in order to solve the general problem, right?

Solve the general puzzle.

So the pseudo code that does it is actually here on

the right hand side.

So this is the pseudo code for an algorithm

that could play a game of Towers of Hanoi for

an "n" sized number of disks.

So we have some basic assumptions.

First of all we're going to say that the rods and disks

are already modeled with some data structure,

we're not gonna talk about that right,

this is just pseudo code.

And then that's gonna be kind of encapsulated

by something called move.

So there's some bit of functionality out there

which encapsulates moving a disk

from one particular rod to another one.

Alright, so we're just gonna say that's out there.

Um, and that will actually end up being,

because that's kind of a basic operation

and it will take a little bit of time,

be the thing that we write a growth function for.

Okay, so let's take a look at the code

on the right hand side.

So we have our Towers of Hanoi pseudo code here.

So you can see that there are four parameters

to this bit of pseudo code.

So, Start is basically, what rod do we want to start on,

Temp is the working one, right?

There's three that are available to us, right?

So where can we put kind of spare things.

And then End which is the last rod right?

The one where I wanna move everything to it.

Final variable there, n, is the tower size, right?

How many disks do I want to use?

So the first time I call this, right, if I were trying to

solve the Towers of Hanoi problem, I would say that Start is

one, because all the disks initially start there

on the left hand side.

They use the middle rod as a kind of, a temporary space

to move things, and I'm trying to move

them to the End, right? The third most, rod.

In the example we did by hand we had three disks

so, n initially would be three.

That's how things would start out.

Take a look at this program, what exactly is happening?

First we have, if n equal one.

So this is our, kind of our base case, right,

the simplest possible puzzle I could solve,

happens to be when I'm moving one disk from

one tower to another.

In that case, basically it's given

that it's gonna work for me.

So, in that case if I have a tower of size one

what I, the only thing I need to do is call move

to go from Start to End.

So I'm moving one final piece.

So, that's the simplest tower I could possibly move,

don't require any recursion there, everything is good.

Else, right, n is the greater than one, so it's at least two

I need to do a little bit of more work.

So there's three steps in here,

that we had basically talked about when we looked

at doing the trace by hand of

how exactly we'd move things along.

So the first line is going to move n minus one disks

from the first tower,

to the, uh last tower.

Well to the temp tower.

So the parameters, right, the parameters

are set up so the first thing is you're,

where you're getting disks from,

the last thing is where you're getting disks to.

So what this line is saying is,

take disks from the start tower, starting tower,

use the n tower as a temporary and the temporary

as the target, right, so we're moving n minus to, right,

meaning for example here, n minus one,

meaning here for example two items, right,

from that first tower to the middle tower.

Alright, that's where we're doing our, kind of our first

partial decomposition of this tower, right?

To move a couple parts of it.

So we do that, first thing.

And here right, the way this code is looking, right, is

we're moving from Start to Temp, right.

So, we're moving from rod one to rod two.

Rod three is where our End is,

we don't want to touch that right now.

The second step is to move from Start to End, right.

After you move that, that smaller tower, right the

n minus one tower, off of that starting rod,

that means the only thing left there is the biggest disk.

So that biggest disk, I can move it where it finally belongs

right, it belongs on the right hand side, on that peg.

So that moves from one to three.

Right, this is from one to two, this is from

one...

to three.

Then we can go over here and basically say,

okay I need to finish my work,

which my work is to then to go from,

from the middle point, right, the Temp, right,

which is, which is number two, over to number three.

Right, I have at this point, right, so, so,

if I jump back to my other slide for a second,

alright, my initial process is basically to say

okay I'm going to from that initial state to the state

where I have, the n minus one tower moved to the middle,

right, that's, that's here.

Then I also move that one piece,

from the first to the very end,

and then once I have that,

I move the two pieces from the middle to the very end.

Which gets me this over here.

Right, so those are the three things that are basically

the map to these different pieces of code over here, right.

We do, we move a smaller tower,

move one piece and then move the smaller tower.

At the end of the day, well hey, we've moved everything

from the starting peg to the ending one.

So in that case, right, we've moved everything along

and we've at least, you know, solved the puzzle.

So now the question is, just how many moves does

this particular method make?