{"id":7185,"date":"2020-05-20T12:53:04","date_gmt":"2020-05-20T10:53:04","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7185"},"modified":"2020-05-20T12:54:05","modified_gmt":"2020-05-20T10:54:05","slug":"i1m2019-el-patron-de-busqueda-por-primero-el-mejor-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2019-el-patron-de-busqueda-por-primero-el-mejor-en-haskell\/","title":{"rendered":"I1M2019: El patr\u00f3n de b\u00fasqueda por primero el mejor 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 informada en espacios de estados.<\/p>\n<p>En primer lugar se estudiaron los algoritmos b\u00fasqueda con informaci\u00f3n (coste, heur\u00edstica y A*). A continuaci\u00f3n se estudi\u00f3 c\u00f3mo adaptar el patr\u00f3n de b\u00fasqueda ciega a b\u00fasqueda informada usando las colas de prioridad. Finalmente, se aplic\u00f3 el patr\u00f3n de b\u00fasqueda por primero el mejor a la resoluci\u00f3n del problema del 8 puzzle.<\/p>\n<p>La clase se ha dado mediante videoconferencia los correspondientes v\u00eddeos son<\/p>\n<ul>\n<li>Algoritmos de b\u00fasqueda informada en espacios de estados<\/li>\n<\/ul>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/-NqS03QuAzs\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<ul>\n<li>El patr\u00f3n de b\u00fasqueda por primero el mejor en Haskell<\/li>\n<\/ul>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/gCcQf3rNcRw\" 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-19\/temas\/tema-23.html#b%C3%BAsqueda-por-primero-el-mejor\" 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 de la primera soluci\u00f3n del problema del 8 puzzle usado en la clase es<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\nimport I1M.BusquedaPrimeroElMejor\nimport Data.List\nimport Data.Matrix \n\n-- Representaci\u00f3n del problema:\n-- ============================\n\n-- Una posici\u00f3n es un par de enteros.\ntype Posicion = (Int,Int)\n\n-- Un tablero es un una matriz \ntype Tablero = Matrix Int\n\n-- inicial1 e inicial2 son ejemplos de estados iniciales del 8 puzzle. \n--      +---+---+---+      +---+---+---+\n--      | 2 | 6 | 3 |      | 2 | 8 | 3 |\n--      +---+---+---+      +---+---+---+\n--      | 5 |   | 4 |      | 1 | 6 | 4 |\n--      +---+---+---+      +---+---+---+\n--      | 1 | 7 | 8 |      | 7 |   | 5 |\n--      +---+---+---+      +---+---+---+\ninicial1, inicial2 :: Tablero \ninicial1 = fromLists [[2,6,3],[5,0,4],[1,7,8]]\ninicial2 = fromLists [[2,8,3],[1,6,4],[7,0,5]]\n\n-- final es el estado final del 8 puzzle. En el ejemplo es\n--      +---+---+---+\n--      | 1 | 2 | 3 | \n--      +---+---+---+ \n--      | 8 |   | 4 | \n--      +---+---+---+ \n--      | 7 | 6 | 5 | \n--      +---+---+---+ \nfinal :: Tablero\nfinal = fromLists [[1,2,3],[8,0,4],[7,6,5]]\n\n-- (posicion t x) es la posici\u00f3n de x en el tablero t. Por ejemplo,\n--    posicion inicial1 0  ==  (2,2)\n--    posicion inicial1 7  ==  (3,2)\nposicion :: Tablero -> Int -> Posicion\nposicion t x =\n  head [(i,j) | i <- [1..3],\n                j <- [1..3],\n                t ! (i,j) == x]     \n\n\n-- (intercambia t p1 p2) es el tablero obtenido intercambiando los\n-- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo,\n--    \u03bb> inicial1\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 5 0 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u03bb> intercambia inicial1 (2,2) (2,3)\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 5 4 0 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\nintercambia :: Tablero -> Posicion -> Posicion -> Tablero\nintercambia t p1 p2 =\n  matrix 3 3 f\n  where f p | p == p1   = t ! p2\n            | p == p2   = t ! p1\n            | otherwise = t ! p\n\n-- (todosMovimientos t) es la lista de los tableros obtenidos\n-- aplic\u00e1ndole al tablero t todos los posibles movimientos; es decir,\n-- intercambiando la posici\u00f3n del hueco con sus adyacentes. Por ejemplo, \n--    \u03bb> inicial1\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 5 0 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u03bb> mapM_ print (todosMovimientos inicial1)\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 0 5 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 0 3 \u2502\n--    \u2502 5 6 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 5 4 0 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 5 7 4 \u2502\n--    \u2502 1 0 8 \u2502\n--    \u2514       \u2518\n--    \u03bb> mapM_ print (todosMovimientos (fromLists [[0,6,3],[2,5,4],[1,7,8]]))\n--    \u250c       \u2510\n--    \u2502 6 0 3 \u2502\n--    \u2502 2 5 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 6 3 \u2502\n--    \u2502 0 5 4 \u2502\n--    \u2502 1 7 8 \u2502\n--    \u2514       \u2518\ntodosMovimientos :: Tablero -> [Tablero]\ntodosMovimientos t =\n  [intercambia t (i,j) (i,j-1) | j > 1] ++   -- Izquierda\n  [intercambia t (i,j) (i-1,j) | i > 1] ++   -- Arriba\n  [intercambia t (i,j) (i,j+1) | j < 3] ++   -- Derecha\n  [intercambia t (i,j) (i+1,j) | i < 3]      -- Abajo\n  where (i,j) = posicion t 0\n\n-- Los nodos del espacio de estados son listas de tableros [t_n,...,t_1]\n-- tal que t_i es un sucesor de t_(i-1).\nnewtype Nodo = Est [Tablero]\n  deriving (Show, Eq)\n\n-- (sucesores e) es la lista de sucesores del estado e. Por ejemplo,\n--    \u03bb> sucesores (Est [inicial1])\n--    [Est [\u250c       \u2510 \u250c       \u2510\n--          \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502\n--          \u2502 0 5 4 \u2502 \u2502 5 0 4 \u2502\n--          \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502\n--          \u2514       \u2518,\u2514       \u2518 ],\n--     Est [\u250c       \u2510 \u250c       \u2510 \n--          \u2502 2 0 3 \u2502 \u2502 2 6 3 \u2502 \n--          \u2502 5 6 4 \u2502 \u2502 5 0 4 \u2502 \n--          \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502 \n--          \u2514       \u2518,\u2514       \u2518],\n--     Est [\u250c       \u2510 \u250c       \u2510  \n--          \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502  \n--          \u2502 5 4 0 \u2502 \u2502 5 0 4 \u2502  \n--          \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502  \n--          \u2514       \u2518,\u2514       \u2518],\n--     Est [\u250c       \u2510 \u250c       \u2510 \n--          \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502 \n--          \u2502 5 7 4 \u2502 \u2502 5 0 4 \u2502 \n--          \u2502 1 0 8 \u2502 \u2502 1 7 8 \u2502 \n--          \u2514       \u2518,\u2514       \u2518]]\n--    \u03bb> sucesores (head it)\n--    [Est [\u250c       \u2510 \u250c       \u2510 \u250c       \u2510  \n--          \u2502 0 6 3 \u2502 \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502  \n--          \u2502 2 5 4 \u2502 \u2502 0 5 4 \u2502 \u2502 5 0 4 \u2502  \n--          \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502  \n--          \u2514       \u2518,\u2514       \u2518,\u2514       \u2518],\n--     Est [\u250c       \u2510 \u250c       \u2510 \u250c       \u2510  \n--          \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502 \u2502 2 6 3 \u2502  \n--          \u2502 1 5 4 \u2502 \u2502 0 5 4 \u2502 \u2502 5 0 4 \u2502  \n--          \u2502 0 7 8 \u2502 \u2502 1 7 8 \u2502 \u2502 1 7 8 \u2502  \n--          \u2514       \u2518,\u2514       \u2518,\u2514       \u2518]]\nsucesores :: Nodo -> [Nodo]\nsucesores (Est (n@(t:ts))) = \n  [Est (t':n) | t' <- todosMovimientos t, \n                t' `notElem` n]\n\n-- (esFinal n) se verifica si n es un nodo final.\nesFinal :: Nodo -> Bool\nesFinal (Est (t:_)) = t == final\n\n-- (heuristica t) es la suma de la distancia Manhatan desde la posici\u00f3n de\n-- cada objeto del tablero a su posici\u00f3n en el estado final. Por\n-- ejemplo,\n--    heuristica inicial1  ==  12\n--    heuristica inicial2  ==  6\nheuristica :: Tablero  -> Int\nheuristica t =\n  sum [distancia (posicion t x) (posicion final x) | x <- [0..8]]\n\n-- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y\n-- p2. Por ejemplo,\n--    distancia (2,7) (4,1)  ==  8\ndistancia :: Posicion -> Posicion -> Int\ndistancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2)\n\n-- Un nodo n1 es menor o igual n2 la heur\u00edstica del estado actual de n1\n-- es menor o igual que la del estado actual de n2. \ninstance Ord Nodo where \n  Est (t1:_) <= Est (t2:_) = heuristica t1 <= heuristica t2\n\n-- (soluciones i) es la lista de las soluciones del 8 puzzle por b\u00fasqueda\n-- primero el mejor a partir del estado inicial i. Por ejemplo,\n--    \u03bb> mapM_ print (head (soluciones inicial2))\n--    \u250c       \u2510\n--    \u2502 2 8 3 \u2502\n--    \u2502 1 6 4 \u2502\n--    \u2502 7 0 5 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 8 3 \u2502\n--    \u2502 1 0 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 2 0 3 \u2502\n--    \u2502 1 8 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 0 2 3 \u2502\n--    \u2502 1 8 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 1 2 3 \u2502\n--    \u2502 0 8 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\n--    \u250c       \u2510\n--    \u2502 1 2 3 \u2502\n--    \u2502 8 0 4 \u2502\n--    \u2502 7 6 5 \u2502\n--    \u2514       \u2518\nsoluciones :: Tablero -> [[Tablero]]\nsoluciones inicial =\n  [reverse ts | (Est ts) <- buscaPM sucesores esFinal (Est [inicial])]\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 informada en espacios de estados. En primer lugar se estudiaron los algoritmos b\u00fasqueda con informaci\u00f3n (coste, heur\u00edstica y A*). A continuaci\u00f3n se estudi\u00f3 c\u00f3mo adaptar el patr\u00f3n de b\u00fasqueda ciega&#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\/7185"}],"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=7185"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7185\/revisions"}],"predecessor-version":[{"id":7188,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7185\/revisions\/7188"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}