No, no tiene que ver con la recursividad, específicamente, la recursividad verdadera enumeraría todo el espacio de búsqueda.
Si bien usualmente usa la recursividad como un detalle de implementación para atravesar el espacio de búsqueda, intencionalmente “se rinde” sin enumerar recursivamente todos los nodos. Esto se llama “podar” el espacio de búsqueda; Se implementa mediante un procedimiento de rechazo .
También tiene un procedimiento de aceptación , que acepta soluciones completas.
- Cómo paralelizar un método recursivo en Java
- ¿Qué lenguaje de programación debo usar para implementar algoritmos que creo?
- ¿La programación lineal admite un algoritmo de tiempo fuertemente polinómico?
- ¿Por qué un árbol se llama estructura de datos?
- Cómo crear un sistema de clasificación que dependa de tres variables (nivel, resultado y tiempo) cuanto más altas sean las dos primeras, mejor, mientras que por un tiempo, un valor menor es mejor
En el límite, si el procedimiento de rechazo siempre devuelve verdadero , entonces es el equivalente del descenso recursivo, pero no necesariamente enumerará todo el árbol, de la forma en que lo haría la recursividad verdadera (ver más abajo).
Dado que implica la poda, un algoritmo de retroceso puede podar cuando una profundidad es demasiado profunda, por ejemplo: mirar hacia adelante N se mueve en un simple programa de juego de ajedrez se vuelve mucho más caro computacionalmente, cuanto mayor sea su valor para N.
Por lo tanto, puede usarlo para limitar el gasto computacional, si tiene una capacidad de cálculo limitada en todo el dominio del tiempo. De esta manera, se puede utilizar como un enfoque para el problema P vs. NP en la teoría de la computabilidad. No necesariamente encontrará una solución … pero puede que sí .
Un ejemplo más clásico es un programa de resolución de laberintos, que se detiene después de encontrar una solución: se considera clásico porque la mayoría de los laberintos tienen una solución única y válida, y se cierra cuando se resuelve el laberinto.
También se puede usar para problemas de satisfacción de restricciones, donde puede detenerse después de cumplir con la restricción o encontrar N nodos que cumplan con la restricción, pero renunciar a la búsqueda de nodos adicionales.
Si se usa para la satisfacción de restricciones, hay un sesgo izquierdo inherente en los resultados que obtienes, ya que es un descenso profundo, por lo que no es útil para los motores de búsqueda que desean vender publicidad, ya que no obtienes el contexto completo a los resultados más relevantes.
