I1M2018: El patrón de búsqueda en espacios de estados en Haskell

En la la segunda parte de la clase de hoy de del curso Informática de 1º del Grado en Matemáticas hemos estudiado la técnica de resolución de problemas mediante búsqueda en espacios de estados.

Se comenzó analizando los árboles de búsquedas para el problema de las 4 reinas y para el problema del 8-puzzle

De este análisis se extrae el patrón de resolución de problemas mediante búsqueda en espacios de estados (EE) y sus argumentos:

  • cuál es el estado inicial,
  • cómo se calculan los sucesores de un estado y
  • cómo decidir si un estado es un estado final.

A continuación se implementa el patrón de búsqueda en espacio de estados en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.

Finalmente, se aplica el patrón para implementar las soluciones de los problemas de las N reinas y del cambio de monedas.

Los apuntes correspondientes a la clase es la 2ª sección del tema 23