Problema de caníbales y misioneros
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 la inteligencia artificial , donde fue utilizado por Saul Amarel como ejemplo de representación del problema. [2] [3]
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 por sí 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 a misioneros y a las mujeres a 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]
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⟩) son entoncesrestado del estado inicial, con el resultado formando 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.
La primera solución conocida al 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.
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.
La línea roja continua denota opcionalmente que el caníbal no puede remar.
En la figura de la derecha, si una esposa o un caníbal que se queda en el bote cuenta como si estuviera sola (en un círculo), es posible una solución más corta.