7.2. Análisis de tiempos de ejecución.
El tiempo de ejecución depende de:
- Número de nodos recorridos: depende de la efectividad de la poda.
- Tiempo gastado en cada nodo: tiempo de hacer las estimaciones de coste y tiempo de manejo de la lista de nodos vivos.
En el peor caso, el tiempo es igual que el de un algoritmo con backtracking (ó peor si tenemos en cuenta el tiempo que requiere la LNV).
En el caso promedio se suelen obtener mejoras respecto al backtracking.
¿Cómo hacer que un algoritmo de ramificación y poda sea más eficiente?
- Hacer estimaciones de costo muy precisas: Se realiza una poda exhaustiva del árbol. Se recorren menos nodos pero se gasta mucho tiempo en realizar las estimaciones.
- Hacer estimaciones de costo poco precisas: Se gasta poco tiempo en cada nodo, pero el número de nodos puede ser muy elevado. No se hace mucha poda.
Se debe buscar un equilibrio entre la exactitud de las cotas y el tiempo de calcularlas.