Práctica 2: Búsqueda informada A*.
En la siguiente versión de search.c, se han realizado los cambios
oportunos para permitir búsqueda heurística con la estrategia
A*. Las heurísticas se programan en los archivos de dominio.
Crear un nuevo directorio y descargar en él las nuevas versiones
de los siguientes ficheros:
Para seleccionar un dominio:
make domain DOM=8puzzle
Para compilar:
make
Para invocar el algoritmo ahora hay una nueva opción de manejo de la
frontera:
Recuerden que 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, breadth
(por defecto) o, a-star
.
- -v cuando imprime la
solución, muestra todos los estados intermedios por los que va pasando.
Objetivos de la práctica:
1. Comprender la implementación de búsqueda heurística
A* para lo que se deben estudiar las modificaciones introducidas en search.c.
2. Comprender las heurísticas implementadas para los problemas de
8puzzle y mission, para lo que se deben estudiar los ficheros correspondientes.
3. Comparar las soluciones y requerimientos de la búsqueda no informada
e informada, e implementar nuevas heurísticas. Para ello se implementará
una nueva heurística para el 8puzzle y se repetirá el estudio
de requerimientos tiempo/memoria para A* y para cada una de esas heurísticas,
comparándolo con los resultados obtenidos para las búsquedas
no informadas.
4. Repetir los estudios que conlleva el objetivo 3 con el problema de la
aspiradora.
Entrega de la práctica: La práctica se entregará el
19 de diciembre en el laboratorio de prácticas a las 11:30h. Para
el objetivo 3 se entregará una explicación de la nueva heurística
implementada, una tabla con los resultados de la práctica 1 y los
de las dos heurísticas ahora probadas, y se comentarán. Para
el objetivo 4 se explicarán las dos heurísticas para este problema
y se repetirá el tipo de tabla del objetivo 3. En las heurísticas
debe estudiarse de forma teórica la admisibilidad y dominancia, y
constatar el efecto de esas propiedades en los resultados.