I1M2014: El problema del granjero mediante búsqueda en espacio de estado.
En 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 30 sobre el problema del granjero mediante búsqueda en espacio de estado.
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 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- Un granjero está parado en un lado del río y con él tiene un lobo, -- una cabra y una repollo. En el río hay un barco pequeño. El granjero -- desea cruzar el río con sus tres posesiones. No hay puentes y en el -- barco hay solamente sitio para el granjero y un artículo. Si deja -- la cabra con la repollo sola en un lado del río la cabra comerá la -- repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a -- la cabra. ¿Cómo puede cruzar el granjero el río con los tres -- artículos, sin que ninguno se coma al otro? -- -- El objetivo de esta relación de ejercicios es resolver el problema -- del granjero 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 -- --------------------------------------------------------------------- -- Importaciones -- -- --------------------------------------------------------------------- import I1M.BusquedaEnEspaciosDeEstados -- Está en http://bit.ly/1AKmUQB -- --------------------------------------------------------------------- -- Ejercicio 1. Definir el tipo Orilla con dos constructores I y D que -- representan las orillas izquierda y derecha, respectivamente. -- --------------------------------------------------------------------- data Orilla = I | D deriving (Eq, Show) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir el tipo Estado como abreviatura de una tupla que -- representan en qué orilla se encuentra cada uno de los elementos -- (granjero, lobo, cabra, repollo). Por ejemplo, (I,D,D,I) representa -- que el granjero está en la izquierda, que el lobo está en la derecha, -- que la cabra está en la derecha y el repollo está en la izquierda. -- --------------------------------------------------------------------- type Estado = (Orilla,Orilla,Orilla,Orilla) -- --------------------------------------------------------------------- -- Ejercicio 3. Definir -- inicial:: Estado -- tal que inicial representa el estado en el que todos están en la -- orilla izquierda. -- --------------------------------------------------------------------- inicial:: Estado inicial = (I,I,I,I) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir -- final:: Estado -- tal que final representa el estado en el que todos están en la -- orilla derecha. -- --------------------------------------------------------------------- final:: Estado final = (D,D,D,D) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- seguro :: Estado -> Bool -- tal que (seguro e) se verifica si el estado e es seguro; es decir, -- que no puede estar en una orilla el lobo con la cabra sin el granjero -- ni la cabra con el repollo sin el granjero. Por ejemplo, -- seguro (I,D,D,I) == False -- seguro (D,D,D,I) == True -- seguro (D,D,I,I) == False -- seguro (I,D,I,I) == True -- --------------------------------------------------------------------- seguro :: Estado -> Bool seguro (g,l,c,r) | l == c = g == l | c == r = g == c | otherwise = True -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- opuesta :: Orilla -> Orilla -- tal que (opuesta x) es la opuesta de la orilla x. Por ejemplo -- opuesta I = D -- --------------------------------------------------------------------- opuesta :: Orilla -> Orilla opuesta I = D opuesta D = I -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- sucesoresE :: Estado -> [Estado] -- tal que (sucesoresE e) es la lista de los sucesores seguros del -- estado e. Por ejemplo, -- sucesoresE (D,I,D,I) == [(I,I,D,I),(I,I,I,I)] -- --------------------------------------------------------------------- sucesoresE :: Estado -> [Estado] sucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)] where m1 (g,l,c,r) = (opuesta g, l, c, r) m2 (g,l,c,r) = (opuesta g, opuesta l, c, r) m3 (g,l,c,r) = (opuesta g, l, opuesta c, r) m4 (g,l,c,r) = (opuesta g, l, c, opuesta r) -- --------------------------------------------------------------------- -- Ejercicio 8. Los nodos del espacio de búsqueda son lista de estados -- [e_n, ..., e_2, e_1] -- donde e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un -- sucesor de e_(i-1). -- -- Definir el tipo de datos NodoRio para representar los nodos del -- espacio de búsqueda. Por ejemplo, -- ghci> :type (Nodo [(I,I,D,I),(I,I,I,I)]) -- (Nodo [(I,I,D,I),(I,I,I,I)]) :: NodoRio -- --------------------------------------------------------------------- data NodoRio = Nodo [Estado] deriving (Eq, Show) -- --------------------------------------------------------------------- -- Ejercicio 9. Definir la función -- sucesoresN :: NodoRio -> [NodoRio] -- tal que (sucesoresN n) es la lista de los sucesores del nodo n. Por -- ejemplo, -- ghci> sucesoresN (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)]) -- [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)], -- Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]] -- --------------------------------------------------------------------- sucesoresN :: NodoRio -> [NodoRio] sucesoresN (Nodo (n@(e:es))) = [Nodo (e':n) | e' <- sucesoresE e, notElem e' es] -- --------------------------------------------------------------------- -- Ejercicio 10. Definir la función -- esFinal:: NodoRio -> Bool -- tal que (esFinal n) se verifica si n es un nodo final; es decir, su -- primer elemento es el estado final. Por ejemplo, -- esFinal (Nodo [(D,D,D,D),(I,I,I,I)]) == True -- esFinal (Nodo [(I,I,D,I),(I,I,I,I)]) == False -- --------------------------------------------------------------------- esFinal:: NodoRio -> Bool esFinal (Nodo (n:_)) = n == final -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- granjeroEE :: [NodoRio] -- tal que granjeroEE son las soluciones del problema del granjero -- mediante el patrón de búsqueda en espacio de estados. Por ejemplo, -- ghci> head granjeroEE -- Nodo [(D,D,D,D),(I,D,I,D),(D,D,I,D),(I,D,I,I), -- (D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)] -- --------------------------------------------------------------------- granjeroEE :: [NodoRio] granjeroEE = buscaEE sucesoresN esFinal (Nodo [inicial]) |