{"id":4896,"date":"2015-05-06T12:48:03","date_gmt":"2015-05-06T10:48:03","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4896"},"modified":"2015-05-15T13:05:35","modified_gmt":"2015-05-15T11:05:35","slug":"i1m2014-el-patron-de-busqueda-en-escalada-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-el-patron-de-busqueda-en-escalada-en-haskell\/","title":{"rendered":"I1M2014: El patr\u00f3n de b\u00fasqueda en escalada en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy 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 escalada.<\/p>\n<p>En primer lugar, se explic\u00f3 el patr\u00f3n de b\u00fasqueda en escalada. A continuaci\u00f3n, se aplic\u00f3 el patr\u00f3n para resolver el problema problema del cambio de monedas y al c\u00e1lculo del \u00e1rbol de expansi\u00f3n m\u00ednimo por escalada mediante el algoritmo de Prim.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 40-52 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-23t.pdf\">tema 23<\/a>:<br \/>\n<!--more--><\/p>\n<p>El c\u00f3digo del patr\u00f3n de b\u00fasqueda en escalada es<\/p>\n<pre lang=\"haskell\">\nmodule BusquedaEnEscalada (buscaEscalada) where\n\n-- ---------------------------------------------------------------------\n-- Importaciones                                                      --\n-- ---------------------------------------------------------------------\n\n-- Nota: Hay que elegir una implementaci\u00f3n de las colas de prioridad y\n-- otra de grafos.\n\n-- Implementaciones de colas de prioridad:\nimport I1M.ColaDePrioridad\n-- import ColaDePrioridadConListas\n-- import ColaDePrioridadConMonticulos\n\n-- ---------------------------------------------------------------------\n-- El patr\u00f3n de b\u00fasqueda en escalada                                  --\n-- ---------------------------------------------------------------------\n\n-- (buscaEscalada 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), obtenidas buscando por escalada.\nbuscaEscalada :: Ord nodo => \n                 (nodo -> [nodo])   -- sucesores\n                 -> (nodo -> Bool)  -- es final\n                 -> nodo            -- nodo actual\n                 -> [nodo]          -- soluciones\nbuscaEscalada sucesores esFinal x = (busca' (inserta x vacia) )\n    where\n      busca' c  \n          | esVacia c           = [] \n          | esFinal (primero c) = [primero c]\n          | otherwise           = \n              busca' (foldr inserta vacia (sucesores x))\n              where x = primero c\n<\/pre>\n<p>El c\u00f3digo del problema del cambio de monedas es<\/p>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEscalada\n\n-- El problema del cambio de monedas consiste en determinar c\u00f3mo\n-- conseguir una cantidad usando el menor n\u00famero de monedas disponibles. \n\n-- Las monedas son n\u00fameros enteros.\ntype Moneda = Int\n\n-- monedas es la lista del tipo de monedas disponibles. Se supone que\n-- hay un n\u00famero infinito de monedas de cada tipo.\nmonedas :: [Moneda]\nmonedas = [1,2,5,10,20,50,100]\n\n-- Las soluciones son listas de monedas.\ntype Soluciones = [Moneda]\n\n-- Los estados son pares formados por la cantidad que falta y la lista\n-- de monedas usadas.\ntype NodoMonedas = (Int, [Moneda])\n\n-- (sucesoresMonedas e) es la lista de los sucesores del estado e en el\n-- problema de las monedas. Por ejemplo,\n--   ghci> sucesoresMonedas (199,[])\n--   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n--    (179,[20]),(149,[50]),(99,[100])]\nsucesoresMonedas :: NodoMonedas -> [NodoMonedas]\nsucesoresMonedas (r,p) = \n    [(r-c,c:p) | c <- monedas, r-c >= 0]\n\n-- (esFinalMonedas e) se verifica si e es un estado final del problema\n-- de las monedas.\nesFinalMonedas :: NodoMonedas -> Bool\nesFinalMonedas (v,_) = v==0\n\n-- (cambio n) es la soluci\u00f3n del problema de las monedas por b\u00fasqueda en\n-- escalada. Por ejemplo,\n--    cambio 199  ==  [2,2,5,20,20,50,100]\ncambio :: Int -> Soluciones\ncambio n = \n    snd (head (buscaEscalada sucesoresMonedas \n                             esFinalMonedas \n                             (n,[])))\n<\/pre>\n<p>El c\u00f3digo para el c\u00e1lculo de \u00e1rboles de expansi\u00f3n m\u00ednimos es<\/p>\n<pre lang=\"haskell\">\nimport I1M.BusquedaEnEscalada\n\n-- Implementaciones del TAD grafo.\nimport I1M.Grafo\n-- import GrafoConVectorDeAdyacencia\n-- import GrafoConMatrizDeAdyacencia\n\nimport Data.Array\nimport Data.List\n\ng1 :: Grafo Int Int    \ng1 = creaGrafo D (1,5) [(1,2,12),(1,3,34),(1,5,78),\n                        (2,4,55),(2,5,32),\n                        (3,4,61),(3,5,44),\n                        (4,5,93)]\n\n-- Una arista esta formada dos nodos junto con su peso.\ntype Arista a b = (a,a,b)\n\n-- Un nodo (NodoAEM (p,t,r,aem)) est\u00e1 formado por el peso p de la \u00faltima\n-- arista a\u00f1adida el \u00e1rbol de expansi\u00f3n m\u00ednimo (aem), la lista t\n-- de nodos del grafo que est\u00e1n en el aem, la lista r de nodos del\n-- grafo que no est\u00e1n en el aem y el aem. \ntype NodoAEM a b = (b,[a],[a],[Arista a b])\n\n-- (sucesoresAEM g n) es la lista de los sucesores del nodo n en el\n-- grafo g. Por ejemplo,\n--    ghci> sucesoresAEM g1 (0,[1],[2..5],[])\n--    [(12,[2,1],[3,4,5],[(1,2,12)]),\n--     (34,[3,1],[2,4,5],[(1,3,34)]),\n--     (78,[5,1],[2,3,4],[(1,5,78)])]\nsucesoresAEM :: (Ix a,Num b) => (Grafo a b) -> (NodoAEM a b)\n                           -> [(NodoAEM a b)]\nsucesoresAEM g (_,t,r,aem)\n        = [(peso x y g, (y:t), delete y r, (x,y,peso x y g):aem)\n           | x <- t , y <- r, aristaEn g (x,y)]\n\n-- (esFinalAEM n) se verifica si n es un estado final; es decir, si no\n-- queda ning\u00fan elemento en la lista de nodos sin colocar en el \u00e1rbol de\n-- expansi\u00f3n m\u00ednimo.\nesFinalAEM (_,_,[],_) = True\nesFinalAEM _          = False\n\n-- (prim g) es el \u00e1rbol de expansi\u00f3n m\u00ednimo del grafo g, por el\n-- algoritmo de Prim como b\u00fasqueda en escalada. Por ejemplo,\n--    prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)]\nprim g = sol\n    where [(_,_,_,sol)] = buscaEscalada (sucesoresAEM g) \n                                        esFinalAEM\n                                        (0,[n],ns,[])\n          (n:ns) = nodos g\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy 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 escalada. En primer lugar, se explic\u00f3 el patr\u00f3n de b\u00fasqueda en escalada. A continuaci\u00f3n, se aplic\u00f3 el patr\u00f3n para resolver el problema problema del cambio de&#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\/4896"}],"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=4896"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4896\/revisions"}],"predecessor-version":[{"id":4900,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4896\/revisions\/4900"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4896"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4896"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4896"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}