Acertijo de los misioneros y los caníbales
El acertijo de los misioneros y los caníbales, y el estrechamente relacionado acertijo de los maridos celosos, es un clásico "acertijo de cruzar el río".[1] El acertijo de los misioneros y los caníbales fue usado por Saúl Amarel como un ejemplo de representación de problema.[2][3]
El acertijo editar
Misioneros y caníbales editar
En el acertijo de los misioneros y los caníbales, tres misioneros y tres caníbales tienen que cruzar un río con una barca que solo puede llevar como máximo dos personas, lo cual es un constreñimiento para ambos bandos, porque si hay misioneros presentes en el barco, los caníbales se comerían a los misioneros. La barca no puede cruzar por el río sin personas a bordo. Y, en algunas variaciones, uno de los caníbales o misioneros tiene sólo un brazo y no puede remar.[1]
Maridos celosos editar
En el acertijo de los maridos celosos, hay tres matrimonios, con el constreñimiento que ninguna mujer puede estar en la presencia de otro hombre a no ser que su marido también esté presente. Bajo este constreñimiento, no puede haber ambas mujeres y presente de hombres en un barco con mujeres y hombres, porque si hay, estas mujeres irían sin sus maridos. Por tanto, al cambiar de hombres a misioneros y de mujeres a caníbales, cualquier solución al acertijo de los maridos celosos también devendrá en una solución al acertijo de los misioneros y los caníbales.[1]
Solución editar
Un sistema actual para solucionar el acertijo de los misioneros y los caníbales por el cual el estado está representado por un vector sencillo ⟨m, c, b⟩. Los elementos del vector representan el número de misioneros, caníbales, y si la barca es en el lado incorrecto, respectivamente. Desde la barca y todo del misioneros e inicio de caníbales en el lado incorrecto, el vector está inicializado a ⟨3,3,1⟩. Las acciones usan la suma y la resta del vector para manipular el vector estatal. Para caso, si un caníbal solitario cruzó el río, el vector ⟨0,1,1⟩ sería restado del estatal de ceder ⟨3,2,0⟩. El estado reflejaría que hay todavía tres misioneros y dos caníbales en el lado incorrecto, y que la barca está ahora en el banco opuesto. A plenamente solucionar el problema, un árbol sencillo está formado con el estado inicial como la raíz. Las cinco acciones posibles (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩, y ⟨1,1,1⟩) es entonces restado del estado inicial, con el resultado que forma nodos de niños de la raíz. Cualquier nodo que tiene más caníbales que missionaries en cualquier banco es en un estado nulo, y es por tanto sacado de consideración más lejana. Los nodos de niños válidos generaron sería ⟨3,2,0⟩, ⟨3,1,0⟩, y ⟨2,2,0⟩. Para cada de estos nodos restantes, nodos de niños están generados por añadir cada uno de los vectores de acción posibles. El algoritmo continúa adición y sustracción alternas para cada nivel del árbol hasta un nodo está generado con el vector ⟨0,0,0⟩ cuando su valor. Esto es el estado de objetivo, y el camino de la raíz del árbol a este nodo representa una secuencia de acciones que soluciona el problema.
La solución más temprana conocida al problema de los maridos celosos, utilizando 11 viajes, como sigue. Los pares casados están representados como α (hombres) y a (mujeres), β y b, y γ y c., p. 291[4]
| Número de viaje | Empezando banco | Viaje | Acabando banco |
|---|---|---|---|
| (Inicio) | αa βb γc | ||
| 1 | βb γc | αUn → | |
| 2 | βb γc | ←α | Un |
| 3 | α β γ | bc → | Un |
| 4 | α β γ | ← Un | b c |
| 5 | αUn | βγ → | b c |
| 6 | αUn | ← βb | γc |
| 7 | Un b | αβ → | γc |
| 8 | Un b | ← c | α β γ |
| 9 | b | Un c → | α β γ |
| 10 | b | ← β | αUn γc |
| 11 | βb → | αUn γc | |
| (Llegada) | αUn βb γc |
Esta es la solución más corta para el acertijo, pero no es la única.[4]
Como se mencionó anteriormente, esta solución al problema de maridos celoso devendrá una solución al problema de los misioneros y los caníbales al reemplazar hombres por misioneros y mujeres por caníbales. En este caso podemos desatender las identidades individuales del misioneros y caníbales. La solución justo dada es todavía más corto, y es uno de cuatro soluciones más cortas.[5]
Si una mujer está en la barca en la orilla (pero no sobre la orilla) cuenta tan siendo por ella (i.e. no en la presencia de cualquier hombres en la orilla), entonces este rompecabezas puede ser solucionado en sólo 9 viajes de un solo sentido:
| Número de viaje | Empezando banco | Viaje | Acabando banco |
|---|---|---|---|
| (Inicio) | αUn βb γc | ||
| 1 | βb γc | αUn → | |
| 2 | βb γc | ← Un | α |
| 3 | β γc | ab → | α |
| 4 | β γc | ← b | αUn |
| 5 | γc | βb → | αUn |
| 6 | γc | ← b | αUn β |
| 7 | γ | bc → | αUn β |
| 8 | γ | ← c | αUn βb |
| 9 | γc → | αUn βb | |
| (Llegada) | αUn βb γc |
Variaciones editar
Una variación obvia es la del número de parejas celosas (o misioneros y caníbales), la capacidad de la barca, o ambos. Si la barca aguanta 2 personas, entonces 2 pares requieren 5 viajes; con 4 o más pares, el problema no tiene ninguna solución.[6] Si la barca puede aguantar 3 personas, entonces hasta 5 pares pueden cruzar; si la barca puede aguantar 4 personas, cualquier número de pares puede cruzar., p. 300.[4] Un sencillo graph-aproximación de teoría a analizar y solucionando estas generalizaciones estuvo dada por Fraley, Cooke, y Detrick en 1966.[7]
Si es añadida una isla en medio del río, entonces cualquier número de pares puede cruzar al utilizar una barca de dos personas. Si cruces de amontonar al banco no es dejado, entonces 8n−6 viajes de una maneras están requeridos a transbordador n pares a través del río;, p. 76 si están dejados, entonces 4n+1 viajes están requeridos si n supera 4, a pesar de que una solución mínima requiere sólo 16 viajes si n equals 4., p. 79.[1] Si las parejas celosos están reemplazados por misioneros y caníbales, el número de los viajes requeridos no cambia si cruces de amontonar al banco no es dejado; si son aun así el número de disminuciones de viajes a 4n−1, suponiendo que n es al menos 3., p. 81.
Historia editar
El primer aspecto conocido del problema de los maridos celosos es en el texto medieval Propositiones ad Acuendos Juvenes, normalmente atribuido a Alcuin (muerto en 804). En la formulación de Alcuin, los pares son hermanos y hermanas, pero el constreñimiento es igual —ninguna mujer puede estar en la compañía de otro hombre a no ser que su hermano esté presente— ., p. 74.[1] Del siglo XIII al siglo XV, el problema fue conocido en Europa del norte, con los pares ahora siendo maridos y mujeres.[4] El problema era más tarde puesto en la forma de maestros y ayudantes; la formulación con los misioneros y los caníbales no apareció hasta finales del siglo XIX., p. 81. Las variaciones del número de pares y la medida de la barca estuvo considerada a principios del siglo XVI. Cadet de Fontenay consideró colocar una pequeña isla en medio del río en 1879; esta variante del problema, con una barca de dos personas, fue completamente solucionada por Ian Pressman y David Singmaster en 1989.
Véase también editar
Referencias editar
- ↑ 'The Jealous Husbands' and 'The Missionaries and Cannibals' 73 (464). June 1989. pp. 73-81.
- Amarel, Saul (1968). Michie, Donald, ed. 3. Amsterdam, London, New York: Elsevier/North-Holland. pp. 131-171. Archivado desde el original el 8 de marzo de 2008.
- Stock, Oliviero, ed. (2006). Searching in a Maze, in Search of Knowledge: Issues in Early Artificial Intelligence 4155. Berlin/Heidelberg: Springer. ISBN 978-3-540-37901-0. doi:10.1007/11829263_1.
- ↑ Dold-Samplonius, Yvonne, ed. (2002). Jealous Husbands Crossing the River: A Problem from Alcuin to Tartaglia. Stuttgart: Franz Steiner Verlag. ISBN 3-515-08223-9.
- . APL '92, the International Conference on APL (St Petersburg, July 6–10, 1992). 1992. ISBN 0-89791-477-5. doi:10.1145/144045.144106.
- Peterson, Ivars (13 de diciembre de 2003). Tricky Crossings 164 (24). Consultado el 12 de marzo de 2011.
- Fraley, Robert; Cooke, Kenneth L.; Detrick, Peter (May 1966). Graphical Solution of Difficult Crossing Puzzles 39 (3). pp. 151-157.