presentacion iterativa

B ú s q u e d a p o r
p ro f u n d i d a d
i t e r a t i v a

Definición

Definición

El nombre profundización iterativa
hace
referencia a que se realiza
iteraciones de
búsquedas cada vez masprofunda.
Esto se hace aumentando
gradualmente el limite realizando la
búsqueda en sucesivos niveles.

Funcionamiento

Funcionamiento
 Se define una profundidad predefinida
 Se desarrolla el árbolrealizando una búsqueda
en profundidad hasta el límite definido en el
punto anterior
 Si encuentra la solución termina
 En caso contrario, se establece un nuevo límite y
volvemos al segundo paso.Funcionamiento
Búsqueda iterada en profundidad l =0

Funcionamiento
Búsqueda iterada en
profundidad l =1

Funcionamiento
Búsqueda iterada en profundidad l
=2

Funcionamiento
Búsqueda iterada enprofundidad l =3

Ventajas y Desventajas

Ventajas y desventajas
 El requerimiento limitado de memoria.
 La uniformidad al expandir los nodos, que
garantiza encontrar la mejor solución de un
problema decosto uniforme antes que ninguna.
 El inconveniente puede ser la redundancia de
que se vuelve a inspeccionar cada nodo ya
comprobado con cada nueva iteración.

Recorrido completo

Recorridocompleto
•0: A
•1: A (repetido), B, C, E
•2: A, B, D, F, C, G, E, F
•3: A, B, D, F, E, C, G, E, F, B

Recorrido completo
Para este grafo, cuanta más profundidad se añade,
los ciclos "ABFE" y "AEFB"simplemente se alargan
antes de que el algoritmo abandone e intente otra
rama.

Uso de memoria
Por lo tanto solo guarda la ruta donde se encuentra
actualmente el nodo a evaluar.

Pseudocodigo

EstrategiaEstrategia
Las estrategias se evalúan de acuerdo a:





Completitud: ¿Siempre encuentra una solución si alguna existe?
Complejidad temporal: Número de nodos generados
Complejidad espacial:Número máximo de nodos en memoria
Optimalidad: ¿Siempre encuentra una solución de mínimo costo?

Complejidad de tiempo y espacio se mide en termino de
 b: Máximo factor del número de ramas del árbol de...