El problema de los misioneros y los caníbales

El problema de los misioneros y los caníbales , y el problema de los maridos celosos , estrechamente relacionado , son acertijos lógicos clásicos de cruce de ríos . ^{[ 1 ]} El problema de los misioneros y los caníbales es un problema de juguete muy conocido en inteligencia artificial , donde Saul Amarel lo utilizó como 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 en una barca con capacidad para un máximo de dos personas, con la condición de que, en ambas orillas, si hay misioneros, no pueden ser superados en número por los caníbales (de lo contrario, los caníbales se comerían a los misioneros). La barca no puede cruzar el río sola, sin nadie a bordo. Además, en algunas variantes, 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 hombres y mujeres presentes en una orilla donde las mujeres superen en número a los hombres, ya que, de ser así, al menos una de esas mujeres estaría sin su marido. Por lo tanto, al cambiar a los hombres por misioneros y a 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 caníbales donde 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 la orilla equivocada, respectivamente. Dado que el barco y todos los misioneros y caníbales comienzan en la orilla equivocada, 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 solitario cruza 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 la orilla equivocada, 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 hijos de la raíz. Cualquier nodo que tenga más caníbales que misioneros en cualquiera de las orillas está en un estado inválido y, por lo tanto, se elimina de la consideración posterior. 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, se generan nodos hijos sumando cada uno de los posibles vectores de acción. El algoritmo continúa alternando resta y 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 el camino desde la raíz del árbol hasta este nodo representa una secuencia de acciones que resuelve el problema.

La primera solución conocida al problema de los maridos celosos, utilizando 11 viajes de ida, es la siguiente. Las parejas casadas están representadas como α (hombre) y a (mujer), β y b , y γ y c . ^{[ 4 ] ,  pág.  291.}

Esta es una solución más corta al problema, pero no es la única solución más corta. ^{[ 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 que se les considere con su esposa en lugar de simplemente estar 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 marido, a pesar de que él esté solo 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 a las mujeres por caníbales. En este caso, podemos obviar las identidades individuales de los misioneros y caníbales. La solución que se acaba de presentar sigue siendo 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) se considera que está sola (es decir, no está en presencia de ningún hombre en la orilla), entonces este acertijo se puede resolver en 9 viajes de ida:

Una generalización obvia consiste en variar el número de parejas celosas (o misioneros y caníbales), la capacidad del barco, o ambas. 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 puede albergar a 3 personas, entonces pueden cruzar hasta 5 parejas; si el barco puede albergar a 4 personas, puede cruzar cualquier número de parejas. ^{[ 4 ] ,  pág.  300.} Fraley, Cooke y Detrick presentaron en 1966 un enfoque sencillo de teoría de grafos para analizar y resolver estas generalizaciones. ^{[ 7 ]}

Si se agrega una isla en medio del río, entonces cualquier número de parejas puede cruzar usando un bote de 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 requeridos 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.  74.} Desde el siglo XIII hasta el XV, el problema se dio a conocer en toda Europa del Norte, siendo ahora las parejas maridos y mujeres. ^{[ 4 ] ,  pp.  291–293.} El problema se planteó más tarde en forma de amos y sirvientes; la formulación con misioneros y caníbales no apareció hasta finales del siglo XIX. ^{[ 1 ] ,  p.  81} Variar el número de parejas y el tamaño del barco se consideró a principios del siglo XVI. ^{[ 4 ] ,  p.  296.} Cadet de Fontenay consideró colocar una isla en medio del río en 1879; esta variante del problema, con una embarcación para dos personas, fue completamente resuelta por Ian Pressman y David Singmaster en 1989. ^{[ 1 ]}

En 2020, la controversia en torno a una caricatura sobre el problema llevó a la junta examinadora AQA a retirar un libro de texto. ^{[ 8 ]}

• Problema de lobos, cabras y repollo
• Circunscripción (lógica)