1

BUSQUEDA

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 Amplitud

Depth 0

Depth 1

Depth 2

Se basa en desarrollar completamente cada nivel del Se basa en desarrollar completamente cada nivel del Arbol antes de pasar a desarrollar la siguienteArbol antes de pasar a desarrollar la siguiente

4

Búsqueda Primero en Amplitud

Depth 0

Depth 1

Depth 2

5

Búsqueda Primero en Amplitud

Depth 0

Depth 1

Depth 2

6

Búsqueda Primero en Amplitud

• Expandir el más chato - menos profundo - “nodo sin expandir”

Arad

Arad

Sibiu TimisoaraZerind

7

Búsqueda Primero en AmplitudArad

Sibiu TimisoaraZerind

OradeaArad

8

Búsqueda Primero en Amplitud

Arad

Sibiu TimisoaraZerind

Oradea FagarasArad RimnicuVilcea

OradeaArad

9

Búsqueda Primero en Amplitud

Arad

Sibiu TimisoaraZerind

Oradea FagarasArad RimnicuVilcea

OradeaArad LugoiArad

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 search• Búsqueda en amplitud Búsqueda en profundidad • Profundización iterativa

• Búsqueda con costo uniforme

13

Búsqueda Primero en Profundidad

Se basa en elegir un camino en el árbol y seguirlo hasta el final.Si no se encuentra la solución se retrocede (“backtraking”) y seprueba 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 Profundidad• Expandir el”nodo sin expandir” más profundo

– QueuingFN = Insertar sucesor en tope de cola

Arad

Sibiu TimisoaraZerind

OradeaArad

23

Búsqueda Primero en Profundidad

Arad

Sibiu TimisoaraZerind

SibiuZerind

OradeaArad

Timisoara

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.

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.

24

Algoritmos de búsqueda básica(desinformada)

mindless search• Bú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 Iterativa• Bú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 IterativaArad

Arad

Sibiu TimisoaraZerind

l = 0l = 0

l = 1etapas 1 y 2

l = 1etapas 1 y 2

32

Profundización IterativaArad

Sibiu TimisoaraZerind

OradeaArad l = 2etapas 1, 2 y 3

l = 2etapas 1, 2 y 3

33

Profundización Iterativa

Arad

Sibiu TimisoaraZerind

Oradea FagarasAradRimnicuVilcea

OradeaArad LugoiArad

l = 2etapa 5

l = 2etapa 5

34

Algoritmos de búsqueda básica(desinformada)

mindless search• Bú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 uniforme• Se basa en desarrollar el nodo con

menor coste.

Arad

Sibiu TimisoaraZerind

75 140 118

<== Zerid, Timisoara, Sibiu <==<== Zerid, Timisoara, Sibiu <==

37

Búsqueda con costo uniforme

Arad

Sibiu TimisoaraZerind

75 140 118

OradeaArad

75+75 71+75

<== Timisoara, Sibiu, Oradea, Arad <==<== Timisoara, Sibiu, Oradea, Arad <==

38

Búsqueda con costo uniforme

Arad

Sibiu TimisoaraZerind

75 140 118

OradeaArad

75+75 71+75

LugoiArad

118+118 111+118

<== Sibiu, Oradea, Arad, Lugoi, Arad <==<== Sibiu, Oradea, Arad, Lugoi, Arad <==

39

40

Propiedades de búsqueda con costo uniforme

• Completa?

– 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?

– Numero de nodos con g(n) costo de la solución óptima

• 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 bidireccional

EstadoFinalEstado inicial

42

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

43

PREGUNTAS….