HSE-96: Trabajo final =============================================================================== En la orilla izquierda de un río se encuentran M misioneros y C caníbales y una barca en la que caben como máximo B personas. El problema consiste en determinar cómo pueden trasladarse los misioneros y caníbales a la orilla derecha teniendo en cuenta que (a) si en la barca van misioneros, su número no puede ser menor que el de caníbales en la barca, (b) si en la orilla en la que no está la barca hay misioneros, su número no puede ser menor que el de caníbales en dicha orilla y (c) la barca no puede ir vacía. ------------------------------------------------------------------------------- En este trabajo se necesitará el fichero "busqueda-heuristica-sin-operadores.lsp" para completar los apartados 5, 6 y 7, así como los ficheros de experimentos: "misioneros-clp.exp" "misioneros-2-clp.exp" "misioneros-lsp.exp" "misioneros-2-lsp.exp" ------------------------------------------------------------------------------- 1.- Escribir el fichero misioneros.clp con un programa CLIPS que encuentre una solución empleando una búsqueda mediante primero el mejor con la heurística heuristica(estado) = número de misioneros en la izquierda + número de canibales en la izquierda, si la barca está en la derecha y heuristica(estado) = número de misioneros en la izquierda + número de canibales en la izquierda - 2 si la barca está en la izquierda. Usar las variables globales ?*misioneros*, ?*canibales* y ?*capacidad* para definir el problema. Por ejemplo, CLIPS> (load "misioneros.clp") ... CLIPS> (deffunction problema (?m ?c ?b) (reset) (bind ?*misioneros* ?m) (bind ?*canibales* ?c) (bind ?*capacidad* ?b) (run)) CLIPS> (problema 3 3 2) 3 3 B || 0 0 2 2 || 1 1 B 3 2 B || 0 1 2 1 || 1 2 B 3 1 B || 0 2 1 1 || 2 2 B 2 2 B || 1 1 0 2 || 3 1 B 1 2 B || 2 1 0 1 || 3 2 B 1 1 B || 2 2 0 0 || 3 3 B CLIPS> En la solución, la primera fila representa el estado inicial (en la izquierda hay 3 misioneros, 3 caníbales y la barca y en la izquierda no hay nada), la segunda fila es el estado resultante del anterior (moviendo 1 misionero y un caníbal a la derecha) y así sucesivamente hasta la última que representa el estado final. El fichero misioneros-clp.exp contiene un conjunto de ejemplos para el programa de los misioneros. Al evaluar los ejemplos, mediante la orden (batch "misioneros-clp.exp") se genera el fichero misioneros-clp.res con los resultados obtenidos. Comprobar misioneros.clp con dichos ejemplos. ------------------------------------------------------------------------------- 2. Escribir el fichero misioneros-2.clp modificando en misioneros.clp la definición de la heurística para aumentar la eficiencia de la búsqueda y comprobarlo evaluando los ejemplos de misioneros-2-clp.exp. ------------------------------------------------------------------------------- 3. Determinar el mayor N tal que el programa misioneros-2.clp encuentra una solución para el problema de N misioneros y N caníbales en una barca con capacidad para dos personas y escribirlo como comentario al final del fichero misioneros-2.clp. ------------------------------------------------------------------------------- 4. Escribir el fichero misioneros.lsp con una representación en LISP del problema anterior. En esta ocasión los operadores asociados al problema dependen de la capacidad de la barca y NO se pueden determinar de antemano. Para suplirlo, definir una función SUCESORES que admita como argumento un estado del problema y devuelva como resultado la lista de todos los estados posibles a los que se puede acceder desde el estado original y respetando todas las restricciones del problema. Por ejemplo, para el caso en el que la capacidad de la barca sea 2, el número total de misioneros sea 3, el número total de canibales sea 3, y representemos los estados mediante una lista de tres elementos donde el primero sea el número de misioneros en la orilla de la izquierda, el segundo sea el número de caníbales en la orilla de la izquierda y el tercero sea 1, si la barca está en la orilla de la izquierda, y 0, si la barca está en la orilla de la derecha, se obtendrá > (setf *misioneros* 3 *canibales* 3 *capacidad* 2) 2 > (sucesores '(3 3 1)) ((2 2 0) (3 1 0) (3 2 0)) ------------------------------------------------------------------------------- 5. Escribir en el fichero misioneros.lsp la definición de la función MISIONEROS para que admita como argumentos claves el procedimiento de búsqueda y la función heurística. Crear también la función HEURISTICA-1 que implemente la heurística descrita en el apartado 1. Así, con cualquiera de las siguientes expresiones se calculan las soluciones del problema mediante el procedimiento de búsqueda por primero el mejor con la heuristica-1 (misioneros 3 3 2 :por 'primero-el-mejor :con 'heuristica-1) (misioneros 3 3 2 :por 'primero-el-mejor) (misioneros 3 3 2 :con 'heuristica-1) (misioneros 3 3 2) Por ejemplo, > (load "busqueda-heuristica-sin-operadores") T > (load "misioneros") T > (misioneros 3 3 2 :por 'primero-el-mejor) 3 3 B || 0 0 2 2 || 1 1 B 3 2 B || 0 1 2 1 || 1 2 B 3 1 B || 0 2 1 1 || 2 2 B 1 2 B || 2 1 0 1 || 3 2 B 1 1 B || 2 2 0 0 || 3 3 B NIL En la solución anterior, la primera fila corresponde al estado inicial (en la izquierda hay 3 misioneros, 3 caníbales y la barca y en la izquierda no hay nada), la segunda fila es el estado resultante del anterior (moviendo 1 misionero y un caníbal a la derecha) y así sucesivamente hasta la última que corresponde al estado final. El fichero misioneros-lsp.exp contiene un conjunto de ejemplos para el programa de los misioneros. Al evaluar los ejemplos, mediante la orden (load "misioneros-lsp.exp") se genera el fichero misioneros-lsp.res con los resultados obtenidos. Comprobar misioneros.lsp con dichos ejemplos. ------------------------------------------------------------------------------- 6. Escribir en el fichero misioneros.lsp la definición de una nueva heurística, HEURISTICA-2, para aumentar la eficiencia de la búsqueda y comprobarlo evaluando los ejemplos de misioneros-2-lsp.exp. ------------------------------------------------------------------------------- 7. Determinar el mayor N tal que el programa misioneros.lsp encuentra una solución para el problema de N misioneros y N caníbales en una barca con capacidad para dos personas, utilizando la funcion HEURISTICA-2, y escribirlo como comentario al final del fichero misioneros.lsp. ******************************************************************************* * IMPORTANTE: ******************************************************************************* Una vez finalizados todos los apartados anteriores, envía por correo electrónico a tu profesor los ficheros "misioneros.clp" (con Subject: Trabajo (misioneros.clp)) "misioneros-2.clp" (con Subject: Trabajo (misioneros-2.clp)) "misioneros.lsp" (con Subject: Trabajo (misioneros.lsp)) Si pones el Subject tal y como se indica antes recibirás por correo electrónico la confirmación de que tu mensaje ha llegado bien. Recuerda, las direcciones son: fmartin@cs.us.es si tu profesor es F. J. Martín. jalonso@cs.us.es si tu profesor es J. A. Alonso.