TALLER PROFUNDIDAD - AMPLITUD ITERATIVA

1. Para el grafo usted deberá llegar de A a H aplicando los algoritmos:

A. Interactive Debending (I D) Búsqueda profundización iterativa.
B. Amplitud iterativa.
2. Explicar:
A. El pseudocodigo de los algoritmos anteriores.
B. Su complejidad exponencial y temporal (mejor caso, peor caso, caso medio).
C. ¿Es Completo? Justifique su respuesta.
D. ¿Es Optimo? Justifique su respuesta.

SOLUCIÓN:

1.El problema con exigir un límite de profundidad, está precisamente en escoger un límite adecuado. Profundidad iterativa va aumentando gradualmente la profundidad hasta encontrar una meta. Es óptimo y completo.

PRUEBA DE ESCRITORIO.

AMPLITUD ITERATIVA:

PSEUDOCODIGOS:

Búsqueda en profundidad iterativa (límite: entero)

  prof=1; Est_abiertos.inicializar()

  Mientras no es_final?(Actual) y prof<limite hacer

    Est_abiertos.insertar(Estado inicial)

    Actual= Est_abiertos.primero()

    Mientras no es_final?(Actual) y no Est_abiertos.vacía?() hacer

       Est_abiertos.borrar_primero()

       Est_cerrados.insertar(Actual)

       si profundidad(Actual) ≤ prof entonces

        Hijos= generar_sucesores(Actual)

        Hijos= tratar_repetidos(Hijos, Est_cerrados, Est_abiertos)

       fsi

       Est_abiertos.insertar(Hijos)

       Actual= Est_abiertos.primero()

    fMientras

   prof=prof+1

   Est_abiertos.inicializar()

   fMientras 

COMPLEJIDAD ESPACIAL Y TEMPORAL

PROFUNDIDAD:

Mejor caso:  O((b-1)*d)

Peor caso:  O(b*d)

Caso medio: O(b*d)/2

AMPLITUD:

Complejidad temporal: O(b^d)

Complejidad espacial:

     Mejor caso:O((b-1)*d)

     Peor caso: O(b*d)

     Caso medio:O(b*d)/2

OPTIMO? COMPLEJO?

PROFUNDIDAD: Es completo porque se puede encontrar la  solución del problema sin perder nodos, pero el coste de las iteraciones anteriores es pequeño comparado con la iteración que encuentra la solución. Es Óptimo porque al expandir los nodos garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna. y mejoras la capacidad de memoria.

AMPLITUD: El algoritmo siempre encontrara la solución de existir. Se podría decir que esta técnica se puede utilizar con problemas que tienen más de una solución y es optimo siempre y cuando el coste sea 1 o menor.