I1M2015: 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.
La clase 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.
Las transparencias usadas en la clase son las páginas 11-28 del tema 23:
El código del patrón de búsqueda en espacio de estados es
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
module BusquedaEnEspaciosDeEstados (buscaEE) where import I1M.Pila -- (buscaEE 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). buscaEE:: (Eq nodo) => (nodo -> [nodo]) -- sucesores -> (nodo -> Bool) -- esFinal -> nodo -- nodo actual -> [nodo] -- soluciones buscaEE sucesores esFinal x = busca' (apila x vacia) where busca' p | esVacia p = [] | esFinal (cima p) = cima p : busca' (desapila p) | otherwise = busca' (foldr apila (desapila p) (sucesores x)) where x = cima p |
El código del problema de las N reinas 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 52 53 54 55 56 57 58 59 |
import I1M.BusquedaEnEspaciosDeEstados -- El problema de las n reinas consiste en colocar n reinas en un -- tablero cuadrado de dimensiones n por n de forma que no se encuentren -- más de una en la misma línea: horizontal, vertical o diagonal. -- Las posiciones de las reinas en el tablero se representan por su -- columna y su fila. type Columna = Int type Fila = Int -- Una solución del problema de las n reinas es una lista de -- posiciones. type SolNR = [(Columna,Fila)] -- (valida sp p) se verifica si la posición p es válida respecto de la -- solución parcial sp; es decir, la reina en la posición p no amenaza a -- ninguna de las reinas de la sp (se supone que están en distintas -- columnas). Por ejemplo, -- valida [(1,1)] (2,2) == False -- valida [(1,1)] (2,3) == True valida :: SolNR -> (Columna,Fila) -> Bool valida solp (c,r) = and [test s | s <- solp] where test (c',r') = and [c'+r'/=c+r,c'-r'/=c-r,r'/=r] -- Los nodos del problema de las n reinas son ternas formadas por la -- columna de la siguiente reina, el número de columnas del -- tablero y la solución parcial de las reinas colocadas anteriormente. type NodoNR = (Columna,Columna,SolNR) -- (sucesoresNR e) es la lista de los sucesores del estado e en el -- problema de las n reinas. Por ejemplo, -- ghci> sucesoresNR (0,4,[]) -- [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] sucesoresNR :: NodoNR -> [NodoNR] sucesoresNR (c,n,solp) = [(c+1,n,solp++[(c,r)]) | r <- [1..n] , valida solp (c,r)] -- (esFinalNR e) se verifica si e es un estado final del problema de las -- n reinas. esFinalNR :: NodoNR -> Bool esFinalNR (c,n,solp) = c > n -- (buscaEE_NR n) es la primera solución del problema de las n reinas, -- por búsqueda en espacio de estados. Por ejemplo, -- ghci> buscaEE_NR 8 -- [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)] buscaEE_NR :: Columna -> SolNR buscaEE_NR n = s where ((_,_,s):_) = buscaEE sucesoresNR esFinalNR (1,n,[]) -- (nSolucionesNR n) es el número de soluciones del problema de las n -- reinas, por búsqueda en espacio de estados. Por ejemplo, -- nSolucionesNR 8 == 92 nSolucionesNR :: Columna -> Int nSolucionesNR n = length (buscaEE sucesoresNR esFinalNR (1,n,[])) |
El código del problema de la mochila 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 52 53 54 55 56 57 58 59 60 61 62 63 |
import I1M.BusquedaEnEspaciosDeEstados import Data.List (sort) -- Se tiene una mochila de capacidad de peso p y una lista de n objetos -- para colocar en la mochila. Cada objeto i tiene un peso w_i y un -- valor v_i. Considerando la posibilidad de colocar el mismo objeto -- varias veces en la mochila, el problema consiste en determinar la -- forma de colocar los objetos en la mochila sin sobrepasar la -- capacidad de la mochila colocando el máximmo valor posible. -- Los pesos son número enteros type Peso = Int -- Los valores son números reales. type Valor = Float -- Los objetos son pares formado por un peso y un valor type Objeto = (Peso,Valor) -- Una solución del problema de la mochila es una lista de objetos. type SolMoch = [Objeto] -- Los estados del problema de la mochila son 5-tupla de la forma -- (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el -- peso de los objetos colocados, l es el límite de la capacidad de la -- mochila, o es la lista de los objetos colocados (ordenados de forma -- creciente según sus pesos) y s es la solución parcial. type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) -- (sucesoresMoch e) es la lista de los sucesores del estado e en el -- problema de la mochila. sucesoresMoch :: NodoMoch -> [NodoMoch] sucesoresMoch (v,p,limite,objetos,solp) = [( v+v', p+p', limite, [o | o@(p'',_) <- objetos,(p''>=p')], (p',v'):solp ) | (p',v') <- objetos, p+p' <= limite] -- (esObjetivoMoch e) se verifica si e es un estado final el problema de -- la mochila. esObjetivoMoch :: NodoMoch -> Bool esObjetivoMoch (_,p,limite,((p',_):_),_) = p+p'>limite -- (buscaEE_Mochila os l) es la solución del problema de la mochila para -- la lista de objetos os y el límite de capacidad l. Por ejemplo, -- > buscaEE_Mochila [(2,3),(3,5),(4,6),(5,10)] 8 -- ([(5,10.0),(3,5.0)],15.0) -- > buscaEE_Mochila [(2,3),(3,5),(5,6)] 10 -- ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) -- > buscaEE_Mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 -- ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) -- > buscaEE_Mochila [(2,2.8),(3,4.4),(5,6.1)] 10 -- ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) buscaEE_Mochila :: [Objeto] -> Peso -> (SolMoch,Valor) buscaEE_Mochila objetos limite = (sol,v) where (v,_,_,_,sol) = maximum (buscaEE sucesoresMoch esObjetivoMoch |