Práctica 1: Búsqueda en árbol
y grafo, no informada. Anchura y profundidad. Aplicación al problema
de la navegación de un robot.
El fichero
search.c contiene el código de la
búsqueda en árbol y grafo, extraído
directamente del pseudocódigo del texto de IA de Russell y Norvig 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 estudiarse 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
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.
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 debe determinarse, para las dos topologías y las dos estrategias, que tamaño máximo (longitud de la solución) de problema puede resolverse y cuales son los requerimientos de tiempo y memoria de la búsqueda.
3. Adaptar el código proporcionado para resolver el siguiente problema:
Un robot para la exploración de Marte tiene que dejar la nave nodriza,
recoger rocas de N lugares en cualquier orden y volver a la nave nodriza. Suponga
que el robot tiene un módulo de navegación que le permite ir directamente
a los sitios de interés. Por tanto el robot puede ejecutar las acciones ir-a-la-nave
ir-a-roca1, ir-a-roca2, ..., ir-a-rocaN cuyo efecto es desplazarse desde el lugar en el
que se encuentra al indicado en el nombre de la acción. El robot también
conoce el tiempo que le lleva desplazarse entre cada par de localizaciones. Se trata de
encontrar una secuencia de acciones que completen la tarea en el menor tiempo posible.
Entrega de la práctica:
La práctica se entregará en las horas de prácticas con fecha límite
el 20 de noviembre de 2006.
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 fecha límite de entrega de la práctica
los estudiantes deben presentarse sin retraso y 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
que deben realizarse en el horario de prácticas.