Práctica 1: Búsqueda en árbol y grafo, no informada. Anchura y profundidad. Aplicación a un problema de puzzle de números.


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.8puzzle.com:En esta página pueden estudiarse propiedades de este tipo de puzzles. 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:

Se parte de un número inicial I y un número objetivo O y se tiene también un conjunto tabú de números; todos ellos del 100 al 999. Cada movimiento permite transformar un número en otro sumándole o restándole 1 a uno de sus dígitos. Por ejemplo se puede pasar del 534 al 535 o del 534 al 524. Las reglas a las que están sujetos los movimientos válidos son: no se puede sumar 1 al dígito 9 o restar 1 al dígito 0; no se puede hacer un movimiento que lleve a un número tabú; no se puede cambiar el mismo dígito en dos movimientos consecutivos. Se trata de encontrar la secuencia de movimientos posibles que llevan de I a O.
Tenga en cuenta que la información de cual ha sido el dígito afectado por el último movimiento debe mantenerse en la información de estado.


Entrega de la práctica:

La práctica se entregará en las horas de prácticas con fecha límite que indicará el profesor.
Se presentará:
-Un dibujo del árbol de búsqueda hasta la profundidad 3 de las soluciones en profundidad y anchura del problema del puzzle de números.
-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.