1.4.3 Nociones de complejidad de la exploración exhaustiva y vuelta atrás
Los algoritmos de exploración exhaustiva tienden a ser ineficientes debido a su necesidad de recorrer todo el espacio de búsqueda para encontrar soluciones. Este problema se agrava al explorar ramas del árbol de decisiones que no conducirán a una solución. Por lo tanto, su eficiencia se ve comprometida, especialmente en problemas complejos.
En contraste, los algoritmos de backtracking mejoran el proceso al podar ramas que ya se ha determinado que no conducirán a soluciones. Cuando el algoritmo identifica que una rama no ofrece resultados, retrocede a un punto anterior en el árbol y continúa explorando otras alternativas. Esta técnica de poda reduce la cantidad de combinaciones que deben evaluarse.
La complejidad de estos enfoques se puede describir de la siguiente manera:
- Complejidad de la exploración exhaustiva: Dado que se requieren explorar todas las combinaciones posibles para llegar a una solución, la complejidad suele ser factorial, es decir, O(n!).
- Complejidad del backtracking: Gracias a la técnica de poda, la complejidad se considera exponencial, es decir, O(nn). Sin embargo, esta complejidad puede variar según factores como la cantidad de ramificaciones en el árbol, el tiempo de ejecución de la función de poda y el número de ramas que se han podado.
Conclusión
A lo largo de esta unidad, se ha evidenciado que los algoritmos son fundamentales para el desarrollo de sistemas computacionales. Existen diversas técnicas para abordar una amplia gama de problemas, y aunque algunos algoritmos, como los de ordenamiento por mezcla o búsqueda indexada, son más eficientes, hay problemas para los cuales no se han desarrollado algoritmos eficientes conocidos. En tales casos, se recurre a métodos como la exploración exhaustiva o el backtracking.
Además, hay otras técnicas que complementan la implementación de algoritmos, como la programación dinámica, algoritmos probabilísticos, heurísticas e inteligencia artificial. Estas herramientas son útiles para resolver problemas complejos de manera más efectiva, aunque requieren un tratamiento previo de la información. Es decir, la información debe estructurarse adecuadamente para facilitar su procesamiento.
Existen diferentes estructuras de datos que permiten organizar la información, tales como pilas, colas, listas, tablas hash, árboles y grafos. Estos elementos son conocidos como tipos abstractos de datos (TAD), y se explorarán en unidades temáticas futuras.