Busqueda por profundidad iterativa

Inteigencia Artificial

1. B úsqueda por profundidad iterativa Daniela Marmolejo Carreón Liliana González Cornejo Alexander Morales Urrea Israel Calderón de la cruz Edgar Pérez Torres José Luis Pérez Ávila //Equipo 5/

2. Definición

3. El nombre profundización iterativa hace referencia a que se realiza iteraciones de búsquedas cada vez mas profunda. Esto se hace aumentando gradualmente el limite realizando la búsqueda en sucesivos niveles. Definición //Equipo 5/

4. Funcionamiento

5. Funcionamiento //Equipo 5/ Se define una profundidad predefinida Se desarrolla el árbol realizando 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.

6. Funcionamiento Búsqueda iterada en profundidad l =0 //Equipo 5/

7. Funcionamiento //Equipo 5/ Búsqueda iterada en profundidad l =1

8. Funcionamiento Búsqueda iterada en profundidad l =2 //Equipo 5/

9. Funcionamiento Búsqueda iterada en profundidad l =3 //Equipo 5/

10. Ventajas y Desventajas

11. Ventajas y desventajas //Equipo 5/ El requerimiento limitado de memoria. La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo 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.

12. Recorrido completo

13. Recorrido completo 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

14. 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.

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

16. Estrategia

17. Estrategia Criterio Completo Si Tiempo (d+1)b0 + d b1 + (d-1)b2 + … + bd = O( bd ) Espacio O( bd ) Optimo Si, si costo de paso =1 //Equipo 5/ 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 búsqueda d: Profundidad de solución de mínimo costo m: Profundidad máxima del espacio de estados (puede ser ∞)

18. Donde se aplican

19. Aplicaciones //Equipo 5/ Se dice que este método es funcional en escenarios donde existen profundidad media y alta

20. Comparación //Equipo 5/

21. Comparación //Equipo 5/ Si queremos llegar de Salina Cruz a Ixtepec , y para simplificar el problema, suponemos que no hay pérdida de tiempo entre trasbordo y trasbordo.

22. Comparación //Equipo 5/ Búsqueda por profundidad Búsqueda iterativa por profundidad

23. Comparación

24. Gracias : )