{"id":6702,"date":"2019-05-31T12:44:18","date_gmt":"2019-05-31T10:44:18","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6702"},"modified":"2019-05-31T12:44:18","modified_gmt":"2019-05-31T10:44:18","slug":"i1m2018-el-problema-de-las-fichas-mediante-busqueda-en-espacio-de-estado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-el-problema-de-las-fichas-mediante-busqueda-en-espacio-de-estado\/","title":{"rendered":"I1M2018: El problema de las fichas mediante b\u00fasqueda en espacio de estado"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>se han resuelto ejercicios de la relaci\u00f3n 44 en el que se aplican los patrones de busqueda en profundidad, en anchura, primero el mejor y en escalada para resolver el provlema de las fichas y comparar las soluciones obtenidas.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Introducci\u00f3n                                                     --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Para el problema de las fichas de orden (m,n) se considera un tablero\n-- con m+n+1 cuadrados consecutivos.\n-- \n-- Inicialmente, en cada uno de los m primeros cuadrados hay una ficha\n-- blanca, a continuaci\u00f3n un hueco y  en cada uno de los n \u00faltimos\n-- cuadrados hay una ficha verde. El objetivo consiste en tener las\n-- fichas verdes al principio y las blancas al final.\n-- \n-- Por ejemplo, en el problema de las fichas de orden (3,3) la situaci\u00f3n\n-- inicial es  \n--       +---+---+---+---+---+---+---+\n--       | B | B | B |   | V | V | V |\n--       +---+---+---+---+---+---+---+\n-- y la final es\n--       +---+---+---+---+---+---+---+\n--       | V | V | V |   | B | B | B |\n--       +---+---+---+---+---+---+---+\n-- \n-- Los movimientos permitidos consisten en desplazar una ficha al hueco\n-- saltando, como m\u00e1ximo, sobre otras dos.\n-- \n-- El objetivo de esta relaci\u00f3n de ejercicios es resolver el problema\n-- de las fichas mediante b\u00fasqueda en espacio de estados, utilizando las \n-- implementaciones estudiadas en el tema 23 \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\/temas\/tema-23.html\n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda\n-- I1M. Los pasos para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Importaciones                                                      --\n-- ---------------------------------------------------------------------\n\nimport I1M.BusquedaEnEspaciosDeEstados\nimport I1M.BusquedaPrimeroElMejor\nimport I1M.BusquedaEnEscalada\nimport I1M.Cola\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Representaci\u00f3n de estados                                        --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir el tipo Ficha con tres constructores B, V y H\n-- que representan las fichas blanca, verde y hueco, respectivamente.\n-- ---------------------------------------------------------------------\n\ndata Ficha = B | V | H\n  deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir el tipo Estado como abreviatura de una lista de\n-- fichas que representa las fichas colocadas en el tablero.\n-- ---------------------------------------------------------------------\n\ntype Estado = [Ficha]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n \n--    inicial ::  Int -> Int -> Estado\n-- tal que (inicial m n) representa el estado inicial del problema de\n-- las fichas de orden (m,n). Por ejemplo,\n--    inicial 2 3  ==  [B,B,H,V,V,V]\n--    inicial 3 2  ==  [B,B,B,H,V,V]\n-- ---------------------------------------------------------------------\n\ninicial ::  Int -> Int -> Estado\ninicial m n = replicate m B ++ [H] ++ replicate n V\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n \n--    final ::  Int -> Int -> Estado\n-- tal que (final m n) representa el estado final del problema de\n-- las fichas de orden (m,n). Por ejemplo,\n--    final 2 3  ==  [V,V,V,H,B,B]\n--    final 3 2  ==  [V,V,H,B,B,B]\n-- ---------------------------------------------------------------------\n\nfinal ::  Int -> Int -> Estado\nfinal m n = replicate n V ++ [H] ++ replicate m B\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    sucesoresE :: Estado -> [Estado]\n-- tal que (sucesoresE e) es la lista de los sucesores del estado e. Por\n-- ejemplo, \n--    ghci> sucesoresE [V,B,H,V,V,B]\n--    [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B],\n--     [V,B,B,V,V,H]]\n--    ghci> sucesoresE [B,B,B,H,V,V,V]\n--    [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V],\n--     [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]]\n-- ---------------------------------------------------------------------\n\nsucesoresE :: Estado -> [Estado]\nsucesoresE e =\n  [intercambia i j e | i <- [j-1,j-2,j-3,j+1,j+2,j+3]\n                     , 0 <= i, i < n]\n  where j = posicionHueco e\n        n = length e\n\n-- (posicionHueco e) es la posici\u00f3n del hueco en el estado e. Por\n-- ejemplo, \n--    posicionHueco inicial  ==  3\nposicionHueco :: Estado -> Int\nposicionHueco e = length (takeWhile (\/=H) e)\n\n-- (intercambia xs i j) es la lista obtenida intercambiando los\n-- elementos de xs en las posiciones i y j. Por ejemplo, \n--    intercambia 2 6 [0..9]  ==  [0,1,6,3,4,5,2,7,8,9]\n--    intercambia 6 2 [0..9]  ==  [0,1,6,3,4,5,2,7,8,9]\nintercambia :: Int -> Int -> [a] -> [a]\nintercambia i j xs = concat [xs1,[x2],xs2,[x1],xs3]\n  where (xs1,x1,xs2,x2,xs3) = divide (min i j) (max i j) xs \n\n-- (divide xs i j) es la tupla (xs1,x1,xs2,x2,xs3) tal que xs1 son los\n-- elementos de xs cuya posici\u00f3n es menos que i, x1 es el elemento de xs\n-- en la posici\u00f3n i, xs2 son los elementos de xs cuya posici\u00f3n es mayor\n-- que i y menor que j, x2 es el elemento de xs en la posici\u00f3n j y xs3\n-- son los elementos de xs cuya posici\u00f3n es mayor que j (suponiendo que\n-- i < j). Por ejemplo, \n--    divide 2 6 [0..9]  ==  ([0,1],2,[3,4,5],6,[7,8,9])\ndivide :: Int -> Int -> [a] -> ([a],a,[a],a,[a])\ndivide i j xs = (xs1,x1,xs2,x2,xs3)\n  where (xs1,x1:ys)  = splitAt i xs\n        (xs2,x2:xs3) = splitAt (j - i - 1) ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Los nodos del espacio de b\u00fasqueda son lista de estados \n--    [e_n, ..., e_2, e_1]\n-- donde e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un\n-- sucesor de e_(i-1). \n-- \n-- Definir el tipo de datos Nodo para representar los nodos del\n-- espacio de b\u00fasqueda. Por ejemplo, \n--    ghci> :type (N [[B,H,B,V,V,V],[B,B,H,V,V,V]])\n--    (N [[B,H,B,V,V,V],[B,B,H,V,V,V]]) :: Nodo\n-- ---------------------------------------------------------------------\n\ndata Nodo = N [Estado]\n  deriving (Eq, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n \n--    inicialN ::  Int -> Int -> Nodo\n-- tal que (inicialN m n) representa el nodo inicial del problema de\n-- las fichas de orden (m,n). Por ejemplo,\n--    inicialN 2 3  ==  N [[B,B,H,V,V,V]]\n--    inicialN 3 2  ==  N [[B,B,B,H,V,V]]\n-- ---------------------------------------------------------------------\n\ninicialN :: Int -> Int -> Nodo\ninicialN m n = N [inicial m n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n \n--    esFinalN :: Int -> Int -> Nodo -> Bool\n-- tal que (esFinalN m n) se verifica si N es un nodo final del problema\n-- de las fichas de orden (m,n). Por ejemplo,\n--    ghci> esFinalN 2 1 (N [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n--    True\n--    ghci> esFinalN 2 1 (N [[V,B,B,H],[H,B,B,V],[B,B,H,V]])\n--    False\n-- ---------------------------------------------------------------------\n\nesFinalN :: Int -> Int -> Nodo -> Bool\nesFinalN m n (N (e:_)) = e == final m n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir la funci\u00f3n\n--    sucesoresN :: Nodo -> [Nodo]\n-- tal que (sucesoresN n) es la lista de los sucesores del nodo n. Por\n-- ejemplo, \n--    ghci> sucesoresN (N [[H,B,B,V],[B,B,H,V]])\n--    [N [[B,H,B,V],[H,B,B,V],[B,B,H,V]],\n--     N [[V,B,B,H],[H,B,B,V],[B,B,H,V]]]\n--    ghci> sucesoresN (N [[B,H,B,V],[H,B,B,V],[B,B,H,V]])\n--    [N [[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]]\n-- ---------------------------------------------------------------------\n\nsucesoresN :: Nodo -> [Nodo]\nsucesoresN (N n@(e:es)) =\n  [N (e':n) | e' <- sucesoresE e,\n              e' `notElem` es]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    solucionesEE :: Int -> Int -> [[Estado]]\n-- tal que (solucionesEE m n) es la lista de las soluciones del problema\n-- de las dichas obtenidas con el patr\u00f3n buscaEE (que realiza la\n-- b\u00fasqueda en profundidad). Por ejemplo,\n--    ghci> mapM_ print (zip [0..] (head (solucionesEE 2 2)))\n--    ( 0,[B,B,H,V,V])\n--    ( 1,[B,H,B,V,V])\n--    ( 2,[H,B,B,V,V])\n--    ( 3,[V,B,B,H,V])\n--    ( 4,[V,B,H,B,V])\n--    ( 5,[V,H,B,B,V])\n--    ( 6,[H,V,B,B,V])\n--    ( 7,[B,V,H,B,V])\n--    ( 8,[B,H,V,B,V])\n--    ( 9,[H,B,V,B,V])\n--    (10,[B,B,V,H,V])\n--    (11,[B,B,V,V,H])\n--    (12,[B,H,V,V,B])\n--    (13,[H,B,V,V,B])\n--    (14,[V,B,H,V,B])\n--    (15,[V,H,B,V,B])\n--    (16,[H,V,B,V,B])\n--    (17,[B,V,H,V,B])\n--    (18,[B,V,V,H,B])\n--    (19,[H,V,V,B,B])\n--    (20,[V,H,V,B,B])\n--    (21,[V,V,H,B,B])\n--    \n--    ghci> length (head (solucionesEE 6 5))\n--    2564\n--    (13.65 secs, 256,880,520 bytes)\n-- ---------------------------------------------------------------------\n\nsolucionesEE :: Int -> Int -> [[Estado]]\nsolucionesEE m n =\n  [reverse es | N es <- buscaEE sucesoresN (esFinalN  m n) (inicialN m n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Se considera la heur\u00edstica que para cada estado vale la\n-- suma de piezas blancas situadas a la izquierda de cada una de las\n-- piezas verdes. Por ejemplo, para el estado\n--       +---+---+---+---+---+---+---+\n--       | B | V | B |   | V | V | B |   \n--       +---+---+---+---+---+---+---+\n-- su valor es 1+2+2 = 5.\n--\n-- Definir la funci\u00f3n\n--    heuristicaE :: Estado -> Int\n-- tal que (heuristicaE e) es la heur\u00edstica del estado e. Por ejemplo,\n-- ---------------------------------------------------------------------\n\nheuristicaE :: Estado -> Int\nheuristicaE []     = 0\nheuristicaE (V:xs) = heuristicaE xs\nheuristicaE (H:xs) = heuristicaE xs\nheuristicaE (B:xs) = heuristicaE xs + length (filter (==V) xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    heuristicaN :: Nodo -> Int\n-- tal que (heuristicaN n) es la heur\u00edstica del primer estado del\n-- camino. Por ejemplo,\n--    heuristicaN (N [[H,B,B,V],[B,B,H,V]])            ==  2\n--    heuristicaN (N [[V,B,B,H],[H,B,B,V],[B,B,H,V]])  ==  0\n-- ---------------------------------------------------------------------\n\nheuristicaN :: Nodo -> Int\nheuristicaN (N (e:_)) = heuristicaE e  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la pertenencia de Nodo a Ord que forma que un\n-- nodo es menor o igual que otro si su heur\u00edstica lo es.\n-- ---------------------------------------------------------------------\n\ninstance Ord Nodo where \n  n1 <= n2 = heuristicaN n1 <= heuristicaN n2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    solucionesPM :: Int -> Int -> [[Estado]]\n-- tal que (solucionesPM m n) es la lista de las soluciones del problema\n-- de las dichas obtenidas con el patr\u00f3n buscaPM (que realiza la\n-- b\u00fasqueda por primero el mejor). Por ejemplo,\n--    ghci> \n--    (0,[B,B,H,V,V])\n--    (1,[B,H,B,V,V])\n--    (2,[B,V,B,H,V])\n--    (3,[H,V,B,B,V])\n--    (4,[V,H,B,B,V])\n--    (5,[V,V,B,B,H])\n--    (6,[V,V,B,H,B])\n--    (7,[V,V,H,B,B])\n--    \n--    ghci> length (head (solucionesPM 6 5))\n--    54\n--    (0.05 secs, 5,430,056 bytes)\n-- ---------------------------------------------------------------------\n\nsolucionesPM :: Int -> Int -> [[Estado]]\nsolucionesPM m n =\n  [reverse es | N es <- buscaPM sucesoresN\n                                (esFinalN m n)\n                                (inicialN m n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    solucionesEscalada :: Int -> Int -> [[Estado]]\n-- tal que (solucionesEscalada m n) es la lista de las soluciones del\n-- problema de las dichas obtenidas con el patr\u00f3n buscaEscalada (que\n-- realiza la b\u00fasqueda por escalada). Por ejemplo,\n--    ghci> mapM_ print (zip [0..] (head (solucionesEscalada 2 2)))\n--    (0,[B,B,H,V,V])\n--    (1,[B,H,B,V,V])\n--    (2,[B,V,B,H,V])\n--    (3,[H,V,B,B,V])\n--    (4,[V,H,B,B,V])\n--    (5,[V,V,B,B,H])\n--    (6,[V,V,B,H,B])\n--    (7,[V,V,H,B,B])\n--\n--    ghci> length (head (solucionesEscalada 4 5))\n--    37\n--    (0.02 secs, 1,718,560 bytes)\n--    \n--    ghci> length (head (solucionesEscalada 6 5))\n--    *** Exception: Prelude.head: empty list\n-- ---------------------------------------------------------------------\n\nsolucionesEscalada :: Int -> Int -> [[Estado]]\nsolucionesEscalada m n =\n  [reverse es | N es <- buscaEscalada sucesoresN\n                                      (esFinalN m n)\n                                      (inicialN m n)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    buscaAnchura :: (Eq nodo) =>\n--                    (nodo -> [nodo]) \n--                 -> (nodo -> Bool)   \n--                 -> nodo             \n--                 -> [nodo]           \n-- tal que (buscaAnchura s o e) es la lista de soluciones del problema\n-- de espacio de estado definido por la funci\u00f3n sucesores (s), el\n-- objetivo (o) y el estado inicial (e) mediante b\u00fasqueda en anchura.\n-- ---------------------------------------------------------------------\n\nbuscaAnchura :: (Eq nodo) =>\n                (nodo -> [nodo]) -- sucesores\n             -> (nodo -> Bool)   -- esFinal\n             -> nodo             -- nodo actual\n             -> [nodo]           -- soluciones\nbuscaAnchura sucesores esFinal x = busca' (inserta x vacia) \n where\n   busca' p  \n    | esVacia p = [] \n    | esFinal y = y : busca' (resto p)\n    | otherwise = busca' (foldr inserta (resto p) (sucesores y))\n     where y = primero p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    solucionesAnchura :: Int -> Int -> [[Estado]]\n-- tal que (solucionesAnchura m n) es la lista de las soluciones del problema\n-- de las dichas obtenidas con el patr\u00f3n buscaAnchura (que realiza la\n-- b\u00fasqueda en profundidad). Por ejemplo,\n--    ghci> mapM_ print (zip [0..] (head (solucionesAnchura 2 2)))\n--    (0,[B,B,H,V,V])\n--    (1,[B,B,V,V,H])\n--    (2,[B,H,V,V,B])\n--    (3,[B,V,V,H,B])\n--    (4,[H,V,V,B,B])\n--    (5,[V,V,H,B,B])\n--    \n--    ghci> length (head (solucionesAnchura 3 2))\n--    8\n--    (0.22 secs, 100,912,336 bytes)\n--    ghci> length (head (solucionesEE 3 2))\n--    37\n--    (0.01 secs, 878,992 bytes)\n--    ghci> length (head (solucionesPM 3 2))\n--    11\n--    (0.01 secs, 826,824 bytes)\n--    \n--    ghci> import System.Timeout\n--    (0.00 secs, 0 bytes)\n--    ghci> timeout (2*10^6) (return $! length (head (solucionesAnchura 3 3)))\n--    Nothing\n--    (2.03 secs, 1,246,161,256 bytes)\n--    ghci> timeout (10*10^6) (return $! length (head (solucionesAnchura 3 3)))\n--    Nothing\n--    (9.91 secs, 4,846,262,912 bytes)\n--    ghci> timeout (10*10^6) (return $! length (head (solucionesEE 3 3)))\n--    Just 82\n--    (0.04 secs, 2,649,472 bytes)\n--    ghci> timeout (10*10^6) (return $! length (head (solucionesPM 3 3)))\n--    Just 18\n--    (0.01 secs, 1,051,912 bytes)\n-- ---------------------------------------------------------------------\n\nsolucionesAnchura :: Int -> Int -> [[Estado]]\nsolucionesAnchura m n =\n  [reverse es | N es <- buscaAnchura sucesoresN (esFinalN  m n) (inicialN m n)]\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\u00e1ticasse han resuelto ejercicios de la relaci\u00f3n 44 en el que se aplican los patrones de busqueda en profundidad, en anchura, primero el mejor y en escalada para resolver el provlema de las fichas y comparar las soluciones obtenidas&#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":[320],"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\/6702"}],"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=6702"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6702\/revisions"}],"predecessor-version":[{"id":6703,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6702\/revisions\/6703"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}