granjero

Sistemas Inteligentes

1. B´ squeda sin Informaci´n
u
o

Pr´ctica 1. 2012/13
a

Problema del granjero, el lobo, la oveja y la col

The farmer-wolf-goat-cabbage problem
Un granjero lleva un lobo, una oveja y una col al mercado. En el camino se encuentran con un
r´ y para cruzarlo hay una barca atada a la orilla. La barca tiene capacidad para el granjero y una
ıo
de sus mercanc´ Siel lobo y la oveja, o la oveja y la col, quedan en la misma orilla el granjero
ıas.
perder´ una de sus mercanc´ ¿En qu´ orden debe ir cruzando el granjero con las mercanc´ para
a
ıas.
e
ıas
que todas queden en la orilla opuesta?

C´mo representamos los Estados del problema
o
Existen dos orillas, A y B, y en una de ellas se encuentra el granjero y sus tres mercanc´
ıas.
Podemosrepresentar cada estado como una lista de cuatro elementos:
( granjero lobo oveja col )
de modo que cada elemento indica la orilla en la que se encuentra cada personaje. Por ejemplo:
( A B A B ) representa el estado en el que el granjero y la oveja est´n en la orilla A, y el lobo y
a
la col en la B.

Funciones para crear y consultar un estado
Para crear un nuevo estado usaremos la funci´ncrear-estado que recibir´ como argumentos
o
a
la orilla A/B en la que se encuentra cada personaje y devolver´ la lista con las 4 posiciones :
a
(defun crear-estado ( granjero lobo oveja col )
(list granjero lobo oveja col) )
Para conocer en qu´ orilla se encuentra cada personaje, defino 4 funciones que consultan la
e
lista que representa el estado:
(defun orilla-granjero (estado)
(nth 0 estado))
(defun orilla-lobo (estado)
(nth 1 estado) )
(defun orilla-oveja (estado)
(nth 2 estado) )
(defun orilla-col (estado)
(nth 3 estado) )
1

Sistemas Inteligentes

1. B´ squeda sin Informaci´n
u
o

Pr´ctica 1. 2012/13
a

Estados no permitidos
Existen estados del problema que no est´n permitidos, ya que por ejemplo, el lobo y la oveja
a
no pueden quedar solos en la mismaorilla, estado ( B A A B ) , y tampoco la oveja y la col.
Definimos entonces la funci´n valido que comprueba las dos condiciones que hacen que un estado
o
NO sea admitido, en cuyo caso devolver´ nil. Son las siguientes:
a
el granjero est´ en la orilla opuesta de la oveja y el lobo,
a
el granjero est´ en la orilla opuesta de la oveja y la col.
a
(defun valido (estado)
(cond (( and ( equal(orilla-lobo estado) (orilla-oveja estado) )
( not(equal (orilla-granjero estado) (orilla-lobo estado) ))) nil)
(( and ( equal (orilla-oveja estado) (orilla-col estado) )
( not(equal (orilla-granjero estado) (orilla-oveja estado) ))) nil)
(t estado) ) )

Funciones para definir los movimientos: Operadores
Una vez que hemos definido la representaci´n de los estados del problema tenemos que definir
olos posibles movimientos. En nuestro problema es el granjero el que va a cruzar de orilla, solo o con
alg´ n personaje.
u
Hay cuatro posibilidades: cruza ´l solo, cruzar con el lobo, cruzar con la oveja, o cruzar con la
e
col. Como resultado de estos movimientos tendremos un nuevo estado en el que: ´l ha cambiado de
e
orilla, o ´l y alguno de los otros tres personajes (lobo, oveja, col)han cambiado de orilla.
e
Por ejemplo, si el estado actual es ( A B A B ) y el granjero cruza solo:
( cruzar-solo (A B A B ) ) devuelve el estado ( B B A B ) .
Funci´n para cambiar de orilla, que devolver´ la orilla opuesta a una dada:
o
a
(defun cambiar (orilla)
(cond (( equal orilla ’a) ’b )
(( equal orilla ’b) ’a ) ))
Movimientos del granjero, los representamos con cuatro funciones.Toman un estado como
entrada y devuelven el nuevo estado generado tras el movimiento, siempre que ´ste sea v´lido.
e
a
(defun cruzar-solo (estado)
(valido ( crear-estado ( cambiar (orilla-granjero estado) )
(orilla-lobo estado)
(orilla-oveja estado)
(orilla-col estado) ) ))
(defun cruzar-lobo (estado)
(cond ( (equal (orilla-granjero estado) (orilla-lobo estado) )
(valido ( crear-estado (...