{"id":6696,"date":"2019-05-24T18:37:33","date_gmt":"2019-05-24T16:37:33","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6696"},"modified":"2019-05-25T18:38:21","modified_gmt":"2019-05-25T16:38:21","slug":"i1m2018-resolucion-de-problemas-mediante-busqueda-en-espacios-de-estados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-resolucion-de-problemas-mediante-busqueda-en-espacios-de-estados\/","title":{"rendered":"I1M2018: Resoluci\u00f3n de problemas mediante b\u00fasqueda en espacios de estados"},"content":{"rendered":"<p>En la segunda 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 43 sobre resoluci\u00f3n de problemas en espacios de estados. Los problemas resueltos son el del domin\u00f3, el de la suma cero y el de las jarras.<\/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-- El objetivo de esta relaci\u00f3n de ejercicios es resolver problemas\n-- mediante b\u00fasqueda en espacio de estados, utilizando las\n-- implementaciones estudiadas en el tema 23 que se pueden descargar\n-- desde  \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\/codigosDeTemas.php\n--\n-- Las transparencias del tema 23 se encuentran en\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\/temas\/tema-23.pdf\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport I1M.BusquedaEnEspaciosDeEstados\nimport Data.List\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Las fichas del domin\u00f3 se pueden representar por pares de\n-- n\u00fameros enteros. El problema del domin\u00f3 consiste en colocar todas las\n-- fichas de una lista dada de forma que el segundo n\u00famero de cada ficha\n-- coincida con el primero de la siguiente.\n--\n-- Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n \n--    domino :: [(Int,Int)] -> [[(Int,Int)]]\n-- tal que (domino fs) es la lista de las soluciones del problema del\n-- domin\u00f3 correspondiente a las fichas fs. Por ejemplo,\n--    ghci> domino [(1,2),(2,3),(1,4)]\n--    [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]\n--    ghci> domino [(1,2),(1,1),(1,4)]\n--    [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]\n--    ghci> domino [(1,2),(3,4),(2,3)]\n--    [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]]\n--    ghci> domino [(1,2),(2,3),(5,4)]\n--    []\n-- ---------------------------------------------------------------------\n\n-- Las fichas son pares de n\u00fameros enteros.\ntype Ficha  = (Int,Int)\n\n-- Un problema est\u00e1 definido por la lista de fichas que hay que colocar\ntype Problema = [Ficha]\n\n-- Los estados son los pares formados por la listas sin colocar y las\n-- colocadas. \ntype Estado = ([Ficha],[Ficha])\n\n-- (inicial p) es el estado inicial del problema p.\ninicial :: Problema -> Estado\ninicial p = (p,[])\n\n-- (es final e) se verifica si e es un estado final.\nesFinal :: Estado -> Bool\nesFinal (fs,_) = null fs \n\nsucesores :: Estado -> [Estado]\nsucesores (fs,[]) =\n  [(delete (a,b) fs, [(a,b)]) | (a,b) <- fs, a \/= b] ++\n  [(delete (a,b) fs, [(b,a)]) | (a,b) <- fs]\nsucesores (fs,n@((x,y):qs)) =\n  [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u \/= v, v == x] ++\n  [(delete (u,v) fs,(v,u):n) | (u,v) <- fs, u \/= v, u == x] ++\n  [(delete (u,v) fs,(u,v):n) | (u,v) <- fs, u == v, u == x] \n\nsoluciones :: Problema -> [Estado]\nsoluciones ps = buscaEE sucesores\n                        esFinal         \n                        (inicial ps)\n\ndomino :: Problema -> [[Ficha]]\ndomino ps = map snd (soluciones ps)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. El problema de suma cero consiste en, dado el conjunto\n-- de n\u00fameros enteros, encontrar sus subconjuntos no vac\u00edo cuyos\n-- elementos sumen cero. \n-- \n-- Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n \n--    suma0 :: [Int] -> [[Int]]\n-- tal que (suma0 ns) es la lista de las soluciones del problema de suma\n-- cero para ns. Por ejemplo,\n--    ghci> suma0 [-7,-3,-2,5,8]\n--    [[-3,-2,5]]\n--    ghci> suma0 [-7,-3,-2,5,8,-1]\n--    [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n--    ghci> suma0 [-7,-3,1,5,8]\n--    []\n-- ---------------------------------------------------------------------\n\n\n-- Los estados son ternas formadas por los n\u00fameros seleccionados, su\n-- suma y los restantes n\u00fameros.\ntype EstadoSuma0 = ([Int], Int, [Int])\n\ninicialSuma0 :: [Int] -> EstadoSuma0\ninicialSuma0 ns = ([],0,ns)\n\nesFinalSuma0 :: EstadoSuma0 -> Bool\nesFinalSuma0 (xs,s,_) = not (null xs) && s == 0\n\nsucesoresSuma0 :: EstadoSuma0 -> [EstadoSuma0]\nsucesoresSuma0 (xs,s,ns) = [(n:xs, n+s, delete n ns) | n <- ns]\n\nsolucionesSuma0 :: [Int] -> [EstadoSuma0]\nsolucionesSuma0 ns = buscaEE sucesoresSuma0\n                             esFinalSuma0\n                             (inicialSuma0 ns)\n\nsuma0 :: [Int] -> [[Int]]\nsuma0 ns = nub [sort xs | (xs,_,_) <- solucionesSuma0 ns]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Se tienen dos jarras, una de 4 litros de capacidad y\n-- otra de 3. Ninguna de ellas tiene marcas de medici\u00f3n. Se tiene una\n-- bomba que permite llenar las jarras de agua. El problema de las\n-- jarras consiste en determinar c\u00f3mo se puede lograr tener exactamente\n-- 2 litros de agua en la jarra de 4 litros de capacidad. \n--\n-- Definir, mediante b\u00fasqueda en espacio de estados, la funci\u00f3n \n--    jarras :: [[(Int,Int)]]\n-- tal que su valor es la lista de las soluciones del problema de las\n-- jarras, Por ejemplo,\n--    ghci> jarras !! 4\n--    [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]\n-- La interpretaci\u00f3n de la soluci\u00f3n es: \n--    (0,0) se inicia con las dos jarras vac\u00edas,\n--    (4,0) se llena la jarra de 4 con el grifo,\n--    (1,3) se llena la de 3 con la de 4,\n--    (1,0) se vac\u00eda la de 3,\n--    (0,1) se pasa el contenido de la primera a la segunda,\n--    (4,1) se llena la primera con el grifo,\n--    (2,3) se llena la segunda con la primera.\n-- \n-- Nota. No importa el orden en el que se generan las soluciones.\n-- ---------------------------------------------------------------------\n\n-- Un estado es una lista de dos n\u00fameros. El primero es el contenido de\n-- la jarra de 4 litros y el segundo el de la de 3 litros. \ntype EstadoJarras = (Int,Int)\n\ninicialJarras :: EstadoJarras\ninicialJarras = (0,0)\n\nesFinalJarras :: EstadoJarras -> Bool\nesFinalJarras (x,_) = x == 2\n\nsucesoresEjarras :: EstadoJarras -> [EstadoJarras]\nsucesoresEjarras (x,y) =\n  [(4,y) | x < 4] ++\n  [(x,3) | y < 3] ++\n  [(0,y) | x > 0] ++\n  [(x,0) | y > 0] ++\n  [(4,y-(4-x)) | x < 4, y > 0, x + y > 4] ++\n  [(x-(3-y),3) | x > 0, y < 3, x + y > 3] ++\n  [(x+y,0) | y > 0, x + y <= 4] ++ \n  [(0,x+y) | x > 0, x + y <= 3]\n\n-- Los nodos son las soluciones parciales\ntype NodoJarras = [EstadoJarras]\n\ninicialNjarras :: NodoJarras\ninicialNjarras = [inicialJarras]\n\nesFinalNjarras :: NodoJarras -> Bool\nesFinalNjarras (e:_) = esFinalJarras e\n\nsucesoresNjarras :: NodoJarras -> [NodoJarras]\nsucesoresNjarras n@(e:es) =\n  [e':n | e' <- sucesoresEjarras e,\n          e' `notElem` n]\n\nsolucionesJarras :: [NodoJarras]\nsolucionesJarras = buscaEE sucesoresNjarras\n                           esFinalNjarras\n                           inicialNjarras\n\njarras :: [[(Int,Int)]]\njarras = map reverse solucionesJarras\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticasse han resuelto ejercicios de la relaci\u00f3n 43 sobre resoluci\u00f3n de problemas en espacios de estados. Los problemas resueltos son el del domin\u00f3, el de la suma cero y el de las jarras. Los ejercicios y su soluci\u00f3n se&#8230;<\/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],"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\/6696"}],"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=6696"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6696\/revisions"}],"predecessor-version":[{"id":6697,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6696\/revisions\/6697"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}