View
126
Download
4
Category
Preview:
Citation preview
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….
Recommended