Algoritmo De Tremaux
440fc-01.jpg?w=320&h=240245px-Portrait_de_Pierre_Tr%C3%A9maux.jpg
Al comienzo de un capítulo de los Simpson la familia se pierde en un laberinto de maíz del que logran salir gracias a Lisa que dice “Por fin, sabía que resolveríamos el laberinto gracias al algoritmo de Tremaux”. Marge y los niños consiguen salir del laberinto gracias al algoritmo de Tremaux.
Charles Tremaux fue un ingeniero francés del siglo XIX. Él fue el que inventó este algoritmo, enunciado 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. 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.
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.
La clave está en no seguir el mismo camino dos veces.
Tremaux'_Methode_-_animiertes_Beispiel.gif
Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License