h1

misioneros y canibales???? parte 1

June 20, 2006

revisando 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

Advertisements

24 comments

  1. 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


  2. 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


  3. 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.


  4. Igual voy a dejar por lo menos una o dos semanas hasta publicar la solucion para dar tiempo de trabajar a los curiosos.

    saludos


  5. 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


  6. No lo tengo.
    pero si sigues la misma forma de plantear el ejercicio no debieras tener problemas.

    saludos


  7. 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.


  8. mm tengo que presentar esta solucion este fin de semana, habra alguien que me lo pueda brindar … mail galonso15@hotmail.com


  9. 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


  10. 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.


  11. 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…


  12. Necesito urgente el codigo del juego en java :s si fueran amables de pasarmelo?¿?’ gracias


  13. 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 !!!!


  14. 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


  15. 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,..


  16. 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…


  17. _ _ _ _ _ _ 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


  18. 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…


  19. 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.


  20. 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


  21. qaray, ezta muy dificil
    ya lo intente y ninguna
    zOluciOn funciOna
    mejOr lo olvidO, biie


  22. 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


  23. ;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))
    )
    )


  24. ;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)
    )



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: