busqueda informada
DESCRIPTION
BUSQUEDA INFORMADA. Capítulo 4. Bosquejo. El mejor primero B úsque da voraz B úsqueda A * A lgoritmos de mejora iterada Ascenso de Montaña Forja simulada La búsqueda local de cambio Los algoritmos genéticos. Repaso: busqueda en un árbol. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/1.jpg)
1
BUSQUEDA INFORMADA
Capítulo 4
![Page 2: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/2.jpg)
2
Bosquejo El mejor primero Búsqueda voraz Búsqueda A*
Algoritmos de mejora iterada Ascenso de Montaña Forja simulada La búsqueda local de cambio Los algoritmos genéticos
![Page 3: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/3.jpg)
3
Repaso: busqueda en un árbol
• Una estrategia de búsqueda está definida escogiendo el orden de expansión de nodo pendientes
![Page 4: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/4.jpg)
4
El mejor primero
• Una idea: Use una función de evaluación f (n) para cada nodo
- La estimación por “conveniencia"- Expanda el nodo deseado
• Implementación: Ordene los nodos de la orilla en forma
decreciente por conveniencia
• Casos especiales:- La búsqueda en menor tiempo- La búsqueda A*
![Page 5: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/5.jpg)
5
Rumanía escalonada en km
![Page 6: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/6.jpg)
6
Búsqueda Voraz
• La función de evaluación f (n) = h (n) (heurística)= la estimación que sea igual a n para que llegue al final
• e.g., hSLD(n) = La distancia de línea recta hSLD (n) de n para Bucarest
• La búsqueda voraz, expande el nodo más prometedor
![Page 7: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/7.jpg)
7
Busqueda Voraz
![Page 8: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/8.jpg)
8
Busqueda Voraz
![Page 9: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/9.jpg)
9
Busqueda Voraz
![Page 10: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/10.jpg)
10
Busqueda Voraz
![Page 11: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/11.jpg)
11
Propiedades: busqueda voraz
• ¿Completa? No – puede quedarse atorada en ciclos, v.g., Iasi Neamt Iasi Neamt
• ¿Tiempo? O(bm), una buena heurística puede mejorar mucho
• ¿Espacio? O(bm)- todos los nodos están dentro de la memoria
• ¿Óptimo? No
![Page 12: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/12.jpg)
12
Busqueda A*
• Idea: Evite caminos dispersos y costosos• f = g (n) + h (n)• g (n) = costo para llegar a n• h (n) = costo estimado de n a la meta• f (n) = costo total estimado del camino a
través de n hasta la meta
![Page 13: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/13.jpg)
13
Ejemplo: Busqueda del A*
![Page 14: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/14.jpg)
14
Ejemplo: Busqueda del A*
![Page 15: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/15.jpg)
15
Ejemplo: Busqueda del A*
![Page 16: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/16.jpg)
16
Ejemplo: Busqueda del A*
![Page 17: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/17.jpg)
17
Ejemplo: Busqueda del A*
![Page 18: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/18.jpg)
18
Ejemplo: Busqueda del A*
![Page 19: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/19.jpg)
19
Heurísticas admisibles
• Una heurística h(n), es admisible si para cada nodo n
h(n) ≤ h*(n), donde h*(n) es el costo verdadero para llegar a la meta desde n
• Una heurística admisible es optimista• Ejemplo: hSLD(n) (nunca se pasa de la distancia
real del camino)• Teorema: Si h(n) es admisible, entonces A*
usando una ARBOL DE BUSQUEDA es óptima
![Page 20: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/20.jpg)
20
Optimalidad de A*Suponga que alguna meta sub-óptima G2 ha sido generada y está en la orilla. Sea n un nodo no expandido en un camino mas corto a una meta óptima G1.
f(G2) = g(G2) dado que h(G2) = 0
g(G2) > g(G1) dado que G2 es sub-óptimo
f(n) dado que h es admisible
como f(G2) > f(n), A* nunca seleccionará G2 para expansión
![Page 21: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/21.jpg)
21
Optimalidad de A*• Supongo que alguna meta sub-óptima G2 ha sido generada y está en el
margen. Dejando ser n la un nodo no expandido en el margen algo semejante que la n está en un camino más pequeño para una G es óptima para llegar al final.
•f(G2) > f(G) de arriba
•h(n) ≤ h^*(n) desde que la h es admisible•g(n) + h(n) ≤ g(n) + h*(n) •f(n) ≤ f(G)
Por lo tanto f(G2) > f(n), y UN * nunca seleccionara a G2 para la espanción
•
![Page 22: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/22.jpg)
22
Heurísticas consistentes
• Una heurística es consistente si para cada nodo n, cada n´ sucesor de n generado por cualquier acción
h(n) ≤ c(n,a,n') + h(n')
• Si la h es consistente, entonces lo hemos hecho
f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n)
• i.e., F (n) decrece poco a lo largo de cualquier camino.• Teorema: Si h (n) es coherente, entonces A* usando un
Grafo de búsqueda es óptimo
![Page 23: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/23.jpg)
23
Optimalidad de A*• A* expande nodos en orden creciente de f
• Gradualmente añade “el contorno de f ” nodos• El contorno tiene todos los nodos con f=f i donde fi < fi+1
![Page 24: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/24.jpg)
24
Propiedades de A*
• ¿Completa? Sí (a menos que haya infinitamente muchos nodos con f(G))
• ¿Tiempo? Exponencial• ¿Espacio? Guarda todos los nodos en
memoria• ¿Óptimo? Sí
![Page 25: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/25.jpg)
25
Heuristicas admisibles
Para el rompecabezas 8• h1(n) = número de tejas que se colocaron mal• h2(n) = sumar las distancias Manhattan• (i.e., No. de cuadrados de posición deseada de cada
teja)
h1(S) = ?
h2(S) = ?
![Page 26: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/26.jpg)
26
Para el rompecabezas 8• h1(n) = número de tejas que se colocaron mal• h2(n) = sumar las distancias Manhattan• (i.e., No. de cuadrados de posición deseada de cada
teja)
h1(S) = ? 8
h2(S) = ? 3+1+2+2+2+3+3+2=18
Heuristicas admisibles
![Page 27: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/27.jpg)
27
Dominio
• Si h2(n) ≥ h1(n) para toda n (ambos son admisibles) h2 domina h1
• h2 es mejor para la búsqueda
• La búsqueda típica cuesta (el número común de nodos expandidos):
• d=12 IDS = 3,644,035 nodosA*(h1) = 227 nodos A*(h2) = 73 nodos
• d=24 IDS = también muchos nodosA*(h1) = 39,135 nodos A*(h2) = 1,641 nodos
![Page 28: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/28.jpg)
28
Problemas Relajados
• Un problema con menos restricciones se considera un problema relajado
• El costo de una solución óptima para un problema relajado proporciona una heurística admisible para el problema original
• Si las reglas de los rompecabezas 8 están relajados a fin de que una teja puede moverse donde quiera, h1 (n) da la solución más corta
• Si las reglas están relajadas a fin de que una teja puede mudarse a cualquier cuadrado adyacente, entonces h2 (n) da la solución más corta
![Page 29: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/29.jpg)
29
Algoritmos de mejora iterada
• En muchos problemas de optimización, el camino a la meta es irrelevante; La meta misma es la solución
• Espacio de estado = conjunto de configuraciones "completas“
• Encontrar configuración óptima – TSP (Traveling Salesman Problem)
• Encontrar configuración que satisfaga restricciones - n-reinas
• En tales casos, podemos usar algoritmos de mejora iterada
• Conservar un solo estado "actual“ y tratar de mejorarlo
![Page 30: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/30.jpg)
30
Ejemplo n-reinas
• Colocar n reinas en un tablero de n x n sin que hayan dos reinas en la misma fila, columna, o diagonal
![Page 31: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/31.jpg)
31
Ascenso de Montaña
![Page 32: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/32.jpg)
32
Problema: A merced de la condición inicial, puede quedarse atorado en el máximo local
Ascenso de Montaña
![Page 33: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/33.jpg)
33
• h= el número de la h de pares de reinas que atacan a cada quien, ya sea directamente o indirectamente
• h = 17 para la condición anteriormente
Ascenso de MontañaLas 8 Reinas
![Page 34: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/34.jpg)
34
• Un mínimo local con h = 1
Ascenso de MontañaLas 8 Reinas
![Page 35: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/35.jpg)
35
Forja Simulada• Sacar el máximo local dejando algunos movimientos
"malos" pero gradualmente ir disminuyendo su frecuencia
![Page 36: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/36.jpg)
36
• Uno puede probar: Si la T disminuye lo suficientemente lenta, la búsqueda encontrará un óptimo (de todo) con probabilidad acercándose a 1
• Ampliamente usado en trazado VLSI, programando, etc.
Forja Simulada
![Page 37: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/37.jpg)
37
Los algoritmos genéticos
• Una individuo es generado combinando los cromosomas de los padres
• Comenzar con k individuos generados al azar (la población)
• Un individuo es representado como una cuerda sobre un alfabeto finito (a menudo una cuerda de 0s y 1s)
• La función de evaluación (la función de adaptabilidad). Los valores superiores para las mejores condiciones.
• Produzca la siguiente generación de condiciones por la selección, cruza, y mutación
![Page 38: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/38.jpg)
38
Los algoritmos genéticos
• función de adaptabilidad: El número de pares atacantes de reinas (min = 0, max = 8 × 7/2 = 28)
• 24/(24+23+20+11) = 31%
• 23/(24+23+20+11) = 29% etc
![Page 39: BUSQUEDA INFORMADA](https://reader036.vdocumento.com/reader036/viewer/2022062301/56815328550346895dc14d55/html5/thumbnails/39.jpg)
39
Los algoritmos genéticos