calidad

Resolución de
problemas mediante
Búsqueda
CAPITULO 4
Búsqueda informada

28 de Marzo 2012

(c) Facundo Bromberg

1

Repaso (cont.)
 Agente

racional: aquel que hace lo correcto.
 Medida de rendimiento: determina el éxito
del agente, es decir, le permite hacer lo
correcto.

Un agente racional es aquel que,
Un agente racional es aquel que,
basado en su historial depercepciones,
basado en su historial de percepciones,
emprende aquella acción que maximiza
emprende aquella acción que maximiza
su medida de rendimiento.
su medida de rendimiento.
28 de Marzo 2012

(c) Facundo Bromberg

2

Agentes resolvedores de
problemas
 Los

agentes resolvedores de problemas son
una clase de agentes basados en objetivos.

 Tarea:

encontrar secuencia deacciones que
alcanza algún estado objetivo.

28 de Marzo 2012

(c) Facundo Bromberg

3



28 de Marzo 2012

(c) Facundo Bromberg

4

Formulación del problema (KE)


Estado inicial



Acciones



Función sucesor
Espacio de estados



Test objetivo



Costo de camino.

Solución: camino desde estado inicial al objetivo.
28 de Marzo 2012
(c) Facundo Bromberg5
Solución óptima: Tiene costo de camino mínimo.

28 de Marzo 2012

(c) Facundo Bromberg

6

Espacio de estados de
Vacaciones en Rumania
Estado
inicial
Función sucesor
desde En(Sibiu)

Estado objetivo

Una
Solución
28 de Marzo 2012

(c) Facundo Bromberg

7

Búsqueda


Nodo: 0

Tiempo

bd+1

bC*/e

bm

bl

bd

bd/2

Espacio

bd+1

bC*/e

bmbl

bd

bd/2

Optimo?

SI*

SI

NO

NO

SI

SI

si costos son
iguales

si costos son
iguales y usa
BPA

si costos son
iguales

28 de Marzo 2012

(c) Facundo Bromberg

Si b finita
Si usa BPA

17

Búsqueda informada

28 de Marzo 2012

(c) Facundo Bromberg

18

Búsqueda informada
Introducción
Métodos no informados
Generan sistematicamente nuevosestados
Los testean con el estado objetivo.

Terriblemente ineficiente:
Espacio de búsqueda es exponencial:
Aguja (objetivo) en un pajar (espacio de estados)

Como podemos mejorar? Heurísticas
Conociendo aquellos caminos mas probables de
llevarnos al objetivo.
En el mejor de los casos, tan solo expandiríamos aquellos
nodos que se encuentran en el camino solución.
28 de Marzo2012

(c) Facundo Bromberg

19

Función heuristica h(n)
Del diccionario: “Una regla aproximada, una simplifación,
o estimación justificada que reduce o limita la búsqueda de
soluciones en dominios dificiles o poco comprendidos”.
h(n) = estima costo del camino mas corto desde el nodo n
hasta el objetivo
Si n es el objetivo, entonces h(n) = 0

28 de Marzo 2012

(c) Facundo Bromberg20

Algoritmo de búsqueda en
arboles.

uncion BUSQUEDA-ARBOLES(problema,frontera) return solución o fallo
frontera ←INSERTA(HACER-NODO(ESTADO-INICIAL[problema],frontera)

op

if VACIA?(frontera) then returnfallo
nodo ← BORRAR-PRIMERO(frontera)
if TEST-OBJETIVO[problema] aplicado a ESTADO[nodo] es cierto
then return SOLUCION(nodo)
frontera← INSERTAR-TODOS(EXPANDIR(nodo, problema),frontera)
end loop

Recordemos: las estrategias se definen seleccionando el orden de expansión.
28 de Marzo 2012

(c) Facundo Bromberg

21

Búsqueda primero el mejor
Orden de expansión de los nodos n en la frontera es
determinado por una función de evaluación f(n).
f(n) estima la distancia estado-inicial al objetivo,
pasando por n.
Elige nodo que aparentemente es el mejor.Implementación:
frontera = cola de prioridad determinada por f(n).

28 de Marzo 2012

(c) Facundo Bromberg

22

Comparación algoritmos de
búsqueda
Algoritmo

Estrategia
(orden de expansión)

A ciegas

Búsqueda primero en anchura

FIFO

Búsqueda primero en profundidad

LIFO

Búsqueda de costo uniforme

g(n)

Informada

Búsqueda voraz

f(n) = h(n)

Búsqueda A*...