Inteligencia Artificial

EJERCICIO 1:
Dibuje mediante un grafo dirigido o describa detalladamente mediante una tabla el espacio de estados (o
espacio de búsqueda) completo para el problema de los misioneros y los caníbales. Para ello
especifique: el conjunto de todos los estados posibles, el estado inicial, el o los estados meta, los
operadores aplicables a cada estado y el coste asociado a cada operador. En elproblema de los
misioneros y los caníbales, tres misioneros están junto a tres caníbales en una de las orillas de un río.
Existe un bote disponible en el río con capacidad máxima para dos personas. Se pide encontrar la
manera de trasladar a los misioneros y a los caníbales a la otra orilla del río, con la condición de que en
ningún momento quede en contacto un número de misioneros con un númeromayor de caníbales. La
dificultad reside en que si la condición mencionada no se cumple, alguno de los misioneros es devorado y
no se puede alcanzar el objetivo del juego. ¿Cuál es la solución menos costosa para este problema?
CRITERIOS DE EVALUACIÓN DEL EJERCICIO 1:
La evaluación sobre 10 puntos de este ejercicio se realizaría atendiendo a los siguientes criterios:
Los estados se especificancorrectamente: 2.5 puntos
Los operadores se especifican correctamente: 2.5 puntos
Los costes de los operadores se especifican correctamente: 1 punto
El espacio de búsqueda se dibuja (mediante un grafo dirigido) o se describe (mediante una tabla)
correctamente: 3 puntos
La solución de menor coste se especifica correctamente: 1 punto
SOLUCIÓN:
Para representar los posibles estados se va autilizar la siguiente notación:
-

“M” se corresponde con los misioneros.
“C” se corresponde con los caníbales.
El estado del problema se va a representar de la siguiente forma (X-Y), donde “X” representa a
los elementos {C, M} situados en el lado izquierdo de la orilla, e “Y” representa a los elementos
{C, M} situados en el lado derecho de la orilla. Por ejemplo, (CCM-CMM) representa lasituación
en la que dos caníbales y un misionero están en la orilla izquierda y dos misioneros y un caníbal
están en la orilla derecha.

Se va a suponer que, en un principio, todos los elementos están en la orilla izquierda, por lo tanto el
estado inicial es (CCCMMM-). El único estado de aceptación será (-CCCMMM) (no tienen porque estar en
dicho orden).
Dado que el bote sólo dispone de dos plazas,para cualquier estado las reglas de producción son las
siguientes: “C”, “M”, “CM”, “CC”, “MM”, que se traslade un caníbal, que se traslade un misionero, que se
trasladen un caníbal y un misionero, que se trasladen dos caníbales, que se trasladen dos misioneros
respectivamente.
Se considera que cada regla de producción tiene coste 1, ya que buscamos la solución que conlleve
menos viajes deorilla a orilla con el bote, sin que los caníbales devoren a ningún misionero.

ESTADOS

REGLAS DE PRODUCCIÓN
C

M

CM

CC

MM

(CCCMMM-)

(CCMMM-C)

(CCCMM-M)

(CCMM-CM)

(CMMM-CC)

(CCCM-MM)

(CCMMM-C)

(CMMM-CC)

(CCMM-CM)

(CMM-CCM)

(MMM-CCC)

(CCM-CMM)

(CCCMM-M)

Estado no permitido

(CMMM-CC)

(MMM-CCC)

(CMM-CCM)

(MM-CCCM)

(CCCMMM-)(CM-CCMM)

(CCMM-CM)

(CMM-CCM)

(CCM-CMM)

(CM-CCMM)

(MM-CCCM)

(CC-CMMM)

(CCMMM-C)

(M-CCCMM)

(CCCM-MM)
(MMM-CCC)

Estado no permitido
(CMMM-CC)

(MM-CCCM)

No aplicable

(CMM-CCM)

Estado no permitido

(CCM-CMM)

Estado no permitido

(MM-CCCM)

Estado no permitido

(CM-CCMM)

(M-CCCMM)

(C-CCMMM)

(-CCCMMM)

(CCCM-MM) (CMMM-CC)

(CC-CMMM)(C-CCMMM)

(CCM-CMM)

(CCCM-MM)

(-CCCMMM)

(CCMM-CM)

(CCC-MMM)

(CMM-CCM)

(M-CCCMM)
(C-CCMMM)
(-CCCMMM)

Estado no permitido
(-CCCMMM)

(CM-CCMM)

(CCM-CMM)

Estado de aceptación

Las soluciones menos costosas para el problema de los misioneros y los canívales son:
1- En primer lugar trasladar a dos caníbales a la orilla derecha del rio, volver con el bote vacío
a...