Archive for the ‘Artificial intelligence’ Category

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