Capítulo 4
BUSQUEDA INFORMADA
1
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
2
Repaso: busqueda en un árbol
• Una estrategia de búsqueda está
definida escogiendo el orden de
expansión de nodo pendientes
3
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*
4
Rumanía escalonada en km
5
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
6
Busqueda Voraz
7
Busqueda Voraz
8
Busqueda Voraz
9
Busqueda Voraz
10
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
11
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
12
Ejemplo: Busqueda del A*
13
Ejemplo: Busqueda del A*
14
Ejemplo: Busqueda del A*
15
Ejemplo: Busqueda del A*
16
Ejemplo: Busqueda del A*
17
Ejemplo: Busqueda del A*
18
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
19
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
20
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
21
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
22
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
23
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í
24
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) = ?
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) = ? 8
h2(S) = ? 3+1+2+2+2+3+3+2=18
26
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=12IDS = 3,644,035 nodos
A*(h1) = 227 nodos
A*(h2) = 73 nodos
• d=24 IDS = también muchos nodos
A*(h1) = 39,135 nodos
A*(h2) = 1,641 nodos
27
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
28
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
29
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
30
Ascenso de Montaña
31
Ascenso de Montaña
Problema: A merced de la condición inicial, puede
quedarse atorado en el máximo local
32
Ascenso de Montaña
Las 8 Reinas
• 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
33
Ascenso de Montaña
Las 8 Reinas
• Un mínimo local con h = 1
34
Forja Simulada
• Sacar el máximo local dejando algunos movimientos
"malos" pero gradualmente ir disminuyendo su
frecuencia
35
Forja Simulada
• 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.
36
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
37
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
38
Los algoritmos genéticos
39
Descargar

LOS ALGORITMOS INFORMADOS DE BUSQUEDA