I1M2018

En la la primera 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 con heurísticas.

En primer lugar se estudió la búsqueda por primero el mejor, se implementó el patrón de búsqueda por primero el mejor y se aplicó el patrón para resolver el problema del 8 puzzle.

En segundó lugar se estudió la búsqueda en escalada, se implementó el patrón de búsqueda en escalada y se aplicó el patrón para resolver el el problema del cambio de monedas por escalada.

Finalmente, se estudió el algoritmo de Prim del árbol de expansión mínimo como un caso particular de búsqueda en escalada.

Los apuntes correspondientes a la clase son las secciones 3 y 4 del tema 23

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticasse han resuelto ejercicios de la relación 43 sobre resolución de problemas en espacios de estados. Los problemas resueltos son el del dominó, el de la suma cero y el de las jarras.

Los ejercicios y su solución se muestran a continuación
Read More “I1M2018: Resolución de problemas mediante búsqueda en espacios de estados”

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

En la primera parte de la clase de hoy del curso de 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.

En primer lugar se ha visto cómo se describen los problemas mediante el estado inicial, los sucesores de los estados y los estados finales. Aplicándola a los problemas del 8-puzzle, del granjero, de las jarras y del viaje.

A continuación se han explicado los procedimientos básicos de búsquedas: en anchrura, en profundidad, en profundidad acotada y en profundidad iterativa.

Los apuntes correspondientes son las 53 primeras transparencias del tema 23a.