{"id":4858,"date":"2015-04-08T19:33:44","date_gmt":"2015-04-08T17:33:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4858"},"modified":"2015-04-08T19:33:44","modified_gmt":"2015-04-08T17:33:44","slug":"i1m2014-el-patron-de-busqueda-en-espacios-de-estados-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-patron-de-busqueda-en-espacios-de-estados-en-haskell\/","title":{"rendered":"I1M2014: El patr\u00f3n de b\u00fasqueda en espacios de estados en Haskell"},"content":{"rendered":"<p>En la la segunda parte de la clase de hoy de del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado la t\u00e9cnica de resoluci\u00f3n de problemas mediante b\u00fasqueda en espacios de estados.<\/p>\n<p>La clase comenz\u00f3 analizando los \u00e1rboles de b\u00fasquedas para el problema de las 4 reinas y para el problema de la mochila.<\/p>\n<p>De este an\u00e1lisis se extrae el patr\u00f3n de resoluci\u00f3n de problemas mediante b\u00fasqueda en espacios de estados (EE) y sus argumentos:<\/p>\n<ul>\n<li>cu\u00e1l es el estado inicial,<\/li>\n<li>c\u00f3mo se calculan los sucesores de un estado y<\/li>\n<li>c\u00f3mo decidir si un estado es un estado final.<\/li>\n<\/ul>\n<p>A continuaci\u00f3n se implementa el patr\u00f3n de b\u00fasqueda en espacio de estados en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.<\/p>\n<p>Finalmente, se aplica el patr\u00f3n para implementar las soluciones de los problemas de las N reinas y del cambio de monedas.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 11-28 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-23t.pdf\">tema 23<\/a>:<br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/8057273' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>El c\u00f3digo del patr\u00f3n de b\u00fasqueda en espacio de estados es<\/p>\n<pre lang=\"haskell\">\nmodule BusquedaEnEspaciosDeEstados (buscaEE) where\nimport I1M.Pila\n\n-- (buscaEE s o e) es la lista de soluciones del problema de espacio de\n-- estado definido por la funci\u00f3n sucesores (s), el objetivo (o) y el\n-- estado inicial (e).\nbuscaEE:: (Eq nodo) => (nodo -> [nodo])    -- sucesores\n                       -> (nodo -> Bool)   -- esFinal\n                       -> nodo             -- nodo actual\n                       -> [nodo]           -- soluciones\nbuscaEE sucesores esFinal x = busca' (apila x vacia) \n where\n   busca' p  \n    | esVacia p        = [] \n    | esFinal (cima p) = cima p : busca' (desapila p)\n    | otherwise        = busca' (foldr apila (desapila p) (sucesores x))\n                         where x = cima p\n<\/pre>\n<p>El c\u00f3digo del problema de las N reinas es<\/p>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEspaciosDeEstados\n\n-- El problema de las n reinas consiste en colocar n reinas en un\n-- tablero cuadrado de dimensiones n por n de forma que no se encuentren\n-- m\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal.\n\n-- Las posiciones de las reinas en el tablero se representan por su\n-- columna y su fila.\ntype Columna = Int\ntype Fila    = Int\n\n-- Una soluci\u00f3n del problema de las n reinas es una lista de\n-- posiciones. \ntype SolNR = [(Columna,Fila)]\n\n-- (valida sp p) se verifica si la posici\u00f3n p es v\u00e1lida respecto de la\n-- soluci\u00f3n parcial sp; es decir, la reina en la posici\u00f3n p no amenaza a\n-- ninguna de las reinas de la sp (se supone que est\u00e1n en distintas\n-- columnas). Por ejemplo, \n--    valida [(1,1)] (2,2)  ==  False\n--    valida [(1,1)] (2,3)  ==  True\nvalida :: SolNR -> (Columna,Fila) -> Bool\nvalida solp (c,r) = and [test s | s <- solp]\n    where test (c',r') = and [c'+r'\/=c+r,c'-r'\/=c-r,r'\/=r]\n\n-- Los nodos del problema de las n reinas son ternas formadas por la\n-- columna de la siguiente reina, el n\u00famero de columnas del\n-- tablero y la soluci\u00f3n parcial de las reinas colocadas anteriormente. \ntype NodoNR = (Columna,Columna,SolNR)\n\n-- (sucesoresNR e) es la lista de los sucesores del estado e en el\n-- problema de las n reinas. Por ejemplo,\n--    ghci> sucesoresNR (0,4,[])\n--    [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])]\nsucesoresNR :: NodoNR -> [NodoNR]\nsucesoresNR (c,n,solp)\n    = [(c+1,n,solp++[(c,r)]) | r <- [1..n] , valida solp (c,r)]\n\n-- (esFinalNR e) se verifica si e es un estado final del problema de las\n-- n reinas. \nesFinalNR :: NodoNR -> Bool\nesFinalNR (c,n,solp) = c > n\n\n-- (buscaEE_NR n) es la primera soluci\u00f3n del problema de las n reinas,\n-- por b\u00fasqueda en espacio de estados. Por ejemplo,\n--    ghci> buscaEE_NR 8\n--    [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)]\nbuscaEE_NR :: Columna -> SolNR\nbuscaEE_NR n = s\n    where ((_,_,s):_) = buscaEE sucesoresNR esFinalNR (1,n,[])\n\n-- (nSolucionesNR n) es el n\u00famero de soluciones del problema de las n\n-- reinas, por b\u00fasqueda en espacio de estados. Por ejemplo,  \n--    nSolucionesNR 8  ==  92\nnSolucionesNR :: Columna -> Int\nnSolucionesNR n = \n    length (buscaEE sucesoresNR \n                    esFinalNR \n                    (1,n,[]))\n<\/pre>\n<p>El c\u00f3digo del problema de la mochila es<\/p>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEspaciosDeEstados\nimport Data.List (sort)\n\n-- Se tiene una mochila de capacidad de peso p y una lista de n objetos\n-- para colocar en la mochila. Cada objeto i tiene un peso w_i y un\n-- valor v_i. Considerando la posibilidad de colocar el mismo objeto\n-- varias veces en la mochila, el problema consiste en determinar la\n-- forma de colocar los objetos en la mochila sin sobrepasar la\n-- capacidad de la mochila colocando el m\u00e1ximmo valor posible.\n\n-- Los pesos son n\u00famero enteros\ntype Peso = Int\n\n-- Los valores son n\u00fameros reales.\ntype Valor = Float\n\n-- Los objetos son pares formado por un peso y un valor\ntype Objeto = (Peso,Valor)\n\n-- Una soluci\u00f3n del problema de la mochila es una lista de objetos.\ntype SolMoch = [Objeto]\n\n-- Los estados del problema de la mochila son 5-tupla de la forma\n-- (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el\n-- peso de los objetos colocados, l es el l\u00edmite de la capacidad de la\n-- mochila, o es la lista de los objetos colocados (ordenados de forma\n-- creciente seg\u00fan sus pesos) y s es la soluci\u00f3n parcial.\ntype NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)\n\n\n-- (sucesoresMoch e) es la lista de los sucesores del estado e en el\n-- problema de la mochila.\nsucesoresMoch :: NodoMoch -> [NodoMoch]\nsucesoresMoch (v,p,limite,objetos,solp)\n    = [( v+v',\n         p+p',\n         limite,\n         [o | o@(p'',_) <- objetos,(p''>=p')], \n         (p',v'):solp )\n       | (p',v') <- objetos, \n         p+p' <= limite]\n\n-- (esObjetivoMoch e) se verifica si e es un estado final el problema de\n-- la mochila.\nesObjetivoMoch :: NodoMoch -> Bool\nesObjetivoMoch (_,p,limite,((p',_):_),_) = p+p'>limite\n\n-- (buscaEE_Mochila os l) es la soluci\u00f3n del problema de la mochila para\n-- la lista de objetos os y el l\u00edmite de capacidad l. Por ejemplo,\n--    > buscaEE_Mochila [(2,3),(3,5),(4,6),(5,10)] 8\n--    ([(5,10.0),(3,5.0)],15.0)\n--    > buscaEE_Mochila [(2,3),(3,5),(5,6)] 10\n--    ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0)\n--    > buscaEE_Mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35\n--    ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0)\n--    > buscaEE_Mochila [(2,2.8),(3,4.4),(5,6.1)] 10\n--    ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4)\nbuscaEE_Mochila :: [Objeto] -> Peso -> (SolMoch,Valor)\nbuscaEE_Mochila objetos limite = (sol,v) \n    where \n      (v,_,_,_,sol) = \n          maximum (buscaEE sucesoresMoch \n                           esObjetivoMoch  \n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la la segunda parte de la clase de hoy de del curso Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado la t\u00e9cnica de resoluci\u00f3n de problemas mediante b\u00fasqueda en espacios de estados. La clase comenz\u00f3 analizando los \u00e1rboles de b\u00fasquedas para el problema de las 4 reinas y para el problema de la&#8230;<\/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\/4858"}],"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=4858"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4858\/revisions"}],"predecessor-version":[{"id":4859,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4858\/revisions\/4859"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4858"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4858"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4858"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}