misioneros y canibales???? parte 1
June 20, 2006revisando mis cosas del semestre pasado me encontre con la primera Übungsblatt de Künstlichen Intelligenz(inteligencia artificial) este es el ejercicio 2:
tres misioneros y tres canibales se encuentran juntos con un bote el el mismo lado del rio, el bote puede transportar como maximo 2 personas . La unica manera segura de hacerlo es que en cada orilla del rio nunca puedan haber mas canibales que misioneros, Como podemos trasladar a las 6 personas de un lado del rio al otro?
quizas muchas personas lo hallan escuchado alguna vez en su vida y hasta lo solucionaron.
Empezemos:
Estado inicial: 3 canibales y 3 misioneros estan al lado izquiero del rio
El estado lo definirán 5 valores (CI,MI,CD,MD,DEB)
CI: ladrones lado izquierdo
MI: misioneros lado izquierdo
CD:ladrones lado derecho
MD:misioneros lado derecho
DEB: Donde esta el bote -> si esta a la izquierda es 0 , si esta a la derecha es 1
por lo tanto el estado inicial es el siguiente (3,3,0,0,0)
Limitaciones: NO pueden haber mas caniables que misioneros en cualquiera de las dos orillas del rio -> CI
Operaciones: hay 5 posibles operaciones que se pueden realizar siempre y cuando cumplan con las limitaciones anteriormente descritas.
OP1: cruzar 1 canibal y 1 misionero
OP2: cruzar 2 canibales y 0 misionero
OP3: cruzar 0 canibal y 2 misioneros
OP4: cruzar 0 canibal y 1 misionero
OP5: cruzar 1 canibal y 0 misionero
Estado final: Los 3 canibales y los tres misioneros se encuentran al lado derecho del rio ->(0,0,3,3,1)
Solucion: la solucion correcta la podemos encontrar en 11 pasos Se animan?????
si ya saben la solucion. Como harian un programa de busqueda para encontrar la solucion de una manera optima.
Proximo post : solucion teorica e implementacion en Java
So ist das Leben! 
jaUJAua por un monto pense como hacerlo facil … pero despues me di cuenta que estaba mal xD
mañana cuando este mas despejadito lo intento resolver … ya estoy chato tanto leer.
Estoy muy cansado para pensar! xD
me quedo una duda con la restriccion
LI “<="MI && LD "<="MD
segun lo que pude extraer el texto la restriccion deberia ser
LI “<"MI && LD "<"MD
o estoy leyendo mal??
xD
pd:tuve que escribir el menor igual y etc entre comillas pk el analizador lexico de esto me lo tomaba como una instruccion de html :s
pense que con \< se solucionaba el problema pero no fue asi :S
si sabes como hacerlo me enseñas please
disculpa utilize otra notacion use siglas en aleman la restriccion es esta
CI<=MI && CD <=MD pero en el texto solo pone restriccion a que nunca puede haber mas canibales que misioneros en cualquier lado del rio, no hay restriccion para que exista la misma cantidad en cada orilla ademas si lo piensas en un principio existe la misma cantidad de canibales y misioneros en la orilla del rio y es una situacion segura. la restriccion dice: la cantidad de canibales del lado izquierdo debe ser menor o igual que la cantidad de misioneros del lado izquierdo y la cantidad de canibales del lado derecho debe ser menor o igual que la cantidad de misioneros del lado derecho. La restriccion esta bien.
Igual voy a dejar por lo menos una o dos semanas hasta publicar la solucion para dar tiempo de trabajar a los curiosos.
saludos
Me ha servido mucho, se agradece !!
Ahora no tendrás algo similar pero con un macaco (mono) que gasta energía llevando bananas a un depósito??
Si es así te lo agradecería triplemente 😉
Mclene
No lo tengo.
pero si sigues la misma forma de plantear el ejercicio no debieras tener problemas.
saludos
creo que no deberian poner esta serie de problemas al alcance de cualquiera porque mi profesora de psicologia nos los pone en el examen y nadie los sabe resolver.
mm tengo que presentar esta solucion este fin de semana, habra alguien que me lo pueda brindar … mail galonso15@hotmail.com
Es lógica mira primero el misionero con el caníbal después dos caníbales dejas uno y buelve con el caníbal caro al izquierdo hay 2 canivales y al derecho hay tres misioneros y un caníbal bueno solo deja al caníbal a la derecha y coje dos misioneros y vete donde estan los caníbales y luego deja un MISIONERO Y COJE UN CANIBAL DESPUES DEJA AL CANIVAL Y COJE OTRO MISIONERO LUEGO DEJA LOS DOS MISIONEROS A LA IZQUIERDA Y COJE EL CANIVAL Y CON ESE CANIVAL CRUZALOS AH TODOS LOS DEMAS CANIBALES Y LISTO ESTA ES MI DIRECCION DIME SI LO LOGRASTES DANIELA_BANDINI@HOTMAIL.COM
Este es un clasico problema de busqueda primero en anchura, se basa en tomar un estado inicial, a partir de ese estado obtener cada uno de los estados posibles y para cada estado obtener a su vez los posibles, hasta encontrar el estdado deseado.
1) encolar primer estado
2) mientras tanga elementos en cola
3) desencolar elemento
4) es el estado deseado
5) si lo es imprime solucion y terminar
6) si no lo es generar todos los estados (no evaluados) a partir del estado desencolado
Como ven la solucion usa un almacenamiento para cada uno de los estados encolados y los estados procesados.
mmmmmmmm, necesito implementarlo también en java…pero con el método de best-first-search…que se supone es el más adecuado…..mmmmmm….si logro desarrollarlo….les aviso…
Necesito urgente el codigo del juego en java :s si fueran amables de pasarmelo?¿?’ gracias
Holas holas muchachos!!! que tal si les pongo el reto de solucionar este problema, utilizando logica difusa y pues implementarlo en MATLAB aver si alguien lo sube !!!! o nos manda un link para poderlo observar……………. DISFRUTENLO !!!!
Hola a tod@s :
El dato que se os esta escapando , es que solamente un misionero y un canibal saben remar , por lo tanto , uno de ellos siempre tiene que ir en la barca.
Saludos
Solucion: el truco es pasar a lo misioneros primero sin que en un lado haya mas canibales que misioneros, asi que:
pasa M,C, del otro lado se baja solo C, y vuelve el M, ahora pasas C,C se baja C, y vuelve el otro C, ahora pasas dos M,M, y se bajan los dos M,M vuelven C,M, ahora pasas dos M,M, y vuelve un C, ahora pasas dos C,C se baja un C, y el otro c, vuelve ahora pasas a los dos C,C que quedaban,es un poco enredado pero esa fue la solucion que encontre si hay otra envienla,..
solucion:es similar a la anterior,con la unica diferencia de q la primera vez pasa cc,se queda c,vuelve c,ahora pasa cc,se queda c,vuelve c,ahora pasa mm se queda m,vuelve mc,ahora pasa mm,se queda mm y vuelve c,ahora pasa cc,se queda c,vuelve c,ahora pasa cc,se queda cc,y asi pasaron los 3 misioneros y los 3 canibales a la otra orilla…
_ _ _ _ _ _ M M M C C C
_ _ _ _ _ _ C C M M M _ _ C
_ _ C _ _ _ C M M M _ _ C
_ _ C _ _ _ C C M M M _ _ _
_ C C _ _ _ C M M M _ _ _
_ C C _ _ _ C M _ M M _ _ _
C C C _ _ _ M _ M M _ _ _
C C C _ _ _ M M _ _ M _ _ _
C C C M _ _ M _ _ M _ _ _
C C C M _ _ M M _ _ _ _ _ _
C C C M M _ M _ _ _ _ _ _
C C C M M M _ _ _ _ _ _
solucion larga y correcta
1. cruza (orilla 2) 1 misionero y 1 canibal
2. deja al canibal y regresa (orilla 1) el misionero
3. el misionero se baja de la canoa y se montan y cruzan(orilla 2) 2 canibales.
4. dejas a 1 canibal y el otro regresa (orilla 1)
5. el canibal se baja de la canoa y se montan los 2 misionros y cruzan (orilla 2)
6. regresa (orilla 1)1 canibal y 1 misionero
7. se baja el canibal y cruzan (orilla 2)2 misioneros
8. se bajan los misioneros y regresa (orilla 1)el canibal
9. el canibal se monta y cruza (orilla 2) con el otro canibal que estaba en la canoa
10.se baja un 1 canibal y regresa (orilla 1)el otro canibal
11.y el otro canibal se monta y cruzan (orilla 2)los 2 canibales
los 3 canibales y los 3 misioneros cruzan…
que DIOS LES BENDIGA…
como se puede solucionar con 5 canivales y 3 misioneros. de un lado del rio 3 canivales y los 3 misioneros y del otro lado 2 canivales y las reglas son las mismas.
este problema ke ponen ati la verdad e muy facil cuando estudiaba la preparatoria el maestro de matematicas nos puso uno similar pero mas dificil nadie lo pudo resolver y le dijimos ke era imposible despues de un rato el lo resolvio pero la vd no recuerdo como era la solucion y aora ke lo kiero enseñar amis amigos no me sale es asi:
ahy 4misioneros y 4 canivales es igual aunna barca donde solo caben 2 no se pueden kedar mas canibales ke misioneros de niuno de los dos lados pero abia otra restriccion a cual lo ase mas dificil ke todos los misioneros saben remar pero solo uno de los canibales sane remar si saben la respuesta porfavor aganmela saber.
niref87@hotmail.com
qaray, ezta muy dificil
ya lo intente y ninguna
zOluciOn funciOna
mejOr lo olvidO, biie
Hola chicos… si alguien tuviera el código java para 3 misioneros y 3 caníbales? de antemano muchas gracias… se los agradezco diegocastillonaranjo@gmail.com
;Tengo la solucion en Autolisp
;Esta es la solucion de misioneros y canibales publicado por Rolando Burgos Cárdenas
;modificada ligeramente por Lauriano Gonzalez Vasquez.
;Para encontrar otras soluciones se pueden modificar el orden de los posibles
;viajes en el bote contenidas en la variable “posibles”
;Todo tipo de comentarios seran analizadas
;Las orillas y el bote son representados por tripletas de (M C 1ó0)
;donde (3 3 1) indica 3 misioneros 3 canibales y el bote presente
(defun maac ()
(setq historia nil); inicializa los posibles movimientos
;(setq posibles ‘((0 2 1)(0 1 1)(1 1 1)(1 0 1)(2 0 1)))
; (setq posibles(reverse posibles))
(setq q ‘((((3 3 1) (0 0 0)))))
(while (not(equal (caaar q) ‘(0 0 0))); este bucle se repite hasta que está vacía la orilla izquierda
(if (not(or (comido (caar q)) (member (caar q) historia)))
(progn
(setq historia (cons (caar q) historia));ahora añade este estado a la historia y pasa
;al siguiente estado
;(setq q (expandir (car q) posibles) )
(setq q (append (expandir (car q) posibles) (cdr q)))
);progn
(setq q (cdr q));desecha un camino si da lugar a canibalismo
;o representa un bucle
);if
);while
;(display (reverse (car q)))
(if (not(member(reverse (car q)) soluciones ))
(setq soluciones (append (list(reverse (car q))) soluciones ))
)
)
(defun comido (estado)
; esta función comprueba si existe canibalismo examinando
; la orilla izquierda (car estado). Si allí M es 1 0 2
; y M C, entonces hay canibalismo en una u otra orilla.
; Si no, no hay en ninguna.
(and (or (= (caar estado) 1)
(= (caar estado) 2)
)
(not (= (caar estado) (cadar estado)))
)
)
(defun expandir (actual posibles) ; esta función desarrolla todos los posibles movimientos
; a partir del estado actual.
(cond
((null posibles) nil)
((movcorrecto (car actual) (car posibles))
(cons (cons (mover (car actual) (car posibles)) actual) (expandir actual (cdr posibles))))
(t (expandir actual (cdr posibles)))
)
)
(defun movcorrecto (estado unmovimiento)
; aquí se resta el número de misioneros y caníbales
; que hay en el bote del número que queda
; en la orilla actual, para asegurarse que no se cogen
; más de los que hay.
(cond
((zerop (caddar estado))(restatodo (cadr estado) unmovimiento))
(t (restatodo (car estado) unmovimiento))
)
)
(defun restatodo (izq_der unmovimiento)
; esta función resta los tres números de un movimiento
; del bote del contenido de una orilla y devuelve
; nil si cualquiera de Las diferencias es “)))
(princ(append (list(nth 0 (nth cont camino)))cadena (list(nth 1 (nth cont camino))) ))
(print)
)
(progn
(setq cam (mapcar ‘- (nth 1(nth (1- cont) camino))(nth 1 cam )))
(setq cadena(list (strcat “<–("(itoa (car cam))"-"(itoa (car (cdr cam)))"-"(itoa 1)") ")))
(princ(append (list(nth 0 (nth cont camino)))cadena (list(nth 1 (nth cont camino))) ))
(print)
)
)
(setq cont(1+ cont))
)
(prin1)
)
(defun aleatorio()
(setq posibilidades '((0 2 1)(0 1 1)(1 1 1)(1 0 1)(2 0 1)))
(setq soluciones nil)
(setq posibl nil)
(setq orden '(0 1 2 3 4))
( repeat 5
(setq posi 0)
(setq num (nth 0 orden))
(repeat 4
(setq posi(1+ posi))
(setq recorre(nth posi orden))
(setq orden(subst 9 num orden ))
(setq orden(subst num recorre orden ))
(setq orden(subst recorre 9 orden ))
(foreach ls orden (setq posibl (append posibl (list(nth ls posibilidades)))))
(setq posibles posibl)
(maac)
(setq posibl nil)
)
)
(presenta)
)
(defun presenta()
(setq cont 0)
(repeat (length(nth 0 soluciones))
(print(append (nth cont (nth 0 soluciones))
(nth cont (nth 1 soluciones))
(nth cont (nth 2 soluciones))
(nth cont (nth 3 soluciones))
)
)
(setq cont(1+ cont))
)
)
;Esta es la solucion de misioneros y canibales publicado por Rolando Burgos Cárdenas
;modificada ligeramente por Lauriano Gonzalez Vasquez.
;Para encontrar otras soluciones se pueden modificar el orden de los posibles
;viajes en el bote contenidas en la variable “posibles”
;Todo tipo de comentarios seran analizadas
;Las orillas y el bote son representados por tripletas de (M C 1ó0)
;donde (3 3 1) indica 3 misioneros 3 canibales y el bote presente
(defun myc ()
(setq historia nil); inicializa los posibles movimientos
;(setq posibles ‘((0 2 1)(0 1 1)(1 1 1)(1 0 1)(2 0 1)))
; (setq posibles(reverse posibles))
(setq q ‘((((3 3 1) (0 0 0)))))
(while (not(equal (caaar q) ‘(0 0 0))); este bucle se repite hasta que está vacía la orilla izquierda
(if (not(or (comido (caar q)) (member (caar q) historia)))
(progn
(setq historia (cons (caar q) historia));ahora añade este estado a la historia y pasa
;al siguiente estado
;(setq q (expandir (car q) posibles) )
(setq q (append (expandir (car q) posibles) (cdr q)))
);progn
(setq q (cdr q));desecha un camino si da lugar a canibalismo
;o representa un bucle
);if
);while
(display (reverse (car q)))
)
(defun comido (estado)
; esta función comprueba si existe canibalismo examinando
; la orilla izquierda (car estado). Si allí M es 1 0 2
; y M C, entonces hay canibalismo en una u otra orilla.
; Si no, no hay en ninguna.
(and (or (= (caar estado) 1)
(= (caar estado) 2)
)
(not (= (caar estado) (cadar estado)))
)
)
(defun expandir (actual posibles) ; esta función desarrolla todos los posibles movimientos
; a partir del estado actual.
(cond
((null posibles) nil)
((movcorrecto (car actual) (car posibles))
(cons (cons (mover (car actual) (car posibles)) actual) (expandir actual (cdr posibles))))
(t (expandir actual (cdr posibles)))
)
)
(defun movcorrecto (estado unmovimiento)
; aquí se resta el número de misioneros y caníbales
; que hay en el bote del número que queda
; en la orilla actual, para asegurarse que no se cogen
; más de los que hay.
(cond
((zerop (caddar estado))(restatodo (cadr estado) unmovimiento))
(t (restatodo (car estado) unmovimiento))
)
)
(defun restatodo (izq_der unmovimiento)
; esta función resta los tres números de un movimiento
; del bote del contenido de una orilla y devuelve
; nil si cualquiera de Las diferencias es “)))
(princ(append (list(nth 0 (nth cont camino)))cadena (list(nth 1 (nth cont camino))) ))
(print)
)
(progn
(setq cam (mapcar ‘- (nth 1(nth (1- cont) camino))(nth 1 cam )))
(setq cadena(list (strcat “<–("(itoa (car cam))"-"(itoa (car (cdr cam)))"-"(itoa 1)") ")))
(princ(append (list(nth 0 (nth cont camino)))cadena (list(nth 1 (nth cont camino))) ))
(print)
)
)
(setq cont(1+ cont))
)
(prin1)
)