Fundamentos deInteligencia Artificial

Búsqueda

Coordinación de Ciencias Computacionales

Instituto Nacional de Astrofísica, Óptica y Electrónica

Manuel Montes (mmontesg@inaoep.mx; 8218)Luis Villaseñor (villasen@inaoep.mx; 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

Búsqueda

Una ruta

Ruta optima

Juegos

Profundidad primero

Amplitud primero

Ascenso de colina

Búsqueda en haz

Primero el mejor

Museo británico

Ramificación y cota

Programación dinámica

A*

Minimax

Poda Alfa-beta

Continuación heurística

Profundidad progresiva

A tientas

Heuristicos

Redes y búsqueda

• 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

s

a

d e

b c

f

g

3

3

44

4 4

55

2

Á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

a eb d

c e b fbe

d f b f d e a c g

g c g f

gTrayectoria s-d-a-b-e-f-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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

1

2

3 4

56

7

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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

1 2

3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18 19 20 21

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úsquedaresultante al aplicar lasbúsquedas en profundidady en anchura.Jueves 18 de sept

Reglas de producción

• Los estados se representan como (X,Y), dondeX = 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

s

a

d e

b c

f

g

3

46.710.4

11

8.9

6.9

s

a

d e

b c

f

g

3

3

44

4 4

55

2

Árbol generado

s

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

8.910.4

10.4 6.9

3.06.7

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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

8.910.4

10.4 6.9

3.06.7

8.96.7

4.0 6.9

Callejónsin salida

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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

8.910.4

10.4 6.9

3.06.7

¿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

a

b

c e

d f

g

1

2

3 4

56

7

14

d

a ed

b fbe

b f d e a c g

c g f

g

11

9

8

10 12

13

15

16

17 18

19

20

21

22

23 24

25

26

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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

s

3 4

7 8 9 6

11 1011 12 10 13

13

1 2

4 5 6 3

87

9

15 14

Asegurar la ruta optima

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

s

b

a g23

51

s

b

a g23

31

Árbol completo

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

s

3 4

7 8 9 6

11 1011 12 10 13

13

1 2

4 5 6 3

87

9

15 1414 16 15 15

1011 12

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 generadocon distancia directa entre ciudades

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

s

13.4 12.9

19.4 12.9

13

13

1

2

3

4

17.7

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

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

s

3 4

7 8 9 6

11 1011 12 10 13

13

1 2

4 3

5

6

15 1414 16 15 15

7

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.