busquedaCanivales

Búsqueda
´
M OTIVACI ON

Y

T ERMINOLOG´I A

Cuando un agente inteligente actua
´ en el mundo se ve enfrentado a una
multiplicidad de alternativas, dentro de las cuales debe elegir.
´ que se realice dependera´ de las consecuencias de la eleccion.
´
La eleccion
Un aspecto esencial de los problemas que se enfrentan en Inteligencia Artificial es el de busqueda
de soluciones.
´
´ siembre relacionadoscon problemas de
Los problemas de busqueda
estan
´
´ Es necesario tener lenguajes de representacion
´ para exprerepresentacion.
sar lo que estamos buscando, como evoluciona el mundo, etc.

Jorge Baier Aranda, PUC

162

El Problema de los Misioneros y Caníbales
Usaremos el problema de los Misioneros y Can´ıbales para mostrar que´ elementos necesitaremos en un problema de busqueda.
´
En esteconocido problema hay tres can´ıbales, tres misioneros, un r´ıo y un bote. Los
can´ıbales, los misioneros y el bote se encuentran en una rivera del r´ıo. Los seis sujetos
´ a dos personas a la vez.
deben cruzar el r´ıo, pero el bote permite trasladar a lo mas
Se debe encontrar una secuencia de movimientos de personas en el bote que permita
´
cruzar a los seis individuos de manera segura. No se debepermitir que hayan mas
can´ıbales que misioneros en algun lado del r´ıo algun
´ momento.

´
Otros problema clasicos
de busqueda
son:
´
•
•
•
•
•

El coloreo de un mapa con cuatro colores.
´ de tareas (scheduling).
Planificacion
´ de rutas (vendedor viajero).
Problemas de planificacion
´ de robots.
Navegacion
´
Encontrar una estrategia para elegir la proxima
jugada en un juego con
adversarios.

JorgeBaier Aranda, PUC

163

Terminología
Para analizar los problemas de busqueda
usaremos la siguiente termino´
log´ıa:
´ del dominio
Estado: Dado un problema, un estado es una configuracion
asociado al problema que se esta´ analizando.
Por ejemplo, en el caso de los misioneros y can´ıbales, un estado esta´ dado
´ de los misioneros, de los can´ıbales y del bote.
por la posicion
´
¿como
es un estadopara el problema de coloreo de mapas?
El estado del problema lo representaremos con un functor
estado(Ci,Mi,Cd,Md,B)
donde los argumentos corresponden a:
Ci: Can´ıbales en la rivera izquierda.
Mi: Misioneros en la rivera izquierda.
Cd: Can´ıbales en la rivera derecha.
Md: Misioneros en la rivera derecha.
B: Indica en que´ lado del r´ıo se encuentra el bote. Los valores posibles
´ izq y der.
seranJorge Baier Aranda, PUC

164

´ estados
Estado Inicial: Dado un problema de busqueda,
existe uno o mas
´
que se toman como de partida.
En nuestro ejemplo, el estado inicial se representa por estado(3,3,0,0,izq).
´ de Estados Objetivos: Para un problema de busqueda
Descripcion
pue´
´ al problema de
den haber varios estados que representen una solucion
busqueda.
´
´ de un predicado o funEstosestados son descritos mediante la definicion
´ que, dado un estado, retorna verdadero si el estado es un estado
cion
objetivo y falso en otro caso.

Jorge Baier Aranda, PUC

165

´ final/1 para identificar estados
En el ejemplo, podemos utilizar la funcion
finales. As´ı:
final(estado(0,0,3,3,der)).

Establece que el estado final es uno en el cual todos los misioneros y
´ al lado derecho del r´ıo.can´ıbales estan
´ Optima: En muchos casos se necesita encontrar un estado ´optiSolucion
´ sea mejor, en
mo. Es decir, que sea un estado objetivo, pero que ademas
algun
´ sentido, que todas los estados objetivos alternativos. En este caso,
´
el problema de busqueda
corresponde a un problema de optimizacion.
´
´ que, dado un estado, entrega otro
Operador: Un operador es una funcion
estado. Por ejemplo, enel caso de los misioneros y de los can´ıbales, podemos definir el operador de cruce resulta/3 que recibe un estado y genera
un estado sucesor .

Jorge Baier Aranda, PUC

166

El predicado resulta(E,A,Er) cuando Er es el estado que se genera al
´ A sobre el estado E.
ejecutar la accion
Podemos escribir este predicado de la siguiente manera:
resulta(E1,cruzar(C,M),E2):posible(cruzar(C,M),E1),...