Caminos en una retícula (con programación dinámica)
Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3×4 se numera como sigue:
|
1 2 3 4 5 |
|-------+-------+-------+-------| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3) | (3,4) | |-------+-------+-------+-------| |
Definir la función
|
1 |
caminos :: (Int,Int) -> [[(Int,Int)]] |
tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
λ> caminos (2,3) [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] λ> mapM_ print (caminos (3,4)) [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)] [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)] [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)] [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
module Programacion_dinamica_Caminos_en_una_reticula where import Data.Array (Array, (!), array) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª solución (por recursión) -- =========================== caminos1 :: (Int,Int) -> [[(Int,Int)]] caminos1 p = map reverse (caminos1Aux p) where caminos1Aux (1,y) = [[(1,z) | z <- [y,y-1..1]]] caminos1Aux (x,1) = [[(z,1) | z <- [x,x-1..1]]] caminos1Aux (x,y) = [(x,y) : cs | cs <- caminos1Aux (x-1,y) ++ caminos1Aux (x,y-1)] -- 2ª solución (con programación dinámica) -- ======================================= caminos2 :: (Int,Int) -> [[(Int,Int)]] caminos2 p = map reverse (matrizCaminos p ! p) matrizCaminos :: (Int,Int) -> Array (Int,Int) [[(Int,Int)]] matrizCaminos (m,n) = q where q = array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]] f 1 y = [[(1,z) | z <- [y,y-1..1]]] f x 1 = [[(z,1) | z <- [x,x-1..1]]] f x y = [(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> maximum (head (caminos1 (2000,2000))) -- (2000,2000) -- (0.01 secs, 3,459,576 bytes) -- λ> maximum (head (caminos2 (2000,2000))) -- (2000,2000) -- (2.79 secs, 1,507,636,688 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ caminos1 (2,3) `shouldBe` [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] it "e2" $ caminos2 (2,3) `shouldBe` [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0010 seconds -- 2 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
from collections import defaultdict from sys import setrecursionlimit from timeit import Timer, default_timer setrecursionlimit(10**6) # 1ª solución (por recursión) # =========================== def caminos1(p: tuple[int, int]) -> list[list[tuple[int, int]]]: def aux(p: tuple[int, int]) -> list[list[tuple[int, int]]]: (x, y) = p if x == 1: return [[(1,z) for z in range(y, 0, -1)]] if y == 1: return [[(z,1) for z in range(x, 0, -1)]] return [[(x,y)] + cs for cs in aux((x-1,y)) + aux((x,y-1))] return [list(reversed(ps)) for ps in aux(p)] # 2ª solución (con programación dinámica) # ======================================= def caminos2(p: tuple[int, int]) -> list[list[tuple[int, int]]]: return [list(reversed(ps)) for ps in diccionarioCaminos(p)[p]] # diccionarioCaminos((m,n)) es el diccionario cuyas claves son los # puntos de la retícula mxn y sus valores son los caminos a dichos # puntos. Por ejemplo, # >>> diccionarioCaminos((2,3)) # defaultdict(<class 'list'>, # {(1,1): [[(1,1)]], # (1,2): [[(1,2),(1,1)]], # (1,3): [[(1,3),(1,2),(1,1)]], # (2,1): [[(2,1),(1,1)]], # (2,2): [[(2,2),(1,2),(1,1)], # [(2,2),(2,1),(1,1)]], # (2,3): [[(2,3),(1,3),(1,2),(1,1)], # [(2,3),(2,2),(1,2),(1,1)], # [(2,3),(2,2),(2,1),(1,1)]]}) def diccionarioCaminos(p: tuple[int, int]) -> dict[tuple[int, int], list[list[tuple[int, int]]]]: m, n = p q = defaultdict(list) for i in range(1, m + 1): for j in range(1, n + 1): if i == 1: q[(i, j)] = [[(1, z) for z in range(j, 0, -1)]] elif j == 1: q[(i, j)] = [[(z, 1) for z in range(i, 0, -1)]] else: q[(i, j)] = [[(i, j)] + cs for cs in q[(i-1, j)] + q[(i, j-1)]] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('max(caminos1((13,13))[0])') # 26.75 segundos # >>> tiempo('max(caminos2((13,13))[0])') # 7.40 segundos # Verificación # ============ def test_caminos() -> None: assert caminos1((2,3)) == \ [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] assert caminos2((2,3)) == \ [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] print("Verificado") # La verificación es # >>> test_caminos() # Verificado |