El objetivo del proyecto es aprender sobre el modelo de espacio de estados y sobre los diferentes algoritmos de búsqueda heurística. No sólo se evaluará la correctitud de la implementación; es importante que los algoritmos sean eficientes y puedan resolver los problemas propuestos en los tiempos estipulados. También es importante su ánalisis de resultados en el informe.
Consideramos los siguientes problemas:
- N-puzzles: 15-puzzle y 24-puzzle
- Cubo de Rubik: 3x3x3
- Top spin: 12-4, 14-4, y 17-4
- Torre de Hanoi con 4 astas: 12, 14, y 18 discos
Estudiar los árboles de búsqueda y su factor de ramificación sin eliminación de duplicados y con eliminación parcial de duplicados (poda de ancestros). Se deben crear tablas para cada problema donde se reporte el número de estados a cada profundidad en el árbol de búsqueda a partir del estado objetivo, hasta la profundidad máxima que se alcance en 15 minutos de ejecución.
Se deben implementar heurísticas PDBs para cada problema. Para los n-puzzles las PDBs deben ser aditivas. Para los otros problemas, se toma el máximo de varias PDBs. Leer el paper "Additive Pattern Databases" de Felner et al. que se incluye, y el paper sobre el Cubo de Rubik. Para el Cubo de Rubik, las PDBs estándar pueden tomar demasiado espacio; en ese caso, se pueden crear mas PDBs de menor tamaño.
Estudiar la búsqueda de soluciones óptimas con algoritmos informados. Buscar soluciones para las instancias dadas en cada problema utilizando los algoritmos: A* con eliminación retardada de duplicados (DDD) e IDA* con eliminación parcial de duplicados. Para las heurísticas en cada problema:
- N-puzzles: distancia Manhattan (15-puzzle) y diferentes additive PDBs (15- y 24-puzzle)
- Cubo de Rubik: max de corner PDB y 2 edge PDBs (si son demasiado grandes, dividirlas en varias PDBs pequeñas)
- Top Spin: max de diferents PDBs
- Torre de Hanoi con 4 astas: max de diferentes PDBs
El tiempo máximo de ejecución lo deciden ustedes según los recursos que tengan a su disposición. Para A*, no permitan que el programa utilice memoria virtual (paginación sobre disco) ya que posiblemente correrá extremadamente lento y no podrán resolver el problema (y la máquina se les "congelará").
Se entregan casos de prueba para los n-puzzles y para el Cubo de Rubik. Para los problemas restantes deben generar casos de prueba con el programa global/generator.cc que se entrega en la distribución de PSVN. Leer el programa para entenderlo y poder ejecutarlo. Se deben generar casos de prueba fáciles y difíciles.
Deben entregar su implementación de la solución junto a un informe que explique las decisiones tomadas y los resultados de sus ejecuciones.
Cualquier trabajo extra (heurísticas o algoritmos extra implementados, otros métodos de eliminación de duplicados, etc...) contará para los puntos de participación.