Algoritmo de retroceso
Un algoritmo de retroceso es un algoritmo de resolución de problemas que utiliza un enfoque de fuerza bruta para encontrar la salida deseada.
El enfoque de fuerza bruta prueba todas las soluciones posibles y elige las soluciones deseadas/mejores.
El término retroceder sugiere que si la solución actual no es adecuada, retroceda y pruebe otras soluciones. Por lo tanto, la recursividad se utiliza en este enfoque.
Este enfoque se utiliza para resolver problemas que tienen múltiples soluciones. Si desea una solución óptima, debe optar por la programación dinámica.
Árbol de espacio de estado
Un árbol de estado espacial es un árbol que representa todos los estados posibles (solución o no solución) del problema desde la raíz como estado inicial hasta la hoja como estado terminal.
Algoritmo de retroceso
Backtrack(x)
if x is not a solution
return false
if x is a new solution
add to list of solutions
backtrack(expand x)Ejemplo de enfoque de retroceso
Problema: Quieres encontrar todas las formas posibles de colocar 2 niños y 1 niña en 3 bancos. Restricción: La niña no debe estar en el banco del medio.
Solución: ¡Hay un total de 3! = 6 posibilidades. Probaremos todas las posibilidades y obtendremos las posibles soluciones. Probamos recursivamente todas las posibilidades.
Todas las posibilidades son:
El siguiente árbol de espacio de estados muestra las posibles soluciones.
Aplicaciones de algoritmos de retroceso
- Para encontrar todos los caminos hamiltonianos presentes en un gráfico.
- Para resolver el problema de N Queen.
- Problema de resolución de laberintos.
- El problema de la gira del Caballero.
