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
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




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.