{"id":5999,"date":"2018-03-21T16:55:58","date_gmt":"2018-03-21T15:55:58","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5999"},"modified":"2018-03-23T16:56:51","modified_gmt":"2018-03-23T15:56:51","slug":"i1m2017-programacion-dinamica-caminos-en-una-reticula","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-programacion-dinamica-caminos-en-una-reticula\/","title":{"rendered":"I1M2017: Programaci\u00f3n din\u00e1mica: Caminos en una ret\u00edcula"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 29, en el que se comparan distintas soluciones del problema de calcular los caminos en una ret\u00edcula. Se ha mostrado como transformar las definiciones recursivas en definiciones con programaci\u00f3n din\u00e1mica. Adem\u00e1s, se han comparado experimentalmente la eficiencia de las distintas definiciones.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List (genericLength)\nimport Data.Matrix\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Se considera una ret\u00edcula con sus posiciones numeradas,\n-- desde el v\u00e9rtice superior izquierdo, hacia la derecha y hacia\n-- abajo. Por ejemplo, la ret\u00edcula de dimensi\u00f3n 3x4 se numera como sigue:\n--    |-------+-------+-------+-------|\n--    | (1,1) | (1,2) | (1,3) | (1,4) |\n--    | (2,1) | (2,2) | (2,3) | (2,4) |\n--    | (3,1) | (3,2) | (3,3) | (3,4) |\n--    |-------+-------+-------+-------|\n--\n-- Definir, por recursi\u00f3n, la funci\u00f3n\n--    caminosR :: (Int,Int) -> [[(Int,Int)]]\n-- tal que (caminosR (m,n)) es la lista de los caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n--    \u03bb> caminosR (2,3)\n--    [[(1,1),(1,2),(1,3),(2,3)],\n--     [(1,1),(1,2),(2,2),(2,3)],\n--     [(1,1),(2,1),(2,2),(2,3)]]\n--    \u03bb> mapM_ print (caminosR (3,4))\n--    [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]\n--    [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]\n--    [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]\n--    [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]\n--    [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]\n--    [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]\n--    [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]\n--    [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]\n--    [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]\n--    [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]\n-- ---------------------------------------------------------------------\n\ncaminosR :: (Int,Int) -> [[(Int,Int)]]\ncaminosR p =\n  map reverse (caminosRAux p)\n  where \n    caminosRAux (1,y) = [[(1,z) | z <- [y,y-1..1]]]\n    caminosRAux (x,1) = [[(z,1) | z <- [x,x-1..1]]]\n    caminosRAux (x,y) = [(x,y) : cs | cs <- caminosRAux (x-1,y) ++ \n                                            caminosRAux (x,y-1)]  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    caminosPD :: (Int,Int) -> [[(Int,Int)]]\n-- tal que (caminosPD (m,n)) es la lista de los caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n).\n-- ---------------------------------------------------------------------\n\ncaminosPD :: (Int,Int) -> [[(Int,Int)]]\ncaminosPD p =\n  map reverse (matrizCaminos p ! p)\n\nmatrizCaminos :: (Int,Int) -> Matrix [[(Int,Int)]]\nmatrizCaminos (m,n) = q\n  where\n    q = matrix m n f\n    f (1,y) = [[(1,z) | z <- [y,y-1..1]]]\n    f (x,1) = [[(z,1) | z <- [x,x-1..1]]]\n    f (x,y) = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)]  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones \n--    length (head (caminosR (8,8)))\n--    length (head (caminosR (8,8)))\n--    maximum (head (caminosR (2000,2000)))\n--    maximum (head (caminosPD (2000,2000)))\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (head (caminosR (8,8)))\n--    15\n--    (1.62 secs, 1,609,566,528 bytes)\n--    \u03bb> length (head (caminosR (8,8)))\n--    15\n--    (0.00 secs, 0 bytes)\n--    \n--    \u03bb> maximum (head (caminosR (2000,2000)))\n--    (2000,2000)\n--    (0.02 secs, 0 bytes)\n--    \u03bb> maximum (head (caminosPD (2000,2000)))\n--    (2000,2000)\n--    (1.30 secs, 199,077,664 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Definir, usando caminosR, la funci\u00f3n\n--    nCaminosCR :: (Int,Int) -> Integer\n-- tal que (nCaminosCR (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n--      nCaminosR (2,3)                        ==  3\n--      nCaminosR (3,4)                        ==  10\n-- ---------------------------------------------------------------------\n\nnCaminosCR :: (Int,Int) -> Integer\nnCaminosCR = genericLength . caminosR\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Definir, usando caminosPD, la funci\u00f3n\n--    nCaminosCPD :: (Int,Int) -> Integer\n-- tal que (nCaminosCPD (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n-- ---------------------------------------------------------------------\n\nnCaminosCPD :: (Int,Int) -> Integer\nnCaminosCPD = genericLength . caminosPD\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.3. Definir, por recursi\u00f3n, la funci\u00f3n\n--    nCaminosR :: (Int,Int) -> Integer\n-- tal que (nCaminosR (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n-- ---------------------------------------------------------------------\n\nnCaminosR :: (Int,Int) -> Integer\nnCaminosR (1,_) = 1 \nnCaminosR (_,1) = 1\nnCaminosR (x,y) = nCaminosR (x-1,y) + nCaminosR (x,y-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.4. Definir, por programaci\u00f3n din\u00e1mica, la funci\u00f3n\n--    nCaminosPD :: (Int,Int) -> Integer\n-- tal que (nCaminosPD (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n-- ---------------------------------------------------------------------\n\nnCaminosPD :: (Int,Int) -> Integer\nnCaminosPD p = matrizNCaminos p ! p\n\nmatrizNCaminos :: (Int,Int) -> Matrix Integer\nmatrizNCaminos (m,n) = q\n  where\n    q = matrix m n f\n    f (1,_) = 1\n    f (_,1) = 1\n    f (x,y) = q!(x-1,y) + q!(x,y-1)  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.5. Los caminos desde (1,1) a (m,n) son las permutaciones\n-- con repetici\u00f3n de m-1 veces la A (abajo) y n-1 veces la D\n-- (derecha). Por tanto, su  n\u00famero es \n--    ((m-1)+(n-1))! \/ (m-1)!*(n-1)!\n--  \n-- Definir, con la f\u00f3rmula anterior, la funci\u00f3n\n--    nCaminosF :: (Int,Int) -> Integer\n-- tal que (nCaminosF (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n-- ---------------------------------------------------------------------\n\nnCaminosF :: (Int,Int) -> Integer\nnCaminosF (m,n) = \n  fact ((m-1)+(n-1)) `div` (fact (m-1) * fact (n-1))\n \nfact :: Int -> Integer\nfact n = product [1..fromIntegral n]\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 2.6. La f\u00f3rmula anterior para el c\u00e1lculo del n\u00famero de\n-- caminos se puede simplificar.\n--  \n-- Definir, con la f\u00f3rmula simplificada, la funci\u00f3n\n--    nCaminosFS :: (Int,Int) -> Integer\n-- tal que (nCaminosFS (m,n)) es el n\u00famero de caminos en la ret\u00edcula de\n-- dimensi\u00f3n mxn desde (1,1) hasta (m,n). Por ejemplo,\n-- ---------------------------------------------------------------------\n\nnCaminosFS :: (Int,Int) -> Integer\nnCaminosFS (m,n) = \n  product [a+1..a+b] `div` product [2..b]\n  where m' = fromIntegral (m-1)\n        n' = fromIntegral (n-1)\n        a  = max m' n'\n        b  = min m' n'\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 2.7. Comparar la eficiencia calculando el tiempo necesario\n-- para evaluar las siguientes expresiones \n--    nCaminosCR  (8,8)\n--    nCaminosCPD (8,8)\n--    nCaminosCR  (12,12)\n--    nCaminosCPD (12,12)\n--    nCaminosR   (12,12)\n--    nCaminosPD  (12,12)\n--    length (show (nCaminosPD (1000,1000)))\n--    length (show (nCaminosF  (1000,1000)))\n--    length (show (nCaminosFS (1000,1000)))\n--    length (show (nCaminosF  (2*10^4,2*10^4)))\n--    length (show (nCaminosFS (2*10^4,2*10^4)))\n-- ---------------------------------------------------------------------\n\n-- La comparaci\u00f3n es\n--    \u03bb> nCaminosCR (8,8)\n--    3432\n--    (2.11 secs, 2,132,573,904 bytes)\n--    \u03bb> nCaminosCR (8,8)\n--    3432\n--    (0.05 secs, 14,977,464 bytes)\n--    \u03bb> nCaminosCPD (8,8)\n--    3432\n--    (0.02 secs, 0 bytes)\n--    \n--    \u03bb> nCaminosCR (12,12)\n--    705432\n--    (18.24 secs, 3,778,889,608 bytes)\n--    \u03bb> nCaminosCPD (12,12)\n--    705432\n--    (3.56 secs, 548,213,968 bytes)\n--    \u03bb> nCaminosR (12,12)\n--    705432\n--    (2.12 secs, 278,911,248 bytes)\n--    \u03bb> nCaminosPD (12,12)\n--    705432\n--    (0.01 secs, 0 bytes)\n--    \n--    \u03bb> length (show (nCaminosPD (1000,1000)))\n--    600\n--    (4.88 secs, 693,774,912 bytes)\n--    \u03bb> length (show (nCaminosF (1000,1000)))\n--    600\n--    (0.01 secs, 0 bytes)\n--    \u03bb> length (show (nCaminosFS (1000,1000)))\n--    600\n--    (0.01 secs, 0 bytes)\n--    \n--    \u03bb> length (show (nCaminosF (2*10^4,2*10^4)))\n--    12039\n--    (8.01 secs, 2,376,767,288 bytes)\n--    \u03bb> length (show (nCaminosFS (2*10^4,2*10^4)))\n--    12039\n--    (2.84 secs, 836,245,992 bytes)\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\u00e1ticas se han explicado las soluciones de los ejercicios de la relaci\u00f3n 29, en el que se comparan distintas soluciones del problema de calcular los caminos en una ret\u00edcula. Se ha mostrado como transformar las definiciones recursivas en definiciones&#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":[265],"tags":[244,270,316],"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\/5999"}],"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=5999"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5999\/revisions"}],"predecessor-version":[{"id":6000,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5999\/revisions\/6000"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5999"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}