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