Máximo de las sumas de los caminos en una matriz
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
1, 7, 3, 8, 4, 9 1, 7, 12, 8, 4, 9 1, 7, 12, 3, 4, 9 1, 7, 12, 3, 8, 9 1, 6, 12, 8, 4, 9 1, 6, 12, 3, 4, 9 1, 6, 12, 3, 8, 9 1, 6, 11, 3, 4, 9 1, 6, 11, 3, 8, 9 1, 6, 11, 2, 8, 9 |
Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.
Definir la función
|
1 |
maximaSuma :: Matrix Int -> Int |
tal que (maximaSuma m) es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
|
1 2 3 4 |
λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) 41 λ> maximaSuma (fromList 800 800 [1..]) 766721999 |
Nota: Se recomienda usar programación dinámica.
Soluciones
|
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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
import Data.Matrix -- 1ª definición -- ============= maximaSuma1 :: Matrix Int -> Int maximaSuma1 = maximum . map sum . caminos1 caminos1 :: Matrix Int -> [[Int]] caminos1 m = map reverse (caminos1Aux m (nf,nc)) where nf = nrows m nc = ncols m -- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p -- desde la posición (1,1) hasta la posición x. Por ejemplo, caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]] caminos1Aux m (1,1) = [[m!(1,1)]] caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]] caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]] caminos1Aux m (i,j) = [m!(i,j) : xs | xs <- caminos1Aux m (i,j-1) ++ caminos1Aux m (i-1,j)] -- 2ª definición -- ============= maximaSuma2 :: Matrix Int -> Int maximaSuma2 = maximum . map sum . caminos2 caminos2 :: Matrix Int -> [[Int]] caminos2 m = map reverse (matrizCaminos m ! (nrows m, ncols m)) matrizCaminos :: Matrix Int -> Matrix [[Int]] matrizCaminos m = q where q = matrix (nrows m) (ncols m) f f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]] f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]] f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- 3ª definicion (por recursión, sin calcular el camino) -- ===================================================== maximaSuma3 :: Matrix Int -> Int maximaSuma3 m = maximaSuma3Aux m (nf,nc) where nf = nrows m nc = ncols m -- (maximaSuma3Aux m p) calcula la suma máxima de un camino hasta la -- posición p. Por ejemplo, -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,4) -- 41 -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (3,3) -- 32 -- λ> maximaSuma3Aux (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) (2,4) -- 31 maximaSuma3Aux :: Matrix Int -> (Int,Int) -> Int maximaSuma3Aux m (1,1) = m ! (1,1) maximaSuma3Aux m (1,j) = maximaSuma3Aux m (1,j-1) + m ! (1,j) maximaSuma3Aux m (i,1) = maximaSuma3Aux m (i-1,1) + m ! (i,1) maximaSuma3Aux m (i,j) = max (maximaSuma3Aux m (i,j-1)) (maximaSuma3Aux m (i-1,j)) + m ! (i,j) -- 4ª solución (mediante programación dinámica) -- ============================================ maximaSuma4 :: Matrix Int -> Int maximaSuma4 m = q ! (nf,nc) where nf = nrows m nc = ncols m q = matrizMaximaSuma m -- (matrizMaximaSuma m) es la matriz donde en cada posición p se -- encuentra el máxima de las sumas de los caminos desde (1,1) a p en la -- matriz m. Por ejemplo, -- λ> matrizMaximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) -- ( 1 7 18 20 ) -- ( 8 20 23 31 ) -- ( 11 28 32 41 ) matrizMaximaSuma :: Matrix Int -> Matrix Int matrizMaximaSuma m = q where nf = nrows m nc = ncols m q = matrix nf nc f where f (1,1) = m ! (1,1) f (1,j) = q ! (1,j-1) + m ! (1,j) f (i,1) = q ! (i-1,1) + m ! (i,1) f (i,j) = max (q ! (i,j-1)) (q ! (i-1,j)) + m ! (i,j) -- Comparación de eficiencia -- ========================= -- λ> maximaSuma1 (fromList 8 8 [1..]) -- 659 -- (0.11 secs, 31,853,136 bytes) -- λ> maximaSuma1a (fromList 8 8 [1..]) -- 659 -- (0.09 secs, 19,952,640 bytes) -- -- λ> maximaSuma1 (fromList 10 10 [1..]) -- 1324 -- (2.25 secs, 349,722,744 bytes) -- λ> maximaSuma2 (fromList 10 10 [1..]) -- 1324 -- (0.76 secs, 151,019,296 bytes) -- -- λ> maximaSuma2 (fromList 11 11 [1..]) -- 1781 -- (3.02 secs, 545,659,632 bytes) -- λ> maximaSuma3 (fromList 11 11 [1..]) -- 1781 -- (1.57 secs, 210,124,912 bytes) -- -- λ> maximaSuma3 (fromList 12 12 [1..]) -- 2333 -- (5.60 secs, 810,739,032 bytes) -- λ> maximaSuma4 (fromList 12 12 [1..]) -- 2333 -- (0.01 secs, 23,154,776 bytes) |
2 Comentarios