5.27.4.4 Búsqueda Heurística y CSP (6 horas) [Habilidades AG-C08,AG-C09]

Referencias Bibliográficas: [Russell and Norvig, 2020,Luger, 2008]

Temas

1. Búsqueda en grafo heurística para resolución de problemas:
   1. Construcción heurística y admisibilidad
   2. Ascenso de colinas
   3. Mínimos locales y el paisaje de búsqueda:
      1. Soluciones locales versus globales
   4. Búsqueda primero el mejor voraz
   5. Búsqueda A*
2. Búsqueda en haz
3. Implementación de la búsqueda A*
4. Satisfacción de restricciones

5. Variaciones de A* (IDA*, SMA*, RBFS)

Aprendizaje esperado (Learning Outcomes)

1. Seleccionar e implementar un algoritmo de búsqueda informada apropiado para un problema después de diseñar una función heurística útil (por ejemplo, un robot navegando en un mundo de cuadrícula 2D) [Aplicar]
2. Evaluar si una heurística para un problema dado es admisible/puede garantizar una solución óptima [Evaluar]
3. Diseñar e implementar búsqueda A*/en haz para resolver un problema, y compararla con otros algoritmos de búsqueda en términos del costo de la solución, número de nodos expandidos, etc [Aplicar]
4. Comparar y contrastar varias búsquedas heurísticas con respecto a la aplicabilidad a un problema dado [Evaluar]
5. Modelar un rompecabezas lógico o Sudoku como un problema de satisfacción de restricciones, resolverlo con búsqueda con retroceso y determinar cuánto la consistencia de arcos puede reducir el espacio de búsqueda [Aplicar]