Backtracking: Método de resolución de problemas por etapas

QUÉ ES BACKTRACKING

Este método se conoce como fuerza bruta: se generan todos los casos posibles y se testean uno a uno hasta encontrar las soluciones necesarias (a veces basta con encontrar una, en otras ocasiones hay que encontrar todas ellas, o quedarse con la mejor).

Sin embargo, en muchos de estos problemas no es necesario crear completamente un caso para ver si es una solución o no. Cuando resolver un problema puede hacerse por etapas se puede comprobar paso a paso si se está creando una solución o si se han tomado decisiones que no conseguirán resolver el problema: en cada etapa se estudian las propiedades cuya validez ha de examinarse con objeto de seleccionar las adecuadas para proseguir con el siguiente paso. La gestión de las etapas, las posibles decisiones que se toman y las relaciones entre ellas, suponen la generación de un árbol de decisiones.

En los nodos se encuentran las soluciones parciales, y los enlaces entre ellos son las decisiones tomadas para cambiar de etapa.

El avance a lo largo del árbol se detiene cuando se llega a una situación en que no puede tomarse ninguna decisión que permita obtener una solución, o cuando efectivamente se llega a resolver el problema.

Backtracking (o Vuelta Atrás) es una técnica de recursión intensiva para resolver problemas por etapas, que utiliza como árbol de decisiones la propia organización de la recursión. Cuando se “avanza” de etapa se realiza una llamada recursiva, y cuando se “retrocede” lo que se hace es terminar el correspondiente proceso recursivo, con lo que efectivamente se vuelve al estado anterior por la pila de entornos creada en la recursión. Como el árbol de decisiones no es una estructura almacenada en memoria, se dice que Backtracking utiliza un árbol implícito y que se habitualmente se denomina árbol de expansión o espacio de búsqueda. Básicamente, Backtracking es un método recursivo para buscar de soluciones por etapas de manera exhaustiva, usando prueba y error para obtener la solución completa del problema añadiendo decisiones a las soluciones parciales.