Enunciado | Objetivos | Solución al 8 puzzle | Misioneros y caníbales | Archivos adicionales
Ejercicio 1: Búsqueda en árbol, no informada. Anchura y profundidad.
El fichero search.c contiene el código de
la búsqueda en árbol, extraído directamente del
pseudocógigo del libro [Russell&Norvig03]. Para construir
cada dominio de búsqueda concreto (por ejemplo, el 8-puzzle), es necesario definir las funciones
especificadas en el fichero search.h
tState *initialState();
int goalTest(tState *s);
int executable(unsigned op,tState *s);
tState *successorState(unsigned op,tState *s);
int cost(unsigned op,tState *s);
void showOperator(unsigned op);
void showState(tState *s);
Por ejemplo, para el 8-puzzle construiremos los ficheros
- 8puzzle.h que contendrá la definición del tipo
tState (la descripción de un estado del problema) así
como las acciones que podamos ejecutar (cada una tendrá un
código, que será una constante entera). Es imprescindible
definir la constante NUM_OPERATORS. Por ejemplo, en 8puzzle.h
podríamos tener las líneas:
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
#define NUM_OPERATORS 4
- 8puzzle.c que contendrá todo el
código para las funciones descritas en search.h. Entre los
includes the 8puzzle.c es necesario añadir en este orden:
#include "8puzzle.h"
#include "search.h"
El program search.c espera leer las definiciones del dominio en
los ficheros domain.h y domain.c. Una opción para cambiar de un
dominio a otro sería copiar 8puzzle.h y 8puzzle.c a domain.h y
domain.c respectivamente. Sin embargo, es más cómodo
crear links simbólicos, para que no haya que copiar de nuevo los
ficheros cada vez que cambiemos algo. Para simplificar la
creación de estos links y el proceso de compilación se
puede usar el fichero Makefile. Por ejemplo, para establecer un dominio determinado, teclearemos:
make domain DOM=8puzzle
que se encarga de crear los links simbólicos, estableciendo
en este caso como dominio de búsqueda el 8puzzle. Para compilar
el programa, simplemente tecleamos:
make
almacenándose el ejecutable en el fichero search.
Por último, el programa de búsqueda utiliza un módulo de colas que necesita los ficheros queue.h y queue.c. El fichero queue.h contiene una descripción de cada una de las funciones que se pueden utilizar.
OBJETIVOS DEL EJERCICIO 1
- Crear los dominios para el problema de 8-puzzle y para el
problema de Misioneros y Caníbales (ficheros mission.h y
mission.c). En el caso de 8 puzzle, se usarán los estados
inicial y final siguientes:
|
|
|
Estado inicial
|
|
Estado meta
|
- Experimentar con la búsqueda en anchura (la incluida por
defecto en search.c) en ambos casos. ¿Cuántos nodos se
expanden?
- Cambiar a búsqueda en profundidad, insertando al principio de la frontera, en lugar de al final:
- ¿Es necesario cambiar algo más en el algoritmo?
- ¿Cuántos nodos se expanden?
- ¿La solución es óptima?
MISIONEROS Y CANÍBALES
Se trata de resolver el siguiente problema:
A
un río llegan tres misioneros y tres caníbales que desean
cruzar a la otra orilla, usando una barca que tiene espacio para dos
personas como máximo. Si en cualquier momento los
caníbales superan en número a los misioneros en cualquier
orilla, se produce un desastre (se los comen). Encontrar la secuencia
de movimientos en la barca que permite trasladarlos a todos al otro
lado de forma segura.
Las acciones posibles podrían codificarse como MxCy que indica que desplazamos x misioneros e y
caníbales de una orilla a la opuesta. Así, dada la
capacidad de la barca, tendríamos tan sólo 5
posibilidades: M0C1, M1C0, M1C1, M2C0, M0C2.
Crear los ficheros mission.h y mission.c de forma similar a los desarrollados para 8puzzle.
SOLUCIÓN AL 8 PUZZLE
Los ficheros de solución están disponibles en 8puzzle.h y 8puzzle.c.
ARCHIVOS ADICIONALES