{"id":4887,"date":"2015-05-04T17:02:29","date_gmt":"2015-05-04T15:02:29","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4887"},"modified":"2015-05-05T11:03:42","modified_gmt":"2015-05-05T09:03:42","slug":"i1m2014-resolucion-de-problemas-mediante-busqueda-en-espacios-de-estados-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-resolucion-de-problemas-mediante-busqueda-en-espacios-de-estados-en-haskell\/","title":{"rendered":"I1M2014: Resoluci\u00f3n de problemas mediante b\u00fasqueda en espacios de estados en Haskell"},"content":{"rendered":"<p>En la segunda parte de 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 34 sobre problemas en espacios de estados.<\/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-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-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport I1M.BusquedaEnEspaciosDeEstados\nimport Data.List (delete, nub, sort)\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)]]\n--    ghci> domino [(1,2),(2,3),(5,4)]\n--    []\n-- ---------------------------------------------------------------------\n\ntype Ficha  = (Int,Int)\n\n-- Los estados son los pares formados por la listas sin colocar y las\n-- colocadas. \ntype EstadoDomino = ([Ficha],[Ficha])\n\ninicialDomino :: [Ficha] -> EstadoDomino\ninicialDomino fs = (fs,[])\n\nesFinalDomino :: EstadoDomino -> Bool\nesFinalDomino (fs,_) = null fs \n\nsucesoresDomino :: EstadoDomino -> [EstadoDomino]\nsucesoresDomino (fs,[]) = [(delete f fs, [f]) | f <- fs]\nsucesoresDomino (fs,n@((x,y):qs)) =\n    [(delete (u,v) fs,(u,v):n) | (u,v) <- rs, u \/= v, v == x] ++\n    [(delete (u,v) fs,(v,u):n) | (u,v) <- rs, u \/= v, u == x] ++\n    [(delete (u,v) fs,(u,v):n) | (u,v) <- rs, u == v, u == x] \n    where rs = [(u,v) | (u,v) <- fs, (u,v) `notElem` n, (v,u) `notElem` n]\n\nsolucionesDomino :: [Ficha] -> [EstadoDomino]\nsolucionesDomino ps = buscaEE sucesoresDomino\n                              esFinalDomino         \n                              (inicialDomino ps)\n\ndomino :: [(Int,Int)] -> [[(Int,Int)]]\ndomino ps = map snd (solucionesDomino 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 se 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-- 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 primera 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\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\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 34 sobre problemas en espacios de estados. 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\/4887"}],"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=4887"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4887\/revisions"}],"predecessor-version":[{"id":4888,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4887\/revisions\/4888"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4887"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4887"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4887"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}