1 ESTRATEGIAS DE BUSQUEDA A CIEGAS

2 Algoritmos de búsqueda ciega (desinformada) mindless search Búsqueda en amplitud Búsqueda en profundidad Profundización iterativa Búsqueda con costo uniforme

3 Búsqueda Primero en AmplitudSe basa en desarrollar completamente cada nivel del Arbol antes de pasar a desarrollar la siguiente Depth 0 Depth 1 Depth 2

4 Búsqueda Primero en AmplitudDepth 0 Depth 1 Depth 2

5 Búsqueda Primero en AmplitudDepth 0 Depth 1 Depth 2

6 Búsqueda Primero en AmplitudExpandir el más chato - menos profundo - “nodo sin expandir” Arad Arad Zerind Sibiu Timisoara

7 Búsqueda Primero en AmplitudArad Zerind Sibiu Timisoara Arad Oradea

8 Búsqueda Primero en AmplitudArad Zerind Sibiu Timisoara Rimnicu Vilcea Arad Oradea Arad Oradea Fagaras

9 Búsqueda Primero en AmplitudArad Sibiu Zerind Timisoara Rimnicu Vilcea Arad Oradea Fagaras Arad Oradea Arad Lugoi

10 Búsqueda Primero en Amplitud1 2 3 4 5 6 7 8 9 10 11 12 13 14 goal

11 Espacio de búsqueda “total” (BPA con supresor de repetidos)Juego de 8 fichas

12 Algoritmos de búsqueda básica(desinformada) mindless searchBúsqueda en amplitud  Búsqueda en profundidad Profundización iterativa Búsqueda con costo uniforme

13 Búsqueda Primero en ProfundidadSe basa en elegir un camino en el árbol y seguirlo hasta el final. Si no se encuentra la solución se retrocede (“backtraking”) y se prueba por otro camino.

14 Búsqueda Primero en Profundidad

15 Búsqueda Primero en Profundidad

16 Búsqueda Primero en Profundidad

17 Búsqueda Primero en Profundidad

18 Búsqueda Primero en Profundidad

19 Búsqueda Primero en Profundidad

20 Búsqueda Primero en Profundidad

21 Búsqueda Primero en Profundidad

22 Búsqueda Primero en ProfundidadExpandir el”nodo sin expandir” más profundo QueuingFN = Insertar sucesor en tope de cola Arad Zerind Sibiu Timisoara Arad Oradea

23 Búsqueda Primero en ProfundidadArad Zerind Sibiu Timisoara Arad Oradea BPP puede incurrir en excursiones cíclicas infinitas. Necesita un espacio de búsqueda que sea * finito * no-cíclico, o bien * supresor de repetidos. Zerind Sibiu Timisoara

24 Algoritmos de búsqueda básica(desinformada) mindless searchBúsqueda en amplitud Búsqueda en profundidad  Profundización iterativa Búsqueda con costo uniforme

25 Ventajas de la búsqueda en extensión• No se “pierde” explorando caminos infructuosos que consumen mucho tiempo sin llegar a una solución o de los que no se vuelve nunca (bucles en profundidad). • Si hay una solución la encuentra. Es más, si hay varias encuentra la óptima. Ventajas de la búsqueda en profundidad • Requiere mucha menos memoria (sólo hay que guardar el camino actual). • Puede encontrar una solución sin examinar mucho el árbol, sobre todo si hay varios caminos a la solución.

26 Profundización IterativaBúsqueda Primero en Profundidad con límite en profundidad l si no se encuentra la solución. Nodos a profundidad l sin sucesores

27 Profundización Iterativa

28 Profundización Iterativa

29 Profundización Iterativa

30 Profundización Iterativa

31 Profundización Iteratival = 0 Arad l = 1 etapas 1 y 2 Arad Zerind Sibiu Timisoara

32 Profundización IterativaArad Zerind Sibiu Timisoara l = 2 etapas 1, 2 y 3 Arad Oradea

33 Profundización Iteratival = 2 etapa 5 Arad Sibiu Zerind Timisoara Rimnicu Vilcea Arad Oradea Arad Oradea Fagaras Arad Lugoi

34 Algoritmos de búsqueda básica(desinformada) mindless searchBúsqueda en amplitud Búsqueda en profundidad Profundización iterativa Búsqueda con costo uniforme <=

35 Búsqueda con costo uniforme

36 Búsqueda con costo uniformeSe basa en desarrollar el nodo con menor coste. Arad 75 140 118 Zerind Sibiu Timisoara <== Zerid, Timisoara, Sibiu <==

37 Búsqueda con costo uniformeArad 75 140 118 Zerind Sibiu Timisoara 75+75 71+75 Arad Oradea <== Timisoara, Sibiu, Oradea, Arad <==

38 Búsqueda con costo uniformeArad 75 140 118 Zerind Sibiu Timisoara 75+75 71+75 Arad Oradea Arad Lugoi <== Sibiu, Oradea, Arad, Lugoi, Arad <==

39

40 Propiedades de búsqueda con costo uniformeCompleta? Sí, mientras b sea finita (similar a búsqueda Primero en Amplitud) Complejidad temporal? Numero de nodos con g(n) £ costo de la solución óptima Complejidad espacial? Optima? Sí, mientras el costo de ruta no disminuya siguiendo cualquier ruta o sea que g(Successor(n)) ³ g(n), para todo n Qué sucede con operadores con costo negativo?

41 Búsqueda bidireccionalEstadoFinal Estado inicial

42 No vale para todos los problemas: Los operadores deben ser reversiblesNo vale para todos los problemas: Los operadores deben ser reversibles. • Problema si hay varias soluciones. • Debe haber comprobación eficiente de encuentro.

43 PREGUNTAS….