Conexión con interfaces
La solución del problema consta de dos partes separadas en varios ejecutables:
- El programa que dados dos estados busca el camino que hay que recorrer para llegar de uno a otro denominado puzzle.
- El interface con el usuario que recoge de éste los estados inicial y final y llama al programa anterior para que solucione el problema. Este interface se ha realizado con la librería curses y con Tcl/Tk pero la entrada/salida de puzzle es exactamente igual. Aquí vamos a mostrar la forma de petición de datos así como una introducción sobre lo que habría que cambiar en caso de modificación del problema.
Entrada
El programa puzzle espera tres tipos de argumentos:
- La heurística a utilizar que se pasa a través de la línea de comandos en forma de un entero entre 0 y 2 correspondientes respectivamente a la distancia Manhattan, el número de casillas bien colocadas y la nula para la búsqueda en anchura.
- El algoritmo a utilizar para resolver el problema de búsqueda.
- Los estados inicial y final entre los que realizar la búsqueda del camino que se almacenan en unos ficheros intermedios denominados inicial y final. La estructura de estos ficheros es la siguiente:
filas x columnas
1 2 3
4 5 6
7 8 0
donde filas y columnas representan el número de filas y columnas. Esta lectura de los ficheros se realiza en la función leerEstadosIF que se encuentra en el fichero puzzle.c.
Salida
La salida depende de si se ha encontrado la solución o no.
- En caso de que no se haya encontrado el programa puzzle nos devuelve un mensaje de error indicando que los estados corresponden a distintas configuraciones.
- Si se ha encontrado la solución el programa crea dos ficheros :
- En uno se encuentran los movimientos que se deben realizar para llegar del estado inicial al final. Este fichero se denomina
solucion
y en cada línea contiene un movimiento del espacio en blanco. Estos movimientos pueden ser N, S, E, O.
- En otro, denominado
generales
están los datos de la solución en el siguiente orden:
- Nodos totales que es un entero.
- Máxima profundidad alcanzada que también es un entero.
- Nodos repetidos, un entero.
- Nodos generados, otro entero.
- Número de movimientos, entero.
- Tiempo de usuario gastado en segundos que es también un flotante con 3 decimales.
Esta solución se genera en la función main
del fichero puzzle.c.
Modificaciones
Sobre este programa se pueden realizar variaciones sin tener que reescribirlo en su totalidad debido a su modularidad. Por ejemplo se pueden crear más interfaces con solo tener en cuenta las especificaciones dadas antes sobre la entrada y salida aunque lo más importante puede ser el realizar modificaciones para el uso de los algoritmos utilizados, ya sean el A*, el IDA*, el SMA* o el DFID, en la resolución de otros problemas. Los pasos podrían ser los siguientes:
- Lo primero es ver si la representación de los estados debe cambiar en cuyo caso tenemos que cambiar la definición de los mismos y las funciones de creación y destrucción de los mismos. Todo esto se encuentra en los ficheros estado.c y estado.h.
- Puede que la representación de los estados no la haya que cambiar pero, en cambio, pueden existir nuevos operadores. La definición de éstos y su estructuración se encuentran en los ficheros operadores.c y operadores.h y su integración en el proceso de búsqueda se encuentra en la definición del array de operadores por lo que sólo habría que definir los nuevos operadores, introducirlos en el vector de operadores y variar la definición del máximo número de operadores.
- También puede haber que definir nuevas heurísticas lo que se puede hacer de forma similar a la definición de nuevos operadores salvo que éstas se encuentran en heuristica.c.html y heuristica.h.html y la definición del vector de heurísticas se encuentra también en busqueda.c.