Completitud: El algoritmo siempre encontrara la solución de existir.
Complejidad temporal: La misma que la búsqueda en anchura. El regenerar el árbol en cada iteración solo añade un factor constante a la función de O(b^d).
Dónde: o b, factor de ramificación: número máximo de sucesores (hijos) de cualquier nodo. O d, profundidad del nodo objetivo menos profundo.
Complejidad espacial: Igual que en la búsqueda en profundidad O(bd).
Optimalizada: La solución es óptima si el coste de paso es 1.
Igual que en el caso del algoritmo en profundidad, el tratar repetidos acaba con todas las ventajas espaciales del algoritmo, por lo que es aconsejable no hacerlo. Como máximo se puede utilizar la estructura de nodos abiertos para detectar bucles en el camino actual
Complejidad Profundidad Iterativa
La complejidad en espacio de la BP es O(bd) O(bd), donde b b es el factor de ramificación y d d es la profundidad de la solución más superficial. Dado que BP visita los estados múltiples veces, puede parecer extremadamente costoso, pero no lo es, dado que la mayor parte de los nodos se encuentran en el nivel más profundo del árbol, por lo tanto no tiene mucha importancia que se visiten los niveles superiores varias veces.
Prueba de escritorio (ID,IB).
Prueba de escritorio ID
Prueba de escritorio IB
No hay comentarios:
Publicar un comentario