Simulacion

EL VIAJE MÁS BARATO POR RÍO

Sobre el río Guadalhorce hay n embarcaderos. En cada uno de ellos se puede

alquilar un bote que permite ir a cualquier otro embarcadero río abajo (es imposible

ir río arriba). Existe una tabla de tarifas que indica el coste del viaje del

embarcadero i al j para cualquier embarcadero de partida i y cualquier embarcadero

de llegada j más abajo en el río (i < j). Puede suceder que un viaje de i a j sea más

caro que una sucesión de viajes más cortos, en cuyo caso se tomaría un primer bote

hasta un embarcadero k y un segundo bote para continuar a partir de k. No hay

coste adicional por cambiar de bote.

Nuestro problema consiste en diseñar un algoritmo eficiente que determine el

coste mínimo para cada par de puntos i,j (i < j) y determinar, en función de n, el

tiempo empleado por el algoritmo.

Solución

Para resolverla según la técnica de Programación Dinámica, hace falta utilizar

una estructura para almacenar resultados intermedios y evitar la repetición de los

cálculos. La estructura que usaremos es una matriz triangular de costes C[i,j], que

iremos rellenando por diagonales mediante el procedimiento que hemos

denominado Costes. La solución al problema es la propia tabla, y sus valores C [i, j]

indican el coste óptimo para ir del embarcadero i al j.

CONST MAXEMBARCADEROS =...;

TYPE MATRIZ=ARRAY [1...MAXEMBARCADEROS], [1...MAXEMBARCADEROS] OF CARDINAL;

PROCEDURE Costes (VAR C: MATRIZ; n: CARDINAL);

VAR i, diagonal: CARDINAL;

BEGIN

FOR i:=1 TO n DO C [i, i]:=0 END; (* condiciones iniciales *)

FOR diagonal:=1 TO n-1 DO

FOR i:=1 TO n-diagonal DO

C [i, diagonal]:=Min(C, i, diagonal)

END

END

END Costes;

Dicho procedimiento utiliza la siguiente función, que permite calcular la

expresión del mínimo que aparece en la ecuación en recurrencia [5.2]:

PROCEDURE Min (VAR C: MATRIZ; i, j: CARDINAL): CARDINAL;

VAR k, min: CARDINAL;

BEGIN

Min:=MAX (CARDINAL);

FOR k:=i+1 TO j DO

min:=Min2(Minot[i,k] + C[k,j])

END;

RETURN min

END Min;

La función Min2 es la que calcula el mínimo de dos números naturales. Es

importante observar que esta función, por la forma en que se va rellenando la

matriz C, sólo hace uso de los elementos calculados hasta el momento.

La complejidad del algoritmo es de orden O(n3), pues está compuesto por dos

bucles anidados de tamaño n, que contienen la llamada a una función de orden

O(n), la que calcula el mínimo.

...