El problema de los misioneros y caníbales , y el problema de los maridos celosos estrechamente relacionados , son los clásicos acertijos de lógica del cruce de ríos . [1] El problema de los misioneros y caníbales es un problema de juguete bien conocido en inteligencia artificial , donde fue utilizado por Saul Amarel como ejemplo de representación de problemas. [2] [3]
El problema
En el problema de los misioneros y caníbales, tres misioneros y tres caníbales deben cruzar un río utilizando un bote que puede llevar como máximo a dos personas, con la restricción de que, para ambas orillas, si hay misioneros presentes en la orilla, no pueden ser superados en número por caníbales (si lo fueran, los caníbales se comerían a los misioneros). El barco no puede cruzar el río solo sin personas a bordo. Y, en algunas variaciones, uno de los caníbales tiene un solo brazo y no puede remar. [1]
En el problema de los maridos celosos, los misioneros y los caníbales se convierten en tres parejas casadas, con la restricción de que ninguna mujer puede estar en presencia de otro hombre a menos que su marido también esté presente. Bajo esta restricción, no puede haber mujeres y hombres presentes en un banco con mujeres más que hombres, ya que si las hubiera, estas mujeres estarían sin sus maridos. Por lo tanto, al cambiar a los hombres por misioneros y las mujeres por caníbales, cualquier solución al problema de los maridos celosos también se convertirá en una solución al problema de los misioneros y caníbales. [1]
Resolviendo
Un sistema para resolver el problema de los misioneros y caníbales en el que el estado actual está representado por un vector simple ⟨m, c, b⟩. Los elementos del vector representan el número de misioneros, caníbales y si el barco está en el lado equivocado, respectivamente. Dado que el barco y todos los misioneros y caníbales comienzan en el lado equivocado, el vector se inicializa en ⟨3,3,1⟩. Las acciones se representan mediante la resta / suma de vectores para manipular el vector de estado. Por ejemplo, si un caníbal solo cruzó el río, el vector ⟨0,1,1⟩ se restaría del estado para obtener ⟨3,2,0⟩. El estado reflejaría que todavía hay tres misioneros y dos caníbales en el lado equivocado, y que el barco ahora está en la orilla opuesta. Para resolver completamente el problema, se forma un árbol simple con el estado inicial como raíz. Las cinco acciones posibles (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩ y ⟨1,1,1⟩) se restan de el estado inicial, con el resultado de formar nodos hijos de la raíz. Cualquier nodo que tenga más caníbales que misioneros en cualquiera de los bancos se encuentra en un estado inválido y, por lo tanto, se elimina de una consideración adicional. Los nodos hijos válidos generados serían ⟨3,2,0⟩, ⟨3,1,0⟩ y ⟨2,2,0⟩. Para cada uno de estos nodos restantes, los nodos hijos se generan agregando cada uno de los posibles vectores de acción. El algoritmo continúa alternando la resta y la suma para cada nivel del árbol hasta que se genera un nodo con el vector ⟨0,0,0⟩ como su valor. Este es el estado objetivo y la ruta desde la raíz del árbol hasta este nodo representa una secuencia de acciones que resuelve el problema.
Solución
La primera solución conocida para el problema de los maridos celosos, utilizando 11 viajes de ida, es la siguiente. Las parejas casadas se representan como α (macho) y un (hembra), β y b , y γ y c . [4] , pág. 291.
Número de viaje | Banco inicial | Viaje | Banco final |
---|---|---|---|
(comienzo) | αa βb γc | ||
1 | βb γc | αa → | |
2 | βb γc | ← α | a |
3 | α β γ | bc → | a |
4 | α β γ | ← a | antes de Cristo |
5 | αa | βγ → | antes de Cristo |
6 | αa | ← βb | γc |
7 | ab | αβ → | γc |
8 | ab | ← c | α β γ |
9 | B | ac → | α β γ |
10 | B | ← β | αa γc |
11 | βb → | αa γc | |
(terminar) | αa βb γc |
Esta es la solución más breve al problema, pero no es la única solución más breve. [4] , pág. 291.
Sin embargo, si solo un hombre puede salir del bote a la vez y los maridos deben estar en la orilla para contar como con su esposa en lugar de estar solo en el bote en la orilla: mover 5 a 6 es imposible, porque tan pronto como γ ha salido b en la orilla, no estará con su esposo, a pesar de que él solo está en el bote.
Como se mencionó anteriormente, esta solución al problema de los maridos celosos se convertirá en una solución al problema de los misioneros y caníbales al reemplazar a los hombres por misioneros y las mujeres por caníbales. En este caso, podemos descuidar las identidades individuales de los misioneros y caníbales. La solución que se acaba de dar es todavía la más corta y es una de las cuatro soluciones más cortas. [5]
Si una mujer en el bote en la orilla (pero no en la orilla) cuenta como si estuviera sola (es decir, no en presencia de ningún hombre en la orilla), entonces este rompecabezas se puede resolver en 9 viajes de ida:
Número de viaje | Banco inicial | Viaje | Banco final |
---|---|---|---|
(comienzo) | αa βb γc | ||
1 | βb γc | αa → | |
2 | βb γc | ← a | α |
3 | β γc | ab → | α |
4 | β γc | ← b | αa |
5 | γc | βb → | αa |
6 | γc | ← b | αa β |
7 | γ | bc → | αa β |
8 | γ | ← c | αa βb |
9 | γc → | αa βb | |
(terminar) | αa βb γc |
Variaciones
Una generalización obvia es variar el número de parejas celosas (o misioneros y caníbales), la capacidad del barco o ambos. Si el barco tiene capacidad para 2 personas, entonces 2 parejas requieren 5 viajes; con 4 o más parejas, el problema no tiene solución. [6] Si el barco tiene capacidad para 3 personas, entonces pueden cruzar hasta 5 parejas; si el barco tiene capacidad para 4 personas, cualquier número de parejas puede cruzar. [4] , pág. 300. Fraley, Cooke y Detrick dieron un enfoque simple de teoría de grafos para analizar y resolver estas generalizaciones en 1966. [7]
Si se agrega una isla en el medio del río, entonces cualquier número de parejas puede cruzar usando un bote para dos personas. Si no se permiten los cruces de orilla a orilla, entonces se requieren 8 n −6 viajes de ida para transportar n parejas a través del río; [1] , pág. 76 si están permitidos, entonces se requieren 4 n +1 viajes si n excede 4, aunque una solución mínima requiere sólo 16 viajes si n es igual a 4. [1] , p. 79. Si las parejas celosas son reemplazadas por misioneros y caníbales, el número de viajes requeridos no cambia si no se permiten los cruces de banco en banco; sin embargo, si lo son, el número de viajes disminuye a 4 n −1, suponiendo que n es al menos 3. [1] , p. 81.
Historia
La primera aparición conocida del problema de los maridos celosos se encuentra en el texto medieval Propositiones ad Acuendos Juvenes , generalmente atribuido a Alcuin (fallecido en 804). En la formulación de Alcuin, las parejas son hermanos y hermanas, pero la restricción sigue siendo la misma: ninguna mujer puede estar en compañía de otro hombre a menos que su hermano esté presente. [1] , pág. 74. Desde el siglo XIII al XV, el problema se dio a conocer en todo el norte de Europa, siendo las parejas ahora maridos y esposas. [4] , págs. 291-293. El problema se planteó más tarde en forma de amos y ayuda de cámara; la formulación con misioneros y caníbales no apareció hasta finales del siglo XIX. [1] , pág. 81 A principios del siglo XVI se consideró la variabilidad del número de parejas y el tamaño del barco. [4] , pág. 296. Cadet de Fontenay consideró colocar una isla en medio del río en 1879; esta variante del problema, con un barco para dos personas, fue completamente resuelta por Ian Pressman y David Singmaster en 1989. [1]
En 2020, la controversia en torno a los temas racistas en una caricatura sobre el problema llevó a la junta examinadora de AQA a retirar un libro de texto que contenía el problema. [8]
Ver también
Referencias
- ^ a b c d e f g h i Pressman, Ian; Singmaster, David (junio de 1989). " ' Los Maridos Celosos' y 'Los Misioneros y Caníbales ' ". La Gaceta Matemática . 73 (464): 73–81. doi : 10.2307 / 3619658 . JSTOR 3619658 .
- ^ Amarel, Saul (1968). Michie, Donald (ed.). "Sobre representaciones de problemas de razonamiento sobre acciones" . Inteligencia de máquina . Amsterdam, Londres, Nueva York: Elsevier / North-Holland. 3 : 131-171. Archivado desde el original el 8 de marzo de 2008.
- ^ Cordeschi, Roberto (2006). "Buscando en un laberinto, en busca de conocimiento: problemas en la inteligencia artificial temprana". En stock, Oliviero; Schaerf, Marco (eds.). Razonamiento, acción e interacción en teorías y sistemas de IA: ensayos dedicados a Luigia Carlucci Aiello . Apuntes de conferencias en informática. 4155 . Berlín / Heidelberg: Springer. págs. 1–23. doi : 10.1007 / 11829263_1 . ISBN 978-3-540-37901-0.
- ^ a b c d e Franci, Raffaella (2002). "Maridos celosos cruzando el río: un problema de Alcuin a Tartaglia". En Dold-Samplonius, Yvonne; Dauben, Joseph W .; Folkerts, Menso; van Dalen, Benno (eds.). De China a París: 2000 años de transmisión de ideas matemáticas . Stuttgart: Franz Steiner Verla. págs. 289-306. ISBN 3-515-08223-9.
- ^ Lim, Ruby (1992). Shaw, Lynne C .; et al. (eds.). Caníbales y misioneros . APL '92, la Conferencia Internacional sobre APL (San Petersburgo, 6 al 10 de julio de 1992). Nueva York: Association for Computing Machinery. págs. 135-142. doi : 10.1145 / 144045.144106 . ISBN 0-89791-477-5.
- ^ Peterson, Ivars (13 de diciembre de 2003). "Travesías difíciles" . Noticias de ciencia . 164 (24) . Consultado el 12 de marzo de 2011 .
- ^ Fraley, Robert; Cooke, Kenneth L .; Detrick, Peter (mayo de 1966). "Solución gráfica de cruces difíciles". Revista de Matemáticas . 39 (3): 151-157. doi : 10.1080 / 0025570X.1966.11975705 . JSTOR 2689307 .
- ^ Corresponsal, Nicola Woolcock, Educación. "Libro de GCSE aprobado por la junta de examen AQA con imagen de caníbales cocinando misionero blanco" . ISSN 0140-0460 . Consultado el 19 de julio de 2020 a través de www.thetimes.co.uk.