Backtracking

En esta ocasión hablaremos de los algoritmos backtracking (algoritmos de vuelta atrás), este método para la resolución de problemas funciona a prueba y error, lo cual lo hace un algoritmo de mucho costo en cuanto a tiempo para encontrar la solución, ya que el probara todas las opciones para llegar a solucionar el problema, pero esto nos asegurara la mejor solución al problema planteado.

La más antigua referencia a Backtracking, es la historia del hilo de Ariadna en la mitología griega. Su padre, el rey Minos de Creta detentaba su tiránico poder sobre su isla y por conquista sobre Atenas. El tributo que pedía de los atenienses consistía en grupos de jóvenes que entraban a su laberinto donde habitaba el Mino tauro (mitad hombre, mitad toro) para encontrar la muerte a manos de éste. El héroe ateniense Teseo se ofreció voluntariamente a acompañar a un grupo dejóvenes que se iban a sacrificar para salvar a Atenas de ésta cruel tradición.

Ariadna se enamoró de Teseo y le regaló un ovillo de hilo dorado para que no se perdiera en el laberinto. La idea era que Teseo desenrollara el ovillo a medida que avanzara por el laberinto, si llegaba a un callejón sin salida tenía que volver atrás y enrollar el hilo hasta llegar al punto donde había escogido dicho camino para intentar una ruta alternativa. El Backtracking funcionó, Teseo asesinó al Mino tauro y escapó del laberinto, y de la isla de Creta con los jóvenes y con Ariadna.

Lo primero que se hace para identificar un problema digno de Backtracking es pensar cómo lo resolverá el usuario como humano; si su mejor solución es empezar con algunas condiciones iniciales e ir probando caminos, hasta llegar a un punto en donde no hay solución y regresar entonces un poco para explorar por otro lado, está pensando en función de Backtracking. Lo más importante para hacer un Backtracking es hacer un “retroceso mínimo”, o sea, no destruir todo si no pudo encontrar una solución, sino sólo borrar lo necesario para poder seguir explorando sin perder todo el camino que has recorrido.

El caso más similar a lo que se debe hacer para implementar un Backtracking es pensar en la manera como se sale de un laberinto, primero se amarra un hilo en el principio del laberinto y se va decidiendo sobre cada bifurcación hacia dónde va a seguir; al momento de encontrar un callejón sin salida sabe que debe regresar y buscar por el lado contrario; si los dos lados no lo llevan a la salida entonces podrá marcar esa bifurcación con alguna señal, regresar más y buscar otro camino. Es lo que se haría en pocas palabras, porque nunca se debería regresar hasta el principio al encontrar un callejón sin salida, se debería retroceder lo menos posible siguiendo al hilo que indica lo que se ha recorrido y no se debería volver a entrar a caminos ya marcados.

La técnica de Backtracking es usada en muchos ámbitos de la programación, por ejemplo, para el cálculo de expresiones regulares o para tareas de reconocimiento de texto, desarrollo de video juegos y de sintaxis de lenguajes regulares. También es usado incluso en la implementación de algunos lenguajes de programación, tales como Planner o Prolog y da soporte a muchos algoritmos en inteligencia artificial.

Dado que en cada llamada recursiva se invoca 2 veces a la misma función y como hay n vocaciones por cada llamada recursiva, su complejidad es: 0(2n)

Note que al tener una complejidad exponencial, el Backtracking no es una técnica muy eficiente, pero su ventaja es que siempre encontrará la solución si es que existe y si tuviéramos todo el tiempo del mundo.

Conclusión
Como se ha mencionado el backtracking es una herramienta muy útil, ya que nos ayuda a resolver problemas grandes en los que no se sabe cual camino tomar, este algoritmo ira buscando la mejor solución a prueba y error, si bien es una algoritmo que nos dará la respuesta requerida no es un algoritmo eficiente, es por esta razón que es un algoritmo heurístico.

Es interesante como cosas tan sencillas se pueden aplicar a la resolucion de problemas diario, como resolver el cubo de Rubik o cubo magico.