Algoritmos y Estructuras de Datos (VJ1215)

Si a > 0, hasta la aldea a se puede llegar alquilando una barca desde la aldea i con un coste costeAlquiler[i][a], para cada i entre 0 y a - 1, ambos inclusive. Hemos de elegir la mejor de esas opciones, y para ello necesitamos saber cuál es el mínimo coste de llegar desde la primera aldea hasta cada una de esas aldeas anteriores. Eso lo podemos calcular recursivamente.

Para cualquier aldea a, sea mínimoCoste(a) el coste mínimo para llegar desde la aldea 0 hasta la aldea a. El resultado que nos piden es mínimoCoste(n - 1).

Si a = 0,
   mínimoCoste(a) = 0

Si a > 0,
   mínimoCoste(a) = min( {mínimoCoste(i) + costeAlquiler[i][a] : i = 0, ..., a - 1} )
	

Por ejemplo, con 7 aldeas:

mínimoCoste(6) = min( {mínimoCoste(5) + costeAlquiler[5][6],
                       mínimoCoste(4) + costeAlquiler[4][6],
                       mínimoCoste(3) + costeAlquiler[3][6],
                       mínimoCoste(2) + costeAlquiler[2][6],
                       mínimoCoste(1) + costeAlquiler[1][6],
                       mínimoCoste(0) + costeAlquiler[0][6]} )

mínimoCoste(5) = min( {mínimoCoste(4) + costeAlquiler[4][5],
                       mínimoCoste(3) + costeAlquiler[3][5],
                       mínimoCoste(2) + costeAlquiler[2][5],
                       mínimoCoste(1) + costeAlquiler[1][5],
                       mínimoCoste(0) + costeAlquiler[0][5]} )

...

mínimoCoste(2) = min( {mínimoCoste(1) + costeAlquiler[1][2],
                       mínimoCoste(0) + costeAlquiler[0][2]} )

mínimoCoste(1) = min( {mínimoCoste(0) + costeAlquiler[0][1]} )
               = costeAlquiler[0][1]

mínimoCoste(0) = 0
	

En ese cálculo recursivo hay cálculos que se repiten, y de ahí el interés de añadir una tabla para guardar mínimoCoste(a).

Sea u = n - 1 la última aldea.

Si a < u, desde la aldea a se puede alquilar una barca para llegar hasta la aldea i con un coste costeAlquiler[a][i], para cada i entre a + 1 y u, ambos inclusive. Hemos de elegir la mejor de esas opciones, y para ello necesitamos saber cuál es el mínimo coste de llegar desde cada una de esas aldeas posteriores hasta la última aldea. Eso lo podemos calcular recursivamente.

Para cualquier aldea a, sea mínimoCoste(a) el coste mínimo para llegar desde la aldea a hasta la aldea u. El resultado que nos piden es mínimoCoste(0).

Si a = u,
   mínimoCoste(a) = 0

Si a < u,
   mínimoCoste(a) = min( {mínimoCoste(i) + costeAlquiler[a][i] : i = a + 1, ..., u} )
	

Por ejemplo, con 7 aldeas:

mínimoCoste(0) = min( {mínimoCoste(1) + costeAlquiler[0][1],
                       mínimoCoste(2) + costeAlquiler[0][2],
                       mínimoCoste(3) + costeAlquiler[0][3],
                       mínimoCoste(4) + costeAlquiler[0][4],
                       mínimoCoste(5) + costeAlquiler[0][5],
                       mínimoCoste(6) + costeAlquiler[0][6]} )

mínimoCoste(1) = min( {mínimoCoste(2) + costeAlquiler[1][2],
                       mínimoCoste(3) + costeAlquiler[1][3],
                       mínimoCoste(4) + costeAlquiler[1][4],
                       mínimoCoste(5) + costeAlquiler[1][5],
                       mínimoCoste(6) + costeAlquiler[1][6]} )

...

mínimoCoste(4) = min( {mínimoCoste(5) + costeAlquiler[4][5],
                       mínimoCoste(6) + costeAlquiler[4][6]} )

mínimoCoste(5) = min( {mínimoCoste(6) + costeAlquiler[5][6]} )
               = costeAlquiler[5][6]

mínimoCoste(6) = 0
	

En ese cálculo recursivo hay cálculos que se repiten, y de ahí el interés de añadir una tabla para guardar mínimoCoste(a).