Download Fundamentos de inteligencia artificial (búsquedas).

Fundamentos de
Inteligencia Artificial
Búsqueda
Coordinación de Ciencias Computacionales
Instituto Nacional de Astrofísica, Óptica y Electrónica
Manuel Montes ([email protected]; 8218)
Luis Villaseñor ([email protected]; 8306)
Objetivos de la sección
• Aprender cómo hallar trayectorias en redes,
resolviendo así problemas de búsqueda.
• Presentar los métodos más populares de
búsqueda.
• Aprender a evaluar los procedimientos de
búsqueda
– Su eficiencia, su facilidad de implementación, su
pertinencia para cierto tipo de problemas.
Métodos básicos de búsqueda
A tientas
Una ruta
Heuristicos
Búsqueda
Profundidad primero
Amplitud primero
Ascenso de colina
Búsqueda en haz
Primero el mejor
Ruta optima
Museo británico
Ramificación y cota
Programación dinámica
A*
Juegos
Minimax
Poda Alfa-beta
Continuación heurística
Profundidad progresiva
Redes y búsqueda
4
4
a
b
c
3
5
5
s
4
d
3
2
4
e
g
f
• Encontrar una trayectoria del punto S al punto G
involucra dos costos:
– El costo del cálculo para encontrar la trayectoria
– El costo del viaje cuando se sigue la trayectoria
Árbol de búsqueda
• Es una representación que considera todas las
trayectorias posibles en la red:
– Los nodos representan trayectorias, y las ramas
conectan trayectorias a extensiones de trayectoria de
un solo paso.
• Idea es construir al vuelo este árbol, siguiendo
una estrategia de búsqueda.
• El número total de trayectorias de un árbol con
factor de ramificación b y profundidad d es bd.
Árbol de búsqueda (cont.)
s
a
d
b
c
e
d
d
a
e
b
f
b
f
g
c
g
d
Trayectoria s-d-a-b-e-f-g
e
b
e
f
g
a
f
c
g
Búsqueda en profundidad primero
• Para llevar a cabo una búsqueda en profundidad,
1. Inserte en una pila el elemento raíz (nodo de partida)
2. Hasta que el elemento tope sea el nodo meta, o se
vacié la pila
1. Si nodo tope tiene hijos, insertar el hijo siguiente aun no
visitado, según ordenamiento.
2. Si no, entonces eliminar nodo tope.
3. Si el nodo meta se alcanza, mencione éxito, de lo
contrario, notifique el fracaso.
Árbol generado
s
1
a
d
2
b
3
d
a
e
b
e
4
c
5
e
b
f
6
d
f
b
f
c
g
d
e
7
g
f
g
a
c
g
Búsqueda en amplitud primero
• Para llevar a cabo una búsqueda en amplitud,
1. Inserte en una cola el elemento raíz (nodo de partida)
2. Hasta que el elemento frontal sea el nodo meta, o se
vacié la cola
1.Si nodo frontal tiene hijos, insertar todos sus hijos al final de la
cola.
2.Eliminar nodo frontal.
3. Si el nodo meta se alcanza, mencione éxito, de lo
contrario, notifique el fracaso.
Árbol generado
s
1
2
a
d
3
4
b
d
7
8
c
13
e
10
11
b
e
14 15
d
a
9
e
6
5
16
f
b
f
g
c
g
17
d
12
b
18
19
e
a
f
g
f
20
c
21
g
Comparación de procedimientos
• ¿cual de los dos procedimientos es mejor?
• ¿son ambos completos?
– ¿garantizan encontrar una solución, si es que existe?
• ¿son ambos óptimos?
– ¿se encontrara la mejor solución en caso de existir
varias?
• ¿y que pasa con su complejidad temporal y
espacial?
Problema de los jarrones de agua
• Se tienen dos jarrones, uno de 4 y otro de 3 litros.
Ninguno tiene marcas de medidas sobre él.
También se tiene una toma de agua que puede
usarse para llenar los jarrones.
• ¿cómo podemos obtener exactamente 2 litros en el jarrón
de 3?
• ¿qué tenemos que hacer para resolver este problema
automáticamente?
• ¿se debe representar el espacio de estados en su
totalidad? ¿hay alguna manera de representar en forma
resumida todos los posibles estados?
Una posible solución
…
…
…
…
Tarea 7:
Dibujar árbol de búsqueda
resultante al aplicar las
búsquedas en profundidad
y en anchura.
Jueves 18 de sept
Reglas de producción
• Los estados se representan como (X,Y), donde
X = 0,1,2,3,4 y Y = 0,1,2,3.
1. (X,Y|X<4)  (4,Y)
2. (X,Y|Y<3)  (X,3)
3. (X,Y|X>0)  (0,Y)
4. (X,Y|Y>0)  (X,0)
5. (X,Y|X+Y>=4 Y>0)  (4,Y-(4-X))
6. (X,Y|X+Y>=3 X>0)  (X-(3-Y),3))
7. (X,Y|X+Y<=4 Y>0)  (X+Y,0))
8. (X,Y|X+Y<=3 X>0)  (0,X+Y)
Métodos Heurísticos
• La búsqueda se puede mejorar si existe una forma
de ordenar las posibilidades de modo que las más
prometedoras se exploren primero.
• Mayor conocimiento, menor tiempo de búsqueda
• Tres métodos muy conocidos:
– Ascenso de colina (-> profundidad primero),
– Búsqueda en Haz (-> anchura primero),
– Primero el mejor
Ascenso de colina
• Mediciones de calidad convierten la búsqueda en
profundidad en ascenso de colina.
• Se ordenan las posibilidades (estados hijo) usando
una medición heurística de la distancia que queda
por recorrer.
– Distancia en línea recta al estado objetivo.
• Mejor medición, mejor el ascenso de colina
Distancias entre ciudades
4
4
a
b
c
3
5
s
5
4
d
4
2
e
f
b
a
c
10.4
s
g
3
6.7
4
11
g
8.9
d
e
6.9
f
3
Árbol generado
s
10.4
8.9
a
d
6.9
10.4
b
d
a
e
3.0
6.7
c
e
d
b
e
f
b
f
g
c
g
d
b
e
f
g
a
f
c
g
Problemas del ascenso de colina
• En problemas orientados a ajuste de parámetros:
– Problema de la falta de colina
• Se encuentra un punto optimo, pero se trata de un máximo
local.
– Problema de la meseta
• La operación de mejoramiento local fracasa por completo.
Todas las pruebas de paso normal dejan intacta la medición de
calidad.
– Problema del borde
• Es como estar en el filo de una navaja, solamente puede
salirse del problema si se tiene un número muy grande de
direcciones para orientar los pasos.
Búsqueda en haz
• Parecida a la búsqueda en amplitud en cuanto a
que avanza de nivel en nivel.
• Sólo se mueve hacia abajo a través de los w
mejores nodos de cada nivel.
– Extiende varias trayectorias parciales y elimina el resto.
• El número de nodos se mantiene manejable aún
cuando la ramificación sea alta y la búsqueda sea
profunda.
Árbol generado
s
10.4
8.9
a
d
6.7
8.9
b
d
4.0
6.9
10.4
a
e
6.9
c
3.0
6.7
e
b
e
b
f
Callejón
sin salida
d
f
b
f
g
c
g
d
e
f
g
a
c
g
Búsqueda primero el mejor
• Extiende la mejor trayectoria parcial en cada punto.
– Considera todos los nodos abiertos hasta el momento.
• Ascenso de colina inspecciona la que parece la mejor
trayectoria hasta el final; la búsqueda primero el mejor
analiza varias trayectorias a la vez, siempre siguiendo
la mejor trayectoria parcial conocida al momento.
• Generalmente la búsqueda primero el mejor encuentra
trayectorias más cortas a los estados meta.
Árbol generado
s
10.4
8.9
a
d
6.9
10.4
b
d
a
e
3.0
6.7
c
e
d
b
e
f
b
f
g
c
g
d
b
e
f
g
a
f
c
g
¿cuál es el mejor método?
• Primero en profundidad es bueno cuando se sabe
– con seguridad – que el árbol no es muy
profundo.
• Primero en anchura, cuando el factor de
ramificación no es muy grande.
• Los métodos heurísticos son adecuados cuando
existe una medida natural de la distancia entre
cada estado y el estado meta.
Encontrando la mejor ruta
• Estos métodos consideran, a diferencia de los
anteriores, el peso de las ramas.
• Su objetivo no es únicamente encontrar una ruta, sino
encontrar la mejor (típicamente la más corta).
• Entre ellos se encuentran:
– El procedimiento del museo británico
– Ramificación y cota
– El algoritmo A*
Procedimiento británico
• ¿qué hacer para asegurar encontrar la ruta
óptima?
• Procedimiento de museo británico:
– Primero encontrar todas las rutas al objetivo
– Después seleccionar la mejor
• Puede usarse búsqueda en anchura o en
profundidad como estrategia de exploración.
– Terminar hasta recorrer el árbol completamente.
• ¿qué inconveniente le encuentran?
Árbol generado con DFS
s
1
14
a
d
8
2
b
d
3
5
e
d
f
7
g
12
f
11
c
b
18
d
e
23
17
13
g
25
22
b
10
b
e
16
e
6
21
a
9
4
c
15
a
19
f
20
g
f
26
24
c
g
Aplicabilidad
• No tiene problemas con árboles (muy) pequeños.
• En la mayoría de los casos no es aplicable.
– Por explosión exponencial
• Si tenemos un árbol (mediano) con niveles d = 10,
y un factor de ramificación b = 10.
– Los estados visitados son bd.
– 1010 = 10 billones de estados
Ramificación y cota
• Menos sacrificado para encontrar la ruta óptima.
• Idea básica es expandir en cada ocasión la ruta
parcial con el menor costo hasta el momento.
– Es decir, todos los nodos abiertos hasta el momento
entran en consideración.
• Similar a método “primero el mejor”, pero al revés.
– En lugar de seguir el trayecto que aparentemente tiene
la menor distancia hacia el objetivo, se sigue aquel que
hasta el momento es el más corto.
Algoritmo básico
• Formar una cola de trayectos parciales. Inicialmente
sólo tiene el elemento raíz.
• Hasta que la cola se vacié o se alcance el nodo
objetivo, determinar si el primer elemento alcanza el
nodo objetivo.
– Si alcanza el objetivo, salir.
– Si no, entonces;
• Borrar el nodo de la cola
• Agregar sus hijos a la cola
• Ordenar los nodos por costo acumulado
• Si el nodo objetivo fue encontrado mencionar éxito, de
lo contrario anunciar falla.
Árbol generado
s
3
1
2
a
d
4
7
5
b
4
6
d
8
9
3
a
e
8
7
11
c
e
e
12
6
10
13
b
11
b
f
10
9
d
f
b
g
c
15
f
g
14
d
e
f
g
a
c
g
13
Asegurar la ruta optima
5
3
b
b
1
1
s
s
2
a
3
g
2
a
3
g
• ¿cuál es la respuesta del método?
• ¿cómo podemos asegurar encontrar la ruta óptima?
• ¿cuándo debemos terminar el algoritmo?
– Cuando todas las rutas parciales tengan igual o mayor
peso que la trayectoria encontrada
Árbol completo
s
3
1
2
a
d
4
7
b
11
11
5
c
6
d
12
e
4
8
9
3
a
e
10
7
e
12
6
10
13
b
11
8
b
f
10
9
14
d
16
f
b
g
c
15
f
g
14
d
e
f
g
a
15
c
15
g
13
Estimación de la distancia restante
• Usar una estimación de la distancia restante a la meta
puede mejorar considerablemente el método.
• Si es buena estimación, entonces ella mas distancia
recorrida debe ser un buen cálculo de la longitud total
de la trayectoria:
– e(long trayectoria) = d(ya recorrida) + e(dist. restante)
• Si las conjeturas fueran correctas este método se
mantendría todo el tiempo en la ruta optima.
– Mejor estimación, mejor la búsqueda
Subestimaciones son apropiadas
• Las estimaciones no son perfectas; esto puede
traer serios problemas al método.
• ¿que sucederá con sobreestimaciones de la
distancia restante?
– Desvío permanente de la trayectoria óptima
– No existiría la certeza, hasta recorrer el árbol completo,
que la ruta encontrada es la optima.
• El método funciona adecuadamente con
subestimaciones de la distancia restante.
Árbol generado
con distancia directa entre ciudades
s
1
a
13.4
d
12.9
2
b
d
19.4
a
e
12.9
3
c
e
b
e
17.7
b
f
13
4
d
f
b
f
g
c
g
d
e
f
g
a
c
g
13
Trayectorias redundantes
• Ramificación y cota puede mejorarse eliminando
las trayectorias redundantes.
• Se relaciona con el principio de programación
dinámica.
– El mejor camino del punto de inicio a la meta, a través
de un lugar intermedio específico, es el mejor camino
hacia éste desde el lugar de inicio, seguido por el mejor
camino desde éste a la meta.
– No hay necesidad de buscar por otras trayectorias
hacia o desde el punto intermedio.
Árbol generado
s
3
1
2
a
d
4
4
7
3
b
d
8
9
a
e
6
7
11
5
c
e
e
12
10
13
b
11
b
f
10
6
14
d
16
f
b
g
c
15
f
g
14
d
e
f
g
a
15
c
15
g
13
Procedimiento A*
• Es una búsqueda de ramificación y cota con:
– Estimación de distancia restante
– Eliminación de trayectorias redundantes
• Si la estimación de la distancia restante es un
limite inferior de la distancia real, entonces A*
produce soluciones optimas.