Licenciado

MISIONEROS Y CANÍBALES
GRUPO 9 El objetivo del problema es:  Deben cruzar el río 3 misioneros y 3 caníbales, de manera que la cantidad de caníbales no puede superar a la cantidad de misioneros porque estos serían comidos por los caníbales.

¿Cómo consiguen los 3 misioneros estar al otro lado del río junto con los caníbales sin que estos se los coman?  Formulemos el problema:    EstadoInicial: En (0,0,0,0,0,0,0) Función sucesor: Cruzar(x,x,x,x,x,x),En(y,y,y,y,y,y,y) Estado deseado: En (1,1,1,1,1,1,1)

Donde:  Para la función En (y,y,y,y,y,y,y) que nos indica la posición en la que se encuentran los elementos respecto al rio. Las tres primeras componentes corresponden a los 3 misioneros y las tres siguientes a los 3 caníbales, la última componente pertenece al bote, ya que estesiempre tiene que ser manejado por alguien tenemos que saber la ubicación que tiene para determinar el cruce o no de ciertos misioneros y/o caníbales; la añadiremos un valor de 0 o 1 a cada componente de la función teniendo el siguiente criterio: - y=0: Indica que se encuentra al lado izquierdo del rio. - y=1: Indica que se encuentra al lado derecho del rio.

Para la función Cruzar(x,x,x,x,x,x) que nosindica que elemento se encuentra en la balsa. Las tres primeras componentes corresponden a los 3 misioneros y las siguientes tres a los caníbales, en esta no necesitamos especificar una componente para el bote ya que éste siempre cruza, la añadiremos un valor de 0 o 1 a cada componente de la función teniendo el siguiente criterio: - x=0: Indica que el elemento no cruzará en el bote. - x=1: Indicaque el elemento cruzará en el bote.  



Recordemos que solo pueden cruzar dos elementos en una balsa y tiene alguien necesariamente que remar en el viaje. El estado deseado En(1,1,1,1,1,1,1) nos indica que los tres misioneros y los tres caníbales se encuentran en el otro lado del río, también el bote.

1er paso: Función sucesor: Cruzar(1,0,0,1,0,0),En(1,0,0,1,0,0,1) Cruzan 1 caníbal y 1misionero. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(1,0,0,1,0,0,1). Se observa que son diferentes por lo que seguimos con las operaciones.

2do paso: Función sucesor: Cruzar(1,0,0,0,0,0),En(0,0,0,1,0,0,0) Cruza 1 misionero. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(0,0,0,1,0,0,0). Seobserva que son diferentes por lo que seguimos con las operaciones.

3er paso: Función sucesor: Cruzar(0,0,0,0,1,1),En(0,0,0,1,1,1,1) Cruzan 2 caníbales. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(0,0,0,1,1,1,1). Se observa que son diferentes por lo que seguimos con las operaciones.

4to paso: Función sucesor: Cruzar(0,0,0,1,0,0),En(0,0,0,0,1,1,0)Cruza 1 caníbal. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(0,0,0,0,1,1,0). Se observa que son diferentes por lo que seguimos con las operaciones.

5to paso: Función sucesor: Cruzar(1,1,0,0,0,0),En(1,1,0,0,1,1,1) Cruzan dos misioneros. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠En(1,1,0,0,1,1,1). Se observa que son diferentes por lo que seguimos con las operaciones.

6to paso: Función sucesor: Cruzar(1,0,0,0,1,0),En(0,1,0,0,0,1,0) Cruzan un caníbal y un misionero. Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(0,1,0,0,0,1,0). Se observa que son diferentes por lo que seguimos con las operaciones.

7mo paso: Función sucesor:Cruzar(1,0,1,0,0,0),En(1,1,1,0,0,1,1) Cruzan 2 misioneros, tenemos entonces a tres misioneros y un caníbal al lado derecho Se compara el estado deseado con la función posición de este paso, es decir En(1,1,1,1,1,1,1) ≠ En(1,1,1,0,0,1,1). Se observa que son diferentes por lo que seguimos con las operaciones.

8vo paso: Función sucesor: Cruzar(0,0,0,0,0,1),En(1,1,1,0,0,0,0) Cruza un caníbal. Se compara...