REDES SEMANTICAS
Enviado por magymmmh • 27 de Febrero de 2014 • 785 Palabras (4 Páginas) • 252 Visitas
Problema de caníbales y misioneros
10 de febrero de 2014
Descripción:
En un lado del rio nos encontramos 3 caníbales y 3 misioneros. Hay un bote para transportar personas al otro lado del rio.
No más de dos personas caben en bote y al menos una persona puede mover el bote. El objetivo principal es conseguir que todas las personas lleguen al otro lado del rio sin que sobrepase el número de caníbales que de misioneros en ningún lado. Para hacerlo tenemos que encontrar una solución paso por paso para llegar al final del rio.
Algoritmo de búsqueda: Anchura
Básicamente es documentar los estados de situaciones presentes del problema, en este caso definimos como (3,3, 1) el número de misioneros, caníbales y el barco dispone el lugar, respectivamente.
Ahora la representación gráfica es similar a un árbol de búsqueda con nodos hijos y padres.
Para cada estado se produce una serie de posibles combinaciones de estados que pueden producir, pero cada estado debe de verificar si existe o no un estado ya producido antes de continuar para evitar una generación infinita de estados, si llega un momento que no puede producir más estados puede volver al estado padre para verificar si puede llegar a la solución.
La idea no es encontrar una solución rápida, si no llegar a encontrar una solución al problema de manera óptima que garantiza la solución, en este caso tomamos este algoritmo como nuestro factor de nuestra solución del problema.
Por lo tanto para este problema tenemos lo siguiente:
Estado Inicial: 3 caníbales, 3 misioneros y el bote están al lado izquierdo del rio.
Por lo tanto el estado inicial es el siguiente (3, 3,1) (0,0,0)
Que simboliza que los 3 misioneros y los tres caníbales están del lado izquierdo además del bote y del lado derecho no hay nada.
Limitaciones: no puede haber más caníbales que misioneros en cualquiera de las dos orillas del rio.
Operaciones: hay 5 posibles operaciones que se pueden realizar siempre y cuando cumplan con las limitaciones.
Operación 1: 1 caníbal y 1 misionero.
Operación 2: 2 caníbales y 0 misioneros.
Operación 3: 0 caníbal y 2 misioneros.
Operación 4: 0 caníbal y 1 misionero.
Operación 5: 1 caníbal y 0 misionero.
Estado Final: Los 3 caníbales, los 3 misioneros y el bote se deben encontrar del lado derecho (0, 0, 0) (3, 3,1).
...