Pongámonos en situación. Has ido a un parque de atracciones o a un parque urbano con tus amigos. Habéis visto que tiene un laberinto y os ha parecido divertido jugar a perderos en él, pero ahora no podéis salir porque no encontráis la puerta. ¿Cómo puedes escapar? Como en todo en esta vida, las matemáticas tienen mucho que decir y te pueden sacar del apuro.
Vamos a ver dos procedimientos para que escapemos del laberinto. En este caso las matemáticas te van a salvar la vida pero debes de tener paciencia, ya que no existe (de momento) un algoritmo para encontrar la salida de la forma más rápida posible. Nos tendremos que conformar con dos sencillos métodos que tarde o temprano encontrarán la puerta, pero su rapidez dependerá de la suerte respecto a la posición en la que lo empieces a aplicar.
Algoritmo de Tremaux
Charles Tremaux fue un ingeniero francés del siglo XIX. Él fue el que inventó este algoritmo para escapar de un laberinto. Actualmente es el más eficiente, y nos asegura la escapatoria de cualquier tipo de laberinto sin importar su forma.
El algoritmo es el siguiente:
De alguna manera debemos de ir marcando el camino que estamos haciendo. Cuando llegamos a un cruce da igual hacia donde sigamos, siempre que no hayamos pasado antes por ahí. Y también es importante que si llegamos a un punto sin salida, volvamos al cruce anterior. Si en dicho cruce ya hemos hecho todos los posibles caminos, retrocedemos al cruce anterior a éste. Y así sucesivamente.
En resumen, este algoritmo es una forma ordenada de probar todos los caminos posibles para escapar. Por eso, podemos tener suerte y acertar a la primera, o podemos ir fallando incluso hasta el último caso. Lo bueno, es que por lo menos no repetiremos ningún camino, y como el laberinto es finito, llegará un momento en el que salgamos seguro.
Como curiosidad, en un capítulo de Los Simpson titulado “¡Alto! O mi perro dispara”, en el que los miembros de la familia juegan a perderse en un laberinto, Lisa utiliza el Algoritmo de Tremaux para salir sana y salva.
Regla de la mano derecha
Este método es muy sencillito, y se utiliza desde hace cientos de años para salir de laberintos, catacumbas o galerías subterráneas en las que es fácil perder la noción de espacio.
El algoritmo es el siguiente:
Cuando decidimos que queremos salir, ponemos nuestra mano derecha (también es análogo para la izquierda) apoyada en la pared, y andamos con la mano así hasta que lleguemos a la salida. Es importante que nunca quitemos la mano de la pared. Así nos aseguramos que pasamos por todas las paredes, y por tanto encontraremos la puerta que estará en una pared.
Simple, ¿verdad? Pero este algoritmo tiene un par de aspectos negativos. El primero es que, al igual que el algoritmo anterior, la velocidad de escapatoria dependerá de la suerte por la posición en la que empecemos.
La otra pega, más importante todavía, es que pueden existir modelos de laberinto en el que no sea efectivo este método, y nos quedemos dando vueltas infinitamente. Un ejemplo de un laberinto así sería uno formado por círculos concéntricos, cuya salida esté en medio, y nosotros nos quedemos dando vueltas alrededor de uno de esos círculos.
Bueno, otro ejemplo de que las matemáticas sirven para todo, incluso para sacarte de situaciones un poco apuradas.
@JcVirin
la regla de la mano derecha tiene solucion. Si mrcamos el camino, al repetir debemos cambiar de mano al siguiente cruce. Sigue siendo mejor que el de tremaux
Cierto Pablo, gran aporte. En dónde se puede ver un artículo explicando este método ?