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 admisible para el 8puzzle y se comparará con la heurística implementada y con las búsquedas no informada (sólo con búsqueda en anchura) en términos de completud, optimalidad y una comparación de las dos heurísticas en cuanto a promedio de nodos generados.
4. Implementar dos heurísticas para el problema del puzzle de números y repetir los estudios que conlleva el objetivo 3. Implementar también el caso particular de h=0 y determinar que tipo de búsqueda se hace en este caso y cuales son sus propiedades.
Entrega de la práctica: La práctica se entregará en las horas de prácticas y en la fecha límite indicada por el profesor. Para
el objetivo 3 se entregará una explicación de la nueva heurística
implementada y los resultados que explican su comportamiento y las comparaciones. De manera similar debe contestarse al objetivo 4. En las heurísticas
debe estudiarse de forma teórica la admisibilidad y dominancia, y
constatar el efecto de esas propiedades en los resultados.