{"id":7192,"date":"2020-05-22T10:17:30","date_gmt":"2020-05-22T08:17:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7192"},"modified":"2020-05-22T10:18:27","modified_gmt":"2020-05-22T08:18:27","slug":"i1m2019-el-patron-de-busqueda-en-escalada-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2019-el-patron-de-busqueda-en-escalada-en-haskell\/","title":{"rendered":"I1M2019: El patr\u00f3n de b\u00fasqueda en escalada en Haskell"},"content":{"rendered":"<p>En la clase de hoy de del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\">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 en espacios de estados.<\/p>\n<p>En primer lugar se explic\u00f3 la idea de la b\u00fasqueda en escalada y c\u00f3mo, usando dicha idea, se puede transformar el patr\u00f3n de b\u00fasqueda por primero el mejor en el de b\u00fasqueda en escalada. Finalmente, se aplic\u00f3 el patr\u00f3n de b\u00fasqueda en escalada a la resoluci\u00f3n del problema del cambio de monedas.<\/p>\n<p>La clase se ha dado mediante videoconferencia y el correspondiente v\u00eddeo es<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/OidcM24zBeg\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p>Los apuntes correspondientes a la clase es la secci\u00f3n 3 del tema 23<br \/>\n\n<!-- iframe plugin v.5.0 wordpress.org\/plugins\/iframe\/ -->\n<iframe loading=\"lazy\" src=\"https:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/temas\/tema-23.html#b%C3%BAsqueda-en-escalada\" width=\"100%\" frameborder=\"1\" height=\"500\" scrolling=\"yes\" class=\"iframe-class\"><\/iframe>\n<\/p>\n<p>Una versi\u00f3n interactiva de los apuntes en IHaskell se encuentra <a href=\"https:\/\/mybinder.org\/v2\/gh\/jaalonso\/Temas_interactivos_de_PF_con_Haskell\/master?urlpath=lab\/tree\/temas\/Tema-23.ipynb\">aqu\u00ed<\/a>.<\/p>\n<p>El c\u00f3digo del problema del cambio de monedas usado en la clase es<br \/>\n<!--more--><\/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-- ejMonedas es la lista del tipo de monedas disponibles. Se supone que\n-- hay un n\u00famero infinito de monedas de cada tipo.\nejMonedas :: [Moneda]\nejMonedas = [1,2,5,10,20,50,100]\n\n-- Las soluciones son listas de monedas.\ntype Solucion = [Moneda]\n\n-- Los estados son pares formados por la cantidad que falta y la lista\n-- de monedas usadas.\ntype Estado = (Int, [Moneda])\n\n-- (sucesores ms e) es la lista de los sucesores del estado e en el\n-- problema de las monedas. Por ejemplo,\n--   \u03bb> sucesores ejMonedas (199,[])\n--   [(198,[1]),(197,[2]),(194,[5]),(189,[10]),\n--    (179,[20]),(149,[50]),(99,[100])]\nsucesores :: [Moneda] -> Estado -> [Estado]\nsucesores monedas (r,ms) = \n  [(r - m, m : ms) | m <- monedas, r - m >= 0]\n\n-- (esFinal e) se verifica si e es un estado final del problema\n-- de las monedas.\nesFinal :: Estado -> Bool\nesFinal (r, _) = r == 0\n\n-- (cambio n) es la soluci\u00f3n del problema de las monedas por b\u00fasqueda en\n-- escalada. Por ejemplo,\n--    \u03bb> cambio ejMonedas 199\n--    Just [2,2,5,20,20,50,100]\n--    \u03bb> cambio [1,5,10,20,50,100] 199\n--    Just [1,1,1,1,5,20,20,50,100]\n--    \u03bb> cambio [5,10,50,100] 199\n--    Nothing\ncambio :: [Moneda] -> Int -> Maybe Solucion\ncambio ms n | null sols = Nothing\n            | otherwise = Just (snd (head sols))\n  where\n    sols = buscaEscalada (sucesores ms) esFinal (n,[])\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En 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 escalada en espacios de estados. En primer lugar se explic\u00f3 la idea de la b\u00fasqueda en escalada y c\u00f3mo, usando dicha idea, se puede transformar el patr\u00f3n de b\u00fasqueda&#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":[331],"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\/7192"}],"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=7192"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7192\/revisions"}],"predecessor-version":[{"id":7195,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7192\/revisions\/7195"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7192"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7192"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7192"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}