{"id":6693,"date":"2019-05-24T18:28:44","date_gmt":"2019-05-24T16:28:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6693"},"modified":"2019-05-25T18:29:21","modified_gmt":"2019-05-25T16:29:21","slug":"i1m2018-el-problema-del-granjero-mediante-busqueda-en-espacio-de-estado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-el-problema-del-granjero-mediante-busqueda-en-espacio-de-estado\/","title":{"rendered":"I1M2018: El problema del granjero mediante b\u00fasqueda en espacio de estado."},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>se han resuelto ejercicios de la relaci\u00f3n 42 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-18\/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 primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticasse han resuelto ejercicios de la relaci\u00f3n 42 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":"closed","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":[320,1],"tags":[],"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\/6693"}],"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=6693"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6693\/revisions"}],"predecessor-version":[{"id":6695,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6693\/revisions\/6695"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6693"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6693"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6693"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}