RESOLUCIÓN DE PROBLEMAS
Importante: Tenga presente que a continuación se presenta el juego de monjes y canívales, si este no inicia automáticamente y se presente un mensaje de "Loading Game 2" usted debe hacer clic derecho sobre él y luego seleccionar "Reproducir".
Problema:
Se tienen 3 monjes y 3 caníbales en el margen Oeste de un río. Existe una canoa con capacidad para dos personas como máximo. Se desea que los seis pasen al margen Este del río, pero hay que considerar que no debe haber más caníbales que monjes en ningún sitio porque entonces los caníbales se comen a los monjes. Además, la canoa siempre debe ser conducida por alguien.
Problema:
Se tienen 3 monjes y 3 caníbales en el margen Oeste de un río. Existe una canoa con capacidad para dos personas como máximo. Se desea que los seis pasen al margen Este del río, pero hay que considerar que no debe haber más caníbales que monjes en ningún sitio porque entonces los caníbales se comen a los monjes. Además, la canoa siempre debe ser conducida por alguien.
Solución:
El espacio de estados está definido por:
{(Mo, Co, Me, Ce, C) / Mo es el número de monjes en el margen oeste con
0<=Mo<=3 AND Co es el número de caníbales en el margen oeste con 0<=Co<=3
AND (Co<=Mo OR Mo=0) AND Me es el número de monjes en el margen este con
0<=Me<=3 AND Ce es el número de caníbales en el margen este con 0<=Ce<=3
AND (Ce<=Me OR Me=0) AND Co+Ce=3 AND Mo+Me=3 AND C = [E|O] es el margen dónde está la canoa}
El estado inicial es (3,3,0,0,O)
El estado final es (0,0,3,3,E)
Las reglas que se pueden aplicar son:
1. Viajan un monje y un caníbal de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=1 AND Co>=1 AND Ce+1<=Me+1 => (Mo-1, Co-1, Me+1, Ce+1, E)
2. Viajan un monje y un caníbal de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=1 AND Ce>=1 AND Co+1<=Mo+1=> (Mo+1, Co+1, Me-1, Ce-1,O)
3. Viajan dos monjes de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=2 AND (Mo-2=0 OR Co<=Mo-2) AND Ce<=Me+2=> (Mo-2, Co, Me+2, Ce, E)
4. Viajan dos monjes de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=2 AND (Me-2=0 OR Ce<=Me-2) AND Co<=Mo+2 => (Mo+2, Co, Me-2, Ce, O)
5. Viajan dos caníbales de O a E:
Si (Mo, Co, Me, Ce, O) AND Co>=2 AND (Me=0 OR Ce+2<=Me) => (Mo, Co-2, Me, Ce+2, E)
6. Viajan dos caníbales de E a O:
Si (Mo, Co, Me, Ce, E) AND Ce>=2 AND (Mo=0 OR Co+2<=Mo) => (Mo, Co+2, Me, Ce-2, O)
7. Viaja un monje de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=1 AND (Mo-1=0 OR Co<=Mo-1) AND Ce<= Me+1 => (Mo-1, Co, Me+1, Ce, E)
8. Viaja un monje de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=1 AND (Me-1=0 OR Ce<=Me-1) AND Co<=Mo+1 => (Mo+1, Co, Me-1, Ce,O)
9. Viaja un caníbal de O a E:
Si (Mo, Co, Me, Ce, O) AND Co>=1 AND (Me=0 OR Ce+1<=Me) => (Mo, Co-1, Me, Ce+1, E)
10. Viaja un caníbal de E a O:
Si (Mo, Co, Me, Ce, O) AND Ce>=1 AND (Mo=0 OR Co+1<=Mo) => (Mo, Co+1, Me, Ce-1, E)
Nota: En referencia a la regla 3 la condición Ce<=Me+2 puede intuirse como redundante. Esta condición no se cumple sólo en el caso Ce=3 y Me=0. Pese a que es un estado que pertenece al espacio de estados válidos, podemos intuir que nunca se llega a tener 3 caníbales y ningún monje del lado Este y la barca del lado Oeste. De todas maneras sólo se puede eliminar si podemos demostrar formalmente la imposibilidad de esta situación.
Un pasaje de estados para ir de (3,3,0,0,O) a (0,0,3,3,E) es el siguiente:
(3,3,0,0,O) => (3,1,0,2,E) => (3,2,0,1,O) => (3,0,0,3,E) => (3,1,0,2,O) =>
(1,1,2,2,E) => (2,2,1,1,O) => (0,2,3,1,E) => (0,3,3,0,O) => (0,1,3,2,E) =>
(0,2,3,1,O) =>(0,0,3,3,E)
El espacio de estados está definido por:
{(Mo, Co, Me, Ce, C) / Mo es el número de monjes en el margen oeste con
0<=Mo<=3 AND Co es el número de caníbales en el margen oeste con 0<=Co<=3
AND (Co<=Mo OR Mo=0) AND Me es el número de monjes en el margen este con
0<=Me<=3 AND Ce es el número de caníbales en el margen este con 0<=Ce<=3
AND (Ce<=Me OR Me=0) AND Co+Ce=3 AND Mo+Me=3 AND C = [E|O] es el margen dónde está la canoa}
El estado inicial es (3,3,0,0,O)
El estado final es (0,0,3,3,E)
Las reglas que se pueden aplicar son:
1. Viajan un monje y un caníbal de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=1 AND Co>=1 AND Ce+1<=Me+1 => (Mo-1, Co-1, Me+1, Ce+1, E)
2. Viajan un monje y un caníbal de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=1 AND Ce>=1 AND Co+1<=Mo+1=> (Mo+1, Co+1, Me-1, Ce-1,O)
3. Viajan dos monjes de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=2 AND (Mo-2=0 OR Co<=Mo-2) AND Ce<=Me+2=> (Mo-2, Co, Me+2, Ce, E)
4. Viajan dos monjes de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=2 AND (Me-2=0 OR Ce<=Me-2) AND Co<=Mo+2 => (Mo+2, Co, Me-2, Ce, O)
5. Viajan dos caníbales de O a E:
Si (Mo, Co, Me, Ce, O) AND Co>=2 AND (Me=0 OR Ce+2<=Me) => (Mo, Co-2, Me, Ce+2, E)
6. Viajan dos caníbales de E a O:
Si (Mo, Co, Me, Ce, E) AND Ce>=2 AND (Mo=0 OR Co+2<=Mo) => (Mo, Co+2, Me, Ce-2, O)
7. Viaja un monje de O a E:
Si (Mo, Co, Me, Ce, O) AND Mo>=1 AND (Mo-1=0 OR Co<=Mo-1) AND Ce<= Me+1 => (Mo-1, Co, Me+1, Ce, E)
8. Viaja un monje de E a O:
Si (Mo, Co, Me, Ce, E) AND Me>=1 AND (Me-1=0 OR Ce<=Me-1) AND Co<=Mo+1 => (Mo+1, Co, Me-1, Ce,O)
9. Viaja un caníbal de O a E:
Si (Mo, Co, Me, Ce, O) AND Co>=1 AND (Me=0 OR Ce+1<=Me) => (Mo, Co-1, Me, Ce+1, E)
10. Viaja un caníbal de E a O:
Si (Mo, Co, Me, Ce, O) AND Ce>=1 AND (Mo=0 OR Co+1<=Mo) => (Mo, Co+1, Me, Ce-1, E)
Nota: En referencia a la regla 3 la condición Ce<=Me+2 puede intuirse como redundante. Esta condición no se cumple sólo en el caso Ce=3 y Me=0. Pese a que es un estado que pertenece al espacio de estados válidos, podemos intuir que nunca se llega a tener 3 caníbales y ningún monje del lado Este y la barca del lado Oeste. De todas maneras sólo se puede eliminar si podemos demostrar formalmente la imposibilidad de esta situación.
Un pasaje de estados para ir de (3,3,0,0,O) a (0,0,3,3,E) es el siguiente:
(3,3,0,0,O) => (3,1,0,2,E) => (3,2,0,1,O) => (3,0,0,3,E) => (3,1,0,2,O) =>
(1,1,2,2,E) => (2,2,1,1,O) => (0,2,3,1,E) => (0,3,3,0,O) => (0,1,3,2,E) =>
(0,2,3,1,O) =>(0,0,3,3,E)