I1M2014: Resolución de problemas mediante búsqueda en espacios de estados en Haskell
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la relación 34 sobre problemas en espacios de estados.
Los ejercicios y su solución se muestran a continuación
|
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- El objetivo de esta relación de ejercicios es resolver problemas -- mediante búsqueda en espacio de estados, utilizando las -- implementaciones estudiadas en el tema 23 que se pueden descargar -- desde -- http://www.cs.us.es/~jalonso/cursos/i1m-14/codigos -- -- Las transparencias del tema 23 se encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-14/temas/tema-23.pdf -- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import I1M.BusquedaEnEspaciosDeEstados import Data.List (delete, nub, sort) -- --------------------------------------------------------------------- -- Ejercicio 1. Las fichas del dominó se pueden representar por pares de -- números enteros. El problema del dominó consiste en colocar todas las -- fichas de una lista dada de forma que el segundo número de cada ficha -- coincida con el primero de la siguiente. -- -- Definir, mediante búsqueda en espacio de estados, la función -- domino :: [(Int,Int)] -> [[(Int,Int)]] -- tal que (domino fs) es la lista de las soluciones del problema del -- dominó correspondiente a las fichas fs. Por ejemplo, -- ghci> domino [(1,2),(2,3),(1,4)] -- [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] -- ghci> domino [(1,2),(1,1),(1,4)] -- [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] -- ghci> domino [(1,2),(3,4),(2,3)] -- [[(1,2),(2,3),(3,4)]] -- ghci> domino [(1,2),(2,3),(5,4)] -- [] -- --------------------------------------------------------------------- type Ficha = (Int,Int) -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type EstadoDomino = ([Ficha],[Ficha]) inicialDomino :: [Ficha] -> EstadoDomino inicialDomino fs = (fs,[]) esFinalDomino :: EstadoDomino -> Bool esFinalDomino (fs,_) = null fs sucesoresDomino :: EstadoDomino -> [EstadoDomino] sucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs] sucesoresDomino (fs,n@((x,y):qs)) = [(delete (u,v) fs,(u,v):n) | (u,v) <- rs, u /= v, v == x] ++ [(delete (u,v) fs,(v,u):n) | (u,v) <- rs, u /= v, u == x] ++ [(delete (u,v) fs,(u,v):n) | (u,v) <- rs, u == v, u == x] where rs = [(u,v) | (u,v) <- fs, (u,v) `notElem` n, (v,u) `notElem` n] solucionesDomino :: [Ficha] -> [EstadoDomino] solucionesDomino ps = buscaEE sucesoresDomino esFinalDomino (inicialDomino ps) domino :: [(Int,Int)] -> [[(Int,Int)]] domino ps = map snd (solucionesDomino ps) -- --------------------------------------------------------------------- -- Ejercicio 2. El problema de suma cero consiste en, dado el conjunto -- de números enteros, encontrar sus subconjuntos no vacío cuyos -- elementos sumen cero. -- -- Definir, mediante búsqueda en espacio de estados, la función -- suma0 :: [Int] -> [[Int]] -- tal que (suma0 ns) es la lista de las soluciones del problema se suma -- cero para ns. Por ejemplo, -- ghci> suma0 [-7,-3,-2,5,8] -- [[-3,-2,5]] -- ghci> suma0 [-7,-3,-2,5,8,-1] -- [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] -- ghci> suma0 [-7,-3,1,5,8] -- [] -- --------------------------------------------------------------------- -- Los estados son ternas formadas por los números seleccionados, su -- suma y los restantes números. type EstadoSuma0 = ([Int], Int, [Int]) inicialSuma0 :: [Int] -> EstadoSuma0 inicialSuma0 ns = ([],0,ns) esFinalSuma0 :: EstadoSuma0 -> Bool esFinalSuma0 (xs,s,_) = not (null xs) && s == 0 sucesoresSuma0 :: EstadoSuma0 -> [EstadoSuma0] sucesoresSuma0 (xs,s,ns) = [(n:xs, n+s, delete n ns) | n <- ns] solucionesSuma0 :: [Int] -> [EstadoSuma0] solucionesSuma0 ns = buscaEE sucesoresSuma0 esFinalSuma0 (inicialSuma0 ns) suma0 :: [Int] -> [[Int]] suma0 ns = nub [sort xs | (xs,_,_) <- solucionesSuma0 ns] -- --------------------------------------------------------------------- -- Ejercicio 3. Se tienen dos jarras, una de 4 litros de capacidad y -- otra de 3. Ninguna de ellas tiene marcas de medición. Se tiene una -- bomba que permite llenar las jarras de agua. El problema de las -- jarras consiste en determinar cómo se puede lograr tener exactamente -- 2 litros de agua en la jarra de 4 litros de capacidad. -- -- Definir, mediante búsqueda en espacio de estados, la función -- jarras :: [[(Int,Int)]] -- tal que su valor es la lista de las soluciones del problema de las -- jarras, Por ejemplo, -- ghci> jarras !! 4 -- [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] -- La interpretación de primera solución es: -- (0,0) se inicia con las dos jarras vacías, -- (4,0) se llena la jarra de 4 con el grifo, -- (1,3) se llena la de 3 con la de 4, -- (1,0) se vacía la de 3, -- (0,1) se pasa el contenido de la primera a la segunda, -- (4,1) se llena la primera con el grifo, -- (2,3) se llena la segunda con la primera. -- --------------------------------------------------------------------- -- Un estado es una lista de dos números. El primero es el contenido de -- la jarra de 4 litros y el segundo el de la de 3 litros. type EstadoJarras = (Int,Int) inicialJarras :: EstadoJarras inicialJarras = (0,0) esFinalJarras :: EstadoJarras -> Bool esFinalJarras (x,_) = x == 2 sucesoresEjarras :: EstadoJarras -> [EstadoJarras] sucesoresEjarras (x,y) = [(4,y) | x < 4] ++ [(x,3) | y < 3] ++ [(0,y) | x > 0] ++ [(x,0) | y > 0] ++ [(4,y-(4-x)) | x < 4, y > 0, x + y > 4] ++ [(x-(3-y),3) | x > 0, y < 3, x + y > 3] ++ [(x+y,0) | y > 0, x + y <= 4] ++ [(0,x+y) | x > 0, x + y <= 3] -- Los nodos son las soluciones parciales type NodoJarras = [EstadoJarras] inicialNjarras :: NodoJarras inicialNjarras = [inicialJarras] esFinalNjarras :: NodoJarras -> Bool esFinalNjarras (e:_) = esFinalJarras e sucesoresNjarras :: NodoJarras -> [NodoJarras] sucesoresNjarras n@(e:es) = [e':n | e' <- sucesoresEjarras e, e' `notElem` n] solucionesJarras :: [NodoJarras] solucionesJarras = buscaEE sucesoresNjarras esFinalNjarras inicialNjarras jarras :: [[(Int,Int)]] jarras = map reverse solucionesJarras |