I1M2019: El patrón de búsqueda en escalada en Haskell
En 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 escalada en espacios de estados.
En primer lugar se explicó la idea de la búsqueda en escalada y cómo, usando dicha idea, se puede transformar el patrón de búsqueda por primero el mejor en el de búsqueda en escalada. Finalmente, se aplicó el patrón de búsqueda en escalada a la resolución del problema del cambio de monedas.
La clase se ha dado mediante videoconferencia y el correspondiente vídeo es
Los apuntes correspondientes a la clase es la sección 3 del tema 23
Una versión interactiva de los apuntes en IHaskell se encuentra aquí.
El código del problema del cambio de monedas usado en la clase es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import I1M.BusquedaEnEscalada -- El problema del cambio de monedas consiste en determinar cómo -- conseguir una cantidad usando el menor número de monedas disponibles. -- Las monedas son números enteros. type Moneda = Int -- ejMonedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. ejMonedas :: [Moneda] ejMonedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Solucion = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type Estado = (Int, [Moneda]) -- (sucesores ms e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- λ> sucesores ejMonedas (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesores :: [Moneda] -> Estado -> [Estado] sucesores monedas (r,ms) = [(r - m, m : ms) | m <- monedas, r - m >= 0] -- (esFinal e) se verifica si e es un estado final del problema -- de las monedas. esFinal :: Estado -> Bool esFinal (r, _) = r == 0 -- (cambio n) es la solución del problema de las monedas por búsqueda en -- escalada. Por ejemplo, -- λ> cambio ejMonedas 199 -- Just [2,2,5,20,20,50,100] -- λ> cambio [1,5,10,20,50,100] 199 -- Just [1,1,1,1,5,20,20,50,100] -- λ> cambio [5,10,50,100] 199 -- Nothing cambio :: [Moneda] -> Int -> Maybe Solucion cambio ms n | null sols = Nothing | otherwise = Just (snd (head sols)) where sols = buscaEscalada (sucesores ms) esFinal (n,[]) |