En este tutorial, aprenderá qué es un algoritmo de retroceso. Además, encontrará un ejemplo de un enfoque de retroceso.
Un algoritmo de retroceso es un algoritmo de resolución de problemas que utiliza un enfoque de fuerza bruta para encontrar el resultado deseado.
El enfoque de fuerza bruta prueba todas las soluciones posibles y elige las mejores o deseadas.
El término retroceso sugiere que si la solución actual no es adecuada, retroceda y pruebe otras soluciones. Por tanto, en este enfoque se utiliza la recursividad.
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 espacial estatal
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.
Árbol espacial estatal
Algoritmo de retroceso
Retroceder (x) si x no es una solución devolver falso si x es una nueva solución agregar a la lista de soluciones retroceder (expandir x)
Ejemplo de enfoque de retroceso
Problema: desea 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. Intentaremos todas las posibilidades y obtendremos las posibles soluciones. Intentamos de forma recursiva todas las posibilidades.
Todas las posibilidades son:
Todas las posibilidades
El siguiente árbol del espacio de estados muestra las posibles soluciones.
Árbol de estados con todas las soluciones
Aplicaciones de algoritmos de retroceso
- Encontrar todos los caminos hamiltonianos presentes en un gráfico.
- Para resolver el problema de N Queen.
- Problema de resolución de laberinto.
- El problema de la gira del Caballero.
