viernes, mayo 31, 2024
HomeTecnologíaProgramacionEl problema de los misioneros y los canibales, incluye codigo en prolog

El problema de los misioneros y los canibales, incluye codigo en prolog

Tres misioneros y tres caníbales están en una de las márgenes de un río junto a un bote en la que sólo cabe 1 o 2 personas. Hay que encontrar la manera de pasarlos al otro lado del río pero teniendo cuidado que en ningún momento quede un grupo de misioneros junto con un grupo  de caníbales, siendo la cantidad de misioneros menor a la de caníbales.
DEFINICION DEL PROBLEMA:
Se debe considerar una secuencia ordenada de 3 números que representarán: la cantidad de
misioneros, caníbales y en que orilla del río se encuentran.
Por lo tanto, el estado inicial será: 3,3,1.
El estado objetivo será: 0,0,0 en la orilla izquierda y 3,3,1 en la orilla derecha.
Operadores posibles:
Pueden ser que un bote:

  • No lleva ningún misionero y lleva un caníbal.
  • Lleva 2 misioneros y ningún caníbal.
  • Lleva 2 caníbales y ningún misionero.
  • Lleva 1 caníbal y un misionero.
  • No lleva ningún caníbal y lleva un misionero.

Solo está permitido si hay igual o más misioneros que caníbales en una orilla o no hay
misioneros que afectar en una orilla.
Se utilizará la búsqueda preferente por profundidad o depth search first.
En la búsqueda preferente por profundidad siempre se expande uno de los nodos que se
encuentre en los más profundo de árbol, por lo tanto los nodos sucesores estarán a
profundidades cada vez mayores.

Enlace al juego 

DESARROLLO EN PROLOG:

/* Problema de los Caníbales y Misioneros usando búsqueda Depth First
Desarrollado en : Visual Prolog v. 5.1
(versión gratuita de Prolog (VIP.exe) bajada de : www.visual-prolog.com ).
Autor : Javier Navarrete T.
******************************************************************************************** */
domains
orilla=orilla(byte,byte,byte)
bote=bote(byte,byte)
hecho=hecho(orilla,orilla)
database - canymis
hecho(orilla,orilla)
predicates
ejecutar.
profundidad(orilla,orilla).
ejecutar_movimiento(orilla,orilla,orilla,orilla).
movimiento(orilla,orilla,orilla,orilla).
imprime_estado(orilla,orilla).
invertir_orillaOproceder(orilla,orilla,orilla,orilla).
mostrar_movimiento(bote).
movimiento(bote).
permitido(orilla).
adicionar(orilla, bote, orilla).
quitar(orilla, bote, orilla).
aplicable(orilla,bote).
mostrar_bote(byte).
clauses
ejecutar :- /* llama a ejecutar para resolver */
assert(hecho(orilla(3,3,1), orilla(0,0,0))), /* estado inicial */
/* Estado INICIAL = 3 misioneros, 3 caníbales y 1 bote en la orilla izquierda
y nada en la orilla derecha */
profundidad(orilla(3,3,1),orilla(0,0,0)). /* busca a partir de este estado */
/* 5 posibles movimientos - no necesariamente permitidos */
movimiento(bote(0,1)). /* No lleva ningún misionero y lleva un caníbal */
movimiento(bote(2,0)). /* Lleva 2 misioneros y ningún caníbal */
movimiento(bote(0,2)). /* Lleva 2 caníbales y ningún misionero */
movimiento(bote(1,1)). /* Lleva 1 caníbal y un misionero (se supone que hay un barquero que los cuida)*/
movimiento(bote(1,0)). /* No lleva ningún caníbal y lleva un misionero */
/* si la situación es permitida */
permitido(orilla(0,_,_)) :- !. /* corte continua donde quedó */
permitido(orilla(M,C,_)) :- M >= C. /* si hay igual o más misioneros que canibales para que no se los coman */
profundidad(orilla(0,0,0),orilla(3,3,1)) :- /* si se encuentra el estado objetivo */
/* Estado OBJETIVO = 3 misioneros, 3 caníbales y 1 bote en la orilla derecha
y nada en la orilla izquierda */
nl,write(" >> Objetivo encontrado << "), nl, nl.
profundidad(Izq,Der) :-
/* Si no es el ESTADO OBJETIVO efectúa la búsqueda */
ejecutar_movimiento(Izq,Der,SgteIzq,SgteDer), /* ejecutar movimiento desde el estado actual */
imprime_estado(SgteIzq,SgteDer),
profundidad(SgteIzq,SgteDer). /* y llamarse recursivamente */
ejecutar_movimiento(Izq,Der,SgteIzq,SgteDer) :-
write("Toma la primera movida permitida que encuentren"),
movimiento(Izq,Der,SgteIzq,SgteDer), /* ver movimiento */
/* si no está el mov sgte. para no repetir situación */
not(hecho(SgteIzq,SgteDer)), /* para obtener un nuevo estado */
/* grabar el mov */
assert(hecho(SgteIzq,SgteDer)),
permitido(SgteIzq), permitido(SgteDer). /* ver si es permitido */
movimiento(orilla(MI,CI,1),Der,PSgteIzq,PSgteDer) :- /* si el bote está en la orilla izquierda */
/* Inicialmente recibirá :
en MI - misioneros a la izquierda 3
en CI - caníbales a la izquierda 3
y el 1 representa que el bote está en la orilla derecha */
invertir_orillaOproceder(orilla(MI,CI,1),Der,PSgteIzq,PSgteDer).
/* entonces el movimiento será de izquierda a derecha */
movimiento(orilla(ML,CL,0),Der,PSgteIzq,PSgteDer) :- /* si el bote está en la orilla derecha */
write("n <--> origen y destino n"),
invertir_orillaOproceder(Der,orilla(ML,CL,0),PSgteDer,PSgteIzq).
/* entonces el movimiento será de derecha a izquierda */
invertir_orillaOproceder(Origen,Destino,SgteO,SgteD) :- /* desde un origen a un destino */
/* Inicialmente recibirá :
en Origen - 3,3,1.
en Destino- 0,0,0.
*/
movimiento(BoteObtenido), /* obtener movimiento de de 5 posibles */
/* Pj si obtiene bote(0,1) */
/* verificar si orilla(3,3,1) el bote(0,1) es aplicable */
aplicable(Origen,BoteObtenido),
/* si opción es aplicable */
quitar(Origen,BoteObtenido,SgteO), /* tomar bote del origen */
/* 3,2,0 inicialmente adicionará un caníbal a la orilla derecha */
adicionar(Destino,BoteObtenido,SgteD), /* y adicionar al destino donde destino 0,0,0 inic */
mostrar_movimiento(BoteObtenido).
/* El movimiento es aplicable al estado */
aplicable(orilla(M,C,1), bote(Mbote,Cbote)) :-
/* inicialmente verá si orilla(3,3,1) y bote(0,1) es aplicable si
M(Cantidad de misioneros (3)) en mayor o igual la cantidad de misioneros en bote permitido (0),
como esto se cumple, ve si C(Cantidad de caníbales (3)) en mayor o igual que la cantidad de
caníbales permitidos en el bote según la combinación bote(0,1) permitida, como se cumple devuelve
un si.
*/
M >= Mbote, C >= Cbote. /* en otras palabras, hay suficiente de cada uno para llenar el bote? */
/* Quitar del origen */
quitar(orilla(MO,CO,1), bote(MB,CB), orilla(MCanti,CCanti,0)) :-
/* inicialmente recibirá orilla(3,3,1), bote(0,1) y un nuevo origen donde :
MCanti = la cantidad de misioneros que habia en la orilla origen (en este caso izq MO)
menos la cantidad de misioneros que suben al bote MB, cual dará 3
CCanti = igual para la cantidad de caníbales (3-1)=2
0 = indica la orilla izquierda
Quiere decir que la orilla izquierda quedará con 3,2,0 (3 mis y 2 cani) */
MCanti = MO-MB, CCanti = CO-CB.
/* Adicionar al destino */
adicionar(orilla(MD,CD,0), bote(MB,CB), orilla(MR,CR,1)) :-
/* Pj si el destino inicial es 0,0,0 y el bote (0,1) entonces :
MR = 0+0 = 0 misioneros a la orilla derecha por que no se transportó ninguno
CR = 0+1 = 1 caníbal a la orilla derecha por se transportó 1, el resultado
será que la orilla derecha tendrá 0 misioneros y 1 caníbal */
MR = MD+MB, CR = CD+CB.
imprime_estado(orilla(MIzq,CIzq,BoteI), orilla(MDer,CDer,_)) :- write("nLa orilla izquierda tiene : "),
write(MIzq), write(" misioneros y "), write(CIzq), write(" caníbalesn"),
write("La orilla derecha tiene : "), write(MDer), write(" misioneros y "),
write(CDer), write(" caníbalesn"), mostrar_bote(BoteI),
write("n>>>>>>>>>>>>>>>>>>Presione una tecla para
continuar<<<<<<<<<<<<<<<<<<<<n"),
readchar(_).
mostrar_movimiento(bote(M,C)) :- write("Movida : "), write(C), write(" caníbal(es) y "),
write(M), write(" misionero(s)n").
mostrar_bote(1) :- write("El bote está en la orilla izquierdan").
mostrar_bote(0) :- write("El bote está en la orilla derechan").
goal
ejecutar.

 

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments

Michgatubela_1592@hottmail.com on Mas frases , pensamientos para el dia del niño
Los “Circles” llegan a Facebook de foma no oficial | Tecnofull on Google+, el nuevo proyecto (red social ) de Google
carlos alberto castro cabañas on Generador de tarjetas para Feliz Cumpleaños gratis
Como eliminar el botón falso “no me gusta” de Facebook ‹ Tecnofull on Botón No me gusta, fraude / spam que inunda Facebook
Falso profeta del fin del mundo “Harold Camping” ganó 80 millones con farsa del 21 de Mayo 2011 « Genoma Web on Falso profeta del fin del mundo “Harold Camping” ganó 80 millones con farsa del 21 de Mayo 2011
Como eliminar el botón falso “no me gusta” de Facebook | on Botón No me gusta, fraude / spam que inunda Facebook
Manera gráfica de ver las busquedas de google por todo el mundo « Genoma Web on Search Globe, una manera gráfica de ver las búsquedas de Google por todo el mundo
Boda Real del Príncipe William y Catherine Middleton: Transmisión en vivo gratis por internet | TecnoFull on Eduman TV online, ver television de varios paises gratis por internet
Clasificacion de las mujeres geek. | Urban Wave on Clasificacion de las mujeres geek, humor
El problema de los misioneros y los canivabales, incluye codigo en prolog | TecnoFull on Jugar gratis los misioneros y los canibales