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

...