Tabla de contenido:
Definición - ¿Qué significa Backtracking?
Backtracking es un algoritmo para capturar algunas o todas las soluciones a problemas computacionales dados, especialmente para problemas de satisfacción de restricciones. El algoritmo solo puede usarse para problemas que pueden aceptar el concepto de una "solución candidata parcial" y permite una prueba rápida para ver si la solución candidata puede ser una solución completa. El retroceso se considera una técnica importante para resolver problemas de satisfacción de restricciones y rompecabezas. También se considera una gran técnica para analizar y también forma la base de muchos lenguajes de programación lógica.
Techopedia explica Backtracking
El retroceso ayuda a resolver un problema general al encontrar una solución al primer subproblema y luego intenta recursivamente resolver otros subproblemas basados en la solución del primer problema. Si el problema actual no se puede resolver, el paso se remonta y la siguiente solución posible se aplica a los pasos anteriores, y luego continúa. De hecho, una de las cosas clave en el retroceso es la recursividad. También se considera como un método de búsqueda exhaustiva utilizando divide y vencerás. Un algoritmo de retroceso finaliza cuando no hay más soluciones para el primer subproblema.
Backtracking es un algoritmo que puede ayudar a lograr la implementación del no determinismo. Se necesita una búsqueda en profundidad de un espacio de emisión determinado. Se utiliza principalmente en lenguajes de programación lógica como Prolog. Dondequiera que se pueda aplicar el retroceso, es más rápido que la técnica de fuerza bruta, ya que elimina una gran cantidad de candidatos con una sola prueba.
