{"id":4872,"date":"2015-04-20T18:51:29","date_gmt":"2015-04-20T16:51:29","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4872"},"modified":"2015-04-22T08:52:43","modified_gmt":"2015-04-22T06:52:43","slug":"i1m2014-el-problema-del-granjero-mediante-busqueda-en-espacio-de-estado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-problema-del-granjero-mediante-busqueda-en-espacio-de-estado\/","title":{"rendered":"I1M2014: El problema del granjero mediante b\u00fasqueda en espacio de estado."},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 30 sobre el problema del granjero mediante b\u00fasqueda en espacio de estado.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- Un granjero est\u00e1 parado en un lado del r\u00edo y con \u00e9l tiene un lobo,\n-- una cabra y una repollo. En el r\u00edo hay un barco peque\u00f1o. El granjero\n-- desea cruzar el r\u00edo con sus tres posesiones. No hay puentes y en el\n-- barco hay solamente sitio para el granjero y un art\u00edculo. Si deja \n-- la cabra con la repollo sola en un lado del r\u00edo la cabra comer\u00e1 la\n-- repollo. Si deja el lobo y la cabra en un lado, el lobo se comer\u00e1 a\n-- la cabra. \u00bfC\u00f3mo puede cruzar el granjero el r\u00edo con los tres\n-- art\u00edculos, sin que ninguno se coma al otro?\n-- \n-- El objetivo de esta relaci\u00f3n de ejercicios es resolver el problema\n-- del granjero mediante b\u00fasqueda en espacio de estados, utilizando las\n-- implementaciones estudiadas en el tema 23 que se pueden descargar desde \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/codigos\n--\n-- Las transparencias del tema 23 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-23.pdf\n\n-- ---------------------------------------------------------------------\n-- Importaciones                                                      --\n-- ---------------------------------------------------------------------\n\nimport I1M.BusquedaEnEspaciosDeEstados -- Est\u00e1 en http:\/\/bit.ly\/1AKmUQB\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir el tipo Orilla con dos constructores I y D que\n-- representan las orillas izquierda y derecha, respectivamente.\n-- ---------------------------------------------------------------------\n\ndata Orilla = I | D\n              deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir el tipo Estado como abreviatura de una tupla que\n-- representan en qu\u00e9 orilla se encuentra cada uno de los elementos\n-- (granjero, lobo, cabra, repollo). Por ejemplo, (I,D,D,I) representa\n-- que el granjero est\u00e1 en la izquierda, que el lobo est\u00e1 en la derecha,\n-- que la cabra est\u00e1 en la derecha y el repollo est\u00e1 en la izquierda.\n-- ---------------------------------------------------------------------\n\ntype Estado = (Orilla,Orilla,Orilla,Orilla)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir \n--    inicial:: Estado\n-- tal que inicial representa el estado en el que todos est\u00e1n en la\n-- orilla izquierda.\n-- ---------------------------------------------------------------------\n\ninicial:: Estado\ninicial = (I,I,I,I)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir \n--    final:: Estado\n-- tal que final representa el estado en el que todos est\u00e1n en la\n-- orilla derecha.\n-- ---------------------------------------------------------------------\n\nfinal:: Estado\nfinal = (D,D,D,D)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--   seguro :: Estado -> Bool\n-- tal que (seguro e) se verifica si el estado e es seguro; es decir,\n-- que no puede estar en una orilla el lobo con la cabra sin el granjero\n-- ni la cabra con el repollo sin el granjero. Por ejemplo,\n--    seguro (I,D,D,I)  ==  False\n--    seguro (D,D,D,I)  ==  True\n--    seguro (D,D,I,I)  ==  False\n--    seguro (I,D,I,I)  ==  True\n-- ---------------------------------------------------------------------\n\nseguro :: Estado -> Bool\nseguro (g,l,c,r) \n       | l == c    = g == l\n       | c == r    = g == c\n       | otherwise = True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n \n--    opuesta :: Orilla -> Orilla\n-- tal que (opuesta x) es la opuesta de la orilla x. Por ejemplo\n--    opuesta I = D \n-- ---------------------------------------------------------------------\n\nopuesta :: Orilla -> Orilla\nopuesta I = D\nopuesta D = I\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    sucesoresE :: Estado -> [Estado]\n-- tal que (sucesoresE e) es la lista de los sucesores seguros del\n-- estado e. Por ejemplo,\n--    sucesoresE (D,I,D,I)  ==  [(I,I,D,I),(I,I,I,I)]\n-- ---------------------------------------------------------------------\n\nsucesoresE :: Estado -> [Estado]\nsucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)] \n    where m1 (g,l,c,r) = (opuesta g, l, c, r)\n          m2 (g,l,c,r) = (opuesta g, opuesta l, c, r)\n          m3 (g,l,c,r) = (opuesta g, l, opuesta c, r)\n          m4 (g,l,c,r) = (opuesta g, l, c, opuesta r)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Los nodos del espacio de b\u00fasqueda son lista de estados \n--    [e_n, ..., e_2, e_1]\n-- donde e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un\n-- sucesor de e_(i-1). \n-- \n-- Definir el tipo de datos NodoRio para representar los nodos del\n-- espacio de b\u00fasqueda. Por ejemplo, \n--    ghci> :type (Nodo [(I,I,D,I),(I,I,I,I)])\n--    (Nodo [(I,I,D,I),(I,I,I,I)]) :: NodoRio\n-- ---------------------------------------------------------------------\n\ndata NodoRio = Nodo [Estado] \n               deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    sucesoresN :: NodoRio -> [NodoRio]\n-- tal que (sucesoresN n) es la lista de los sucesores del nodo n. Por\n-- ejemplo, \n--    ghci> sucesoresN (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)])\n--    [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)],\n--     Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]]\n-- ---------------------------------------------------------------------\n\nsucesoresN :: NodoRio -> [NodoRio]\nsucesoresN (Nodo (n@(e:es))) =\n    [Nodo (e':n) | e' <- sucesoresE e, notElem e' es]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    esFinal:: NodoRio -> Bool\n-- tal que (esFinal n) se verifica si n es un nodo final; es decir, su\n-- primer elemento es el estado final. Por ejemplo,\n--    esFinal (Nodo [(D,D,D,D),(I,I,I,I)])  ==  True\n--    esFinal (Nodo [(I,I,D,I),(I,I,I,I)])  ==  False\n-- ---------------------------------------------------------------------\n\nesFinal:: NodoRio -> Bool\nesFinal (Nodo (n:_)) = n == final\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    granjeroEE :: [NodoRio]\n-- tal que granjeroEE son las soluciones del problema del granjero\n-- mediante el patr\u00f3n de b\u00fasqueda en espacio de estados. Por ejemplo,\n--    ghci> head granjeroEE\n--    Nodo [(D,D,D,D),(I,D,I,D),(D,D,I,D),(I,D,I,I),\n--          (D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)]\n-- ---------------------------------------------------------------------\n\ngranjeroEE :: [NodoRio]\ngranjeroEE = buscaEE sucesoresN \n                     esFinal \n                     (Nodo [inicial])\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 30 sobre el problema del granjero mediante b\u00fasqueda en espacio de estado. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[238],"tags":[244,270,305],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4872"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=4872"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4872\/revisions"}],"predecessor-version":[{"id":4873,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4872\/revisions\/4873"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4872"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4872"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4872"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}