Tema 5 - Backtracking
El backtracking o vuelta atrás es un esquema que consiste en la busqueda exhaustiva de soluciones a través de llamadas recursivas.
El espacio de posibles soluciones se puede plantear como un arbol
Este tipo de algorimos pueden:
- Encontrar una solución → El algoritmo se detiene (se detienen las llamadas recursivas) cuando encuentra una solución factible
- Encontrar todas las soluciones → El algoritmos se ejecuta hasta que ha comprobado todo el espacio de soluciones
- Encontrar la mejor solución → El algoritmo obtiene todas las soluciones y determina cual es la mejor en función de un criterio dado
Una problema puede resolverse como un algoritmo de backtracking cuando la solución puede expresarse como una n-tupla
() siendo la componente elegida en cada etapa de (llamada recursiva, siendo la profundidad de la recursividad en la que se encontraba el algoritmo en el momento en el que se añadió dicha componente a la solución)Este algoritmo es básicamente un algoritmo de fuerza bruta aunque suele incluir algunas modificaciones para evitar comprobar soluciones infactibles. Aplicando la lógica para evitar hacer pasos innecesarios
Esquema de la técnica
- Si el paso actual es una solución, retornamos de la recursividad con la solución actual
- Si no es solución …
- Iteramos sobre todas las posibles combinaciones de soluciones para la siguiente etapa
- Si la solución de la iteración actual no incumple ninguna restricción del problema
- Se hace la llamada recursiva con esa solución