* b es el factor de ramificación (el número de opciones posibles en cada punto de decisión).
* d es la profundidad del árbol de búsqueda (el número máximo de decisiones que deben tomarse para alcanzar una solución).
Explicación:
El retroceso explora todas las soluciones posibles construyendo sistemáticamente una solución candidata un paso a la vez. En cada paso, verifica si el candidato actual es prometedor (es decir, si podría conducir a una solución válida). Si el candidato es prometedor, el algoritmo explora recursivamente más opciones. Si el candidato no es prometedor (un "callejón sin salida"), el algoritmo * retrocede * al paso anterior e intenta una opción diferente.
Debido a que el algoritmo explora un árbol de posibilidades, y el número de ramas puede crecer rápidamente, la complejidad del tiempo puede volverse muy grande, especialmente a medida que aumenta la profundidad `d`.
¿Por qué exponencial?
Piense en ello como una búsqueda de árboles. Si cada nodo en el árbol tiene `b` niños (factor de ramificación` b`), y la profundidad máxima del árbol es `d`, entonces en el peor de los casos, podría explorar todos los nodos` b^d`.
Consideraciones importantes:
* El peor de los casos: La complejidad del tiempo O (B^d) es típicamente un escenario * peor de los casos *. El tiempo de ejecución real depende en gran medida del problema y la efectividad de la poda (cuán efectivamente puede identificar el algoritmo y evitar explorar ramas no prometedoras).
* poda: Los buenos algoritmos de retroceso emplean varias técnicas de poda para reducir significativamente el espacio de búsqueda. La poda puede mejorar drásticamente el tiempo de ejecución, pero no cambia la naturaleza exponencial inherente del algoritmo en el peor de los casos.
* Ejemplo: Un ejemplo clásico es resolver el problema N-Queens. Para colocar n reinas en un tablero de ajedrez NXN, el factor de ramificación está relacionado con el número de columnas disponibles en una fila, y la profundidad está relacionada con el número de filas. La peor complejidad del tiempo se reduce significativamente al verificar los conflictos (reinas atacantes) en cada paso, que poda muchas de las ramas potenciales.
* Otros factores: Además de `B` y` D`, otros factores pueden afectar el tiempo de ejecución. Por ejemplo, el tiempo que lleva evaluar si una solución candidata es prometedora también puede ser un factor significativo.
* NP-COMPLETENTIS: Muchos problemas que se resuelven con retroceso de retroceso son NP-completos. Esto significa que se cree que no hay un algoritmo de tiempo polinomial para resolverlos en general, y el retroceso a menudo se convierte en un enfoque necesario (aunque a veces ineficiente).
En resumen:
Si bien el retroceso puede ser una poderosa técnica de resolución de problemas, su complejidad de tiempo exponencial significa que es el más adecuado para los problemas donde:
* El tamaño del problema es relativamente pequeño.
* Se pueden emplear estrategias de poda efectivas para reducir significativamente el espacio de búsqueda.
* Una solución aproximada es aceptable si la solución exacta lleva demasiado tiempo para encontrar.
Si su problema es grande y la poda es ineficaz, es posible que deba considerar algoritmos alternativos o técnicas de aproximación.