Práctica 1: Búsqueda en árbol
y grafo, no informada. Anchura y profundidad. Aplicación al problema
de la aspiradora con obstáculos.
El fichero
search.c contiene el código de la
búsqueda en árbol y grafo, extraído
directamente del pseudocógigo del libro [Russell&Norvig03] e implementado
por Pedro Cabalar para la propuesta de prácticas del curso 2004.
Para construir cada dominio de búsqueda concreto (por ejemplo, el
8-puzzle), es necesario definir las funciones especificadas en el fichero
search.h
typedef struct tSearchNode_ {
tState *state;
struct tSearchNode_ *parent;
unsigned action;
int pathCost;
int depth;
} tSearchNode;
tState *initialState();
int goalTest(tState *s);
int executable(unsigned op,tState *s);
tState *successorState(unsigned op,tState *s);
int cost(unsigned op,tState *s);
int h(tSearchNode *n);
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 RIGHT 2
#define LEFT 3
#define NUM_OPERATORS 4
typedef struct tState_ {
int cells[3][3];
int r,c;
} tState;
-
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.
search admite tres
parámetros opcionales en línea de comando
search -a <algoritmo> -f <tipodeinsercion> -v
- -a <algoritmo>
especifica el tipo de algoritmo que puede ser
tree (por defecto) o graph.
- -f <tipodeinsercion>
fija la estrategia que puede ser
depth o breadth
(por defecto).
- -v cuando imprime
la solución, muestra todos los estados intermedios por los que va
pasando.
Por último, el programa de búsqueda utiliza un
módulo de colas que necesita los ficheros
queue.h y
queue.c. En search.c está también el código
de la búsqueda con topología en grafo para lo que se proporcionan
un módulo de hashing en
hash.h y
hash.c
www.cut-the-knot.org/pythagoras/fiteen.shtml:En esta página pueden extudiarse propiedades de este tipo de puzzles: en particular del 15puzzle (puzzle de Loyd) y del 8puzzle. De interés si se quiere implementar un chequeo previo a la búsqueda sobre la existencia o no de solución dadas una configuración inicial y una final.
Objetivos de la práctica 1:
1. Experimentar con los algoritmos de búsqueda en árbol
y grafo, búsqueda en anchura y búsqueda en profundidad, con
el problema de los misioneros y caníbales (
mission.c,
mission.h,
mission.pdf)
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 se codifican como
MxC
y 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.
2. Experimentar con los algoritmos de búsqueda en árbol
y grafo, búsqueda en anchura y búsqueda en profundidad, con
el problema del 8puzzle (
8puzzle.h,
8puzzle.c).
En particular deben presentarse los resultado de un estudio de las prestaciones
de la solución en tiempo y memoria para problemas de distinta longitud
de la solución, para las dos topologías y las dos estrategias.
3. Resolver el problema de la aspiradora ([Russell&Norvig03]) para
grids MxM, pero con la variante de que puede haber celdas que son obstáculos
por donde el agente aspiradora no puede pasar.
Entrega de la práctica:
La práctica se entregará en las horas de prácticas
el 21 de noviembre de 2005.
Se presentará:
-Un dibujo del árbol de búsqueda hasta la profundidad 3
de las soluciones en profundidad y anchura del problema de los misioneros
y caníbales.
-El estudio al que hace referencia el apartado 2.
-La solución al apartado 3.
Es importante observar que en la entrega de la práctica deben conocer bien el código de búsqueda (search) y del problema (domain) ya que se pedirán también variantes de los mismos.