El problema de los misioneros y los caníbales , y el problema de los maridos celosos , estrechamente relacionado con él , son clásicos acertijos de lógica de cruce de ríos . [1] El problema de los misioneros y los caníbales es un conocido problema de juguete en inteligencia artificial , donde fue utilizado por Saul Amarel como un ejemplo de representación de problemas. [2] [3]
En el problema de los misioneros y los caníbales, tres misioneros y tres caníbales deben cruzar un río utilizando un bote que puede llevar a dos personas como máximo, con la restricción de que, en ambas orillas, si hay misioneros presentes en la orilla, no pueden ser superados en número por los caníbales (si lo estuvieran, los caníbales se comerían a los misioneros). El bote no puede cruzar el río por sí solo sin personas a bordo. Y, en algunas variantes, uno de los caníbales tiene un solo brazo y no puede remar. [1]
En el caso 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. Con esta restricción, no puede haber tanto mujeres como hombres presentes en un banco en el que las mujeres superen en número a los hombres, ya que si los hubiera, al menos una de esas mujeres estaría sin su marido. Por lo tanto, al cambiar 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 los caníbales. [1]
Un sistema para resolver el problema de los misioneros y los caníbales en el que el estado actual se representa mediante 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 a ⟨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 solitario 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 del estado inicial y el resultado forma nodos secundarios de la raíz. Cualquier nodo que tenga más caníbales que misioneros en cualquiera de las orillas se encuentra en un estado no válido y, por lo tanto, se elimina de la consideración posterior. Los nodos secundarios válidos generados serían ⟨3,2,0⟩, ⟨3,1,0⟩ y ⟨2,2,0⟩. Para cada uno de estos nodos restantes, se generan nodos secundarios sumando 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.
La primera solución conocida para el problema de los maridos celosos, que utiliza 11 viajes de ida, es la siguiente: las parejas casadas se representan como α (hombre) y a (mujer), β y b , y γ y c . [4] , pág. 291.
Esta es la solución más corta al problema, pero no es la única solución más corta. [4] , p. 291.
Sin embargo, si solo un hombre puede salir del bote a la vez y los maridos deben estar en la orilla para ser considerados con su esposa en lugar de estar solo en el bote en la orilla: el movimiento 5 a 6 es imposible, porque tan pronto como γ haya 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 los caníbales al reemplazar a los hombres por misioneros y a las mujeres por caníbales. En este caso, podemos descuidar las identidades individuales de los misioneros y los caníbales. La solución que acabamos de dar es aún 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:
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, puede cruzar cualquier número de parejas. [4] , p. 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 añade una isla en medio del río, 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. 76 si se permiten, entonces se requieren 4 n +1 viajes si n excede 4, aunque una solución mínima requiere solo 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 necesarios no cambia si no se permiten los cruces de orilla a orilla; sin embargo, si se permiten, el número de viajes disminuye a 4 n −1, suponiendo que n es al menos 3. [1] , p. 81.
La primera aparición conocida del problema de los maridos celosos se encuentra en el texto medieval Propositiones ad Acuendos Juvenes , generalmente atribuido a Alcuino (fallecido en 804). En la formulación de Alcuino, 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 hasta el XV, el problema se hizo conocido en toda Europa del Norte, y las parejas ahora eran maridos y esposas. [4] , pp. 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ó variar el 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 bote para dos personas, fue resuelta completamente 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]