Retroceder el tiempo es el deseo de muchas personas en el mundo; recrear buenos momentos o incluso cambiarlos, las acciones que cómo seres humanos realizamos naturalmente, lamentablemente nosotros no tenemos esa habilidad, pero, el backtracking sí. Este concepto se puede definir como un algoritmo general para encontrar todas (o algunas) de las soluciones en algunos problemas computacionales, en particular los problemas de satisfacción de restricciones; que aumenta gradualmente los candidatos a las soluciones y abandona a un candidato ("retrocesos") tan pronto como determina que el candidato no puede ser completado a una solución válida.
Generalmente, utilizamos el ejemplo del juego de ajedrez por computadora; cuando hacemos una jugada y esta nos da una consecuencia, tenemos la opción de retrocederla y corregirla buscando otra solución, es decir, tendríamos la capacidad de corregir nuestro pasado para tener un mejor futuro. En investigación de Andrea (2017) podemos ver la publicación de un buen artículo sobre los algoritmos de «vuelta atrás»: Backtracking Explained. Se trata de una estrategia normalmente recursiva para resolver problemas como los de los laberintos, la colocación de piezas y similares, en los que mediante una búsqueda en profundidad se puede dar con la solución.
Dependiendo del tipo de problema que se tenga que resolver, el uso del Backtracking y sus variantes nos ayuda mucho a la hora de encontrar la solución si esta es existente, pero cuando se agregan más soluciones o la búsqueda de la mejor de todas las soluciones se puede presentar una serie de desventajas y ventajas tales como las siguientes:
Ventajas
-
Si existen una o las soluciones el backtracking las calcula.
-
Es relativamente sencillo de implementar en los problemas a resolver.
-
Se adapta a características en específico del problema.
Desventajas
-
Si la solución es infinita, y si esta existe, no se encontrará nunca.
-
Consume mucha memoria para tener que almacenar los ciclos de búsqueda.
-
Se necesita un hardware especial para almacenar la información de los resultados del Backtracking.
Independiente de que se cumplan o no los pros y contras vistos anteriormente el uso de este algoritmo para lograr la solución requerida en el proyecto es de vital importancia si este es aplicado correctamente. Se tiene que tener en cuenta sí se puede ejecutar este tipo de instrucciones sin mayor problema a la hora de compilar y a la vez obtener los resultados esperados en la acción deseada.
Esta estrategia tiene relación con Branch & Bound o también conocido como Ramificación y poda; este método busca una solución como en el método de backtracking, pero cada solución tiene asociado un costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar una solución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientes tienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). La forma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda de la solución óptima al "podar" (pruning) los sub-árboles de descendientes costosos.
El bracktracking se usa en la implementación de los lenguajes de programación tales como Lenguaje de programación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores. Su uso en inteligencia artificial ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el A estrella.
Referencias:
Andrea, I., & A. (2017, 15 noviembre). Los algoritmos recursivos de vuelta atrás (backtracking) explicados y con ejemplos. Microsiervos (Ordenadores). https://www.microsiervos.com/archivo/ordenadores/algoritmos-vuelta-atras-backtracking.html
Uerick, U. (2013, 12 junio). Ventajas y Desventajas del algoritmo Backtracking. Master-Slave Line Following robot. https://uerick.wordpress.com/2013/06/12/ventajas-y-desventajas-del-algoritmo-backtracking/