I1M2014: El patrón de búsqueda en escalada en Haskell
En la primera parte de la clase de hoy 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 primer lugar, se explicó el patrón de búsqueda en escalada. A continuación, se aplicó el patrón para resolver el problema problema del cambio de monedas y al cálculo del árbol de expansión mínimo por escalada mediante el algoritmo de Prim.
Las transparencias usadas en la clase son las páginas 40-52 del tema 23:
El código del patrón de búsqueda en escalada 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 |
module BusquedaEnEscalada (buscaEscalada) where -- --------------------------------------------------------------------- -- Importaciones -- -- --------------------------------------------------------------------- -- Nota: Hay que elegir una implementación de las colas de prioridad y -- otra de grafos. -- Implementaciones de colas de prioridad: import I1M.ColaDePrioridad -- import ColaDePrioridadConListas -- import ColaDePrioridadConMonticulos -- --------------------------------------------------------------------- -- El patrón de búsqueda en escalada -- -- --------------------------------------------------------------------- -- (buscaEscalada s o e) es la lista de soluciones del problema de espacio de -- estado definido por la función sucesores (s), el objetivo (o) y el -- estado inicial (e), obtenidas buscando por escalada. buscaEscalada :: Ord nodo => (nodo -> [nodo]) -- sucesores -> (nodo -> Bool) -- es final -> nodo -- nodo actual -> [nodo] -- soluciones buscaEscalada sucesores esFinal x = (busca' (inserta x vacia) ) where busca' c | esVacia c = [] | esFinal (primero c) = [primero c] | otherwise = busca' (foldr inserta vacia (sucesores x)) where x = primero c |
El código del problema del cambio de monedas 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 |
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 -- monedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. monedas :: [Moneda] monedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Soluciones = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type NodoMonedas = (Int, [Moneda]) -- (sucesoresMonedas e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- ghci> sucesoresMonedas (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesoresMonedas :: NodoMonedas -> [NodoMonedas] sucesoresMonedas (r,p) = [(r-c,c:p) | c <- monedas, r-c >= 0] -- (esFinalMonedas e) se verifica si e es un estado final del problema -- de las monedas. esFinalMonedas :: NodoMonedas -> Bool esFinalMonedas (v,_) = v==0 -- (cambio n) es la solución del problema de las monedas por búsqueda en -- escalada. Por ejemplo, -- cambio 199 == [2,2,5,20,20,50,100] cambio :: Int -> Soluciones cambio n = snd (head (buscaEscalada sucesoresMonedas esFinalMonedas (n,[]))) |
El código para el cálculo de árboles de expansión mínimos 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 48 49 50 51 |
import I1M.BusquedaEnEscalada -- Implementaciones del TAD grafo. import I1M.Grafo -- import GrafoConVectorDeAdyacencia -- import GrafoConMatrizDeAdyacencia import Data.Array import Data.List g1 :: Grafo Int Int g1 = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] -- Una arista esta formada dos nodos junto con su peso. type Arista a b = (a,a,b) -- Un nodo (NodoAEM (p,t,r,aem)) está formado por el peso p de la última -- arista añadida el árbol de expansión mínimo (aem), la lista t -- de nodos del grafo que están en el aem, la lista r de nodos del -- grafo que no están en el aem y el aem. type NodoAEM a b = (b,[a],[a],[Arista a b]) -- (sucesoresAEM g n) es la lista de los sucesores del nodo n en el -- grafo g. Por ejemplo, -- ghci> sucesoresAEM g1 (0,[1],[2..5],[]) -- [(12,[2,1],[3,4,5],[(1,2,12)]), -- (34,[3,1],[2,4,5],[(1,3,34)]), -- (78,[5,1],[2,3,4],[(1,5,78)])] sucesoresAEM :: (Ix a,Num b) => (Grafo a b) -> (NodoAEM a b) -> [(NodoAEM a b)] sucesoresAEM g (_,t,r,aem) = [(peso x y g, (y:t), delete y r, (x,y,peso x y g):aem) | x <- t , y <- r, aristaEn g (x,y)] -- (esFinalAEM n) se verifica si n es un estado final; es decir, si no -- queda ningún elemento en la lista de nodos sin colocar en el árbol de -- expansión mínimo. esFinalAEM (_,_,[],_) = True esFinalAEM _ = False -- (prim g) es el árbol de expansión mínimo del grafo g, por el -- algoritmo de Prim como búsqueda en escalada. Por ejemplo, -- prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] prim g = sol where [(_,_,_,sol)] = buscaEscalada (sucesoresAEM g) esFinalAEM (0,[n],ns,[]) (n:ns) = nodos g |