Camino de coste mínimo entre dos nodos de un grafo dirigido

De Wikipedia, la enciclopedia libre

Tabla de contenidos 1 Descripción detallada del problema 2 Estrategia de resolución 3 Implementación en Pseudocódigo 3.1 Coste 4 Modificaciones del algoritmo 5 Implementación en Pseudocódigo del algoritmo modificado 5.1 Llamada inicial 6 Referencias

[editar] Descripción detallada del problema

A lo largo del río hay n poblados, en cada poblado se puede alquilar una canoa, la cual puede devolverse en cualquier otro poblado que esté a favor de la corriente. El coste del alquiler desde un poblado i hasta otro j puede resultar mayor que el coste total de una serie de alquileres más breves. En tal caso, es más rentable devolver la primera canoa en algún poblado k entre i y j, y seguir camino en una segunda canoa, sin cargos adicionales por cambiar de canoa.

[editar] Estrategia de resolución

Buscamos un algoritmo eficiente para determinar el coste mínimo de un viaje en canoa desde todos los posibles puntos de partida i hasta todos los posibles puntos de llegada j.

Desde un poblado i solo se puede ir a poblados más abajo en el río. Suponemos que están numerados de menor a mayor en el sentido de la corriente. La información dada es el coste de un alquiler desde i hasta j para todo posible punto de partida i y para todo posible punto de llegada j > i.

• alquiler[i, j] = coste de una canoa para ir directamente desde i hasta j.

Se trata de un caso particular del problema de caminos mínimos, resoluble mediante el algoritmo de Floyd. Vamos a presentar un algoritmo más específico. Para calcular el mejor coste para ir desde el poblado i al poblado j planteamos una función recursiva que compruebe todas las posibilidades:

• coste(i, i + 1) = alquiler[i, i + 1].

Cuando los poblados no son consecutivos, tenemos también la posibilidad de hacer paradas intermedias para cambiar de canoa. Tenemos que contemplar la posibilidad de parar en cualquiera de los poblados k entre i y j, y si pasamos por k, la parte del camino que va de i a k y la parte del camino que va de k a j también tienen que ser óptimas porque la suma de costes sea óptima, también han de serlo los sumandos. Por tanto, se cumple el principio de optimalidad y podemos plantear la siguiente recurrencia:

• coste(i, j) = min{alquiler[i, j], min(i<k<j) {coste(i, k) + coste(k, j)}} si i < j – 1

La recursión está bien fundada, en el sentido de que el número de posibles paradas intermedias (j – i) siempre decrece.

Utilizaremos una matriz coste [1..n, 1..n] para calcular los valores coste (i, j), de la cual solo necesitaremos la mitad superior por encima de la diagonal principal. Podemos rellenar la matriz por diagonales, para lo que necesitamos numerar las diagonales (desde d = 1 hasta d = n – 1) y los elementos dentro de una diagonal (la fila va desde el i = 1 al i = n – d, y la columna podemos calcularla como j = i + d).

[editar] Implementación en Pseudocódigo

Podemos ver que d = 1 es el caso básico (la primera diagonal encima de la principal). El algoritmo que implementa todas estas ideas es el siguiente:

 fun canoas1 (alquiler[1..n, 1..n] de real+) dev coste[1..n,1..n] de real+
   {inicialización}
   coste := alquiler;
   para d = 2 hasta n – 1 hacer {recorrer diagonales}
     para i = 1 hasta n – d hacer {recorrer elementos de la diagonal}
       j := i + d;
       {cálculo del mínimo}
       para k = i + 1 hasta j – 1 hacer
         coste[i, j] := min(coste[i, j], coste[i, k] + coste[k, j]);
       fpara
     fpara
   fpara
 ffun

El mínimo entre no parar y sí parar se calcula inicializando la matriz coste con alquiler y después minimizando (bucle para k).

[editar] Coste

A pesar de que los caminos estén orientados (no se puede retroceder) el coste del algoritmo sigue estando en θ (n3) y su espacio adicional en θ (1).

[editar] Modificaciones del algoritmo

Ahora podemos modificar el algoritmo anterior para que, además, nos proporcione un plan de alquileres para viajar desde el primer poblado (el más cercano al nacimiento del río) hasta el último (el más cercano a la desembocadura).

Para obtener un plan de alquileres, necesitamos una matriz adicional camino [1..n, 1..n] que indique el poblado de intercambio de canoa que permite obtener un mínimo coste. Esta matriz se inicializa con ceros, que indican que de momento no hay poblado intermedio, y se irá modificando junto con coste.

[editar] Implementación en Pseudocódigo del algoritmo modificado

 fun canoas2 (alquiler[1..n, 1..n] de real +) dev <coste[1..n, 1..n] de real+, camino[1..n, 1..n] de 0..n>
   coste := alquiler;
   camino[1..n, 1..n] := [0];
   para d = 2 hasta n – 1 hacer {recorrer diagonales}
     para i = 1 hasta n – d hacer {recorrer elementos de la diagonal}
       j := i + d;
       para k = i + 1 hasta j - 1 hacer
         temp := coste[i, k] + coste[k, j]
         si temp < coste[i, j] entonces
           coste[i, j] := temp;
           camino[i, j] := k;
         fsi
       fpara
     fpara
   fpara
 ffun

Su coste es el mismo que el algoritmo anterior.

[editar] Llamada inicial

Para obtener el plan de alquileres entre dos poblados i y j (i < j), habrá que procesar recursivamente la información contenida en camino, siendo el caso básico cuando se alcanza el valor 0.

 proc plan (e camino[1..n, 1..n] de 0..n, e i, j: 1..n)
   k := camino[i, j];
   si k <> 0 entonces
     plan(camino, i, k);
     imprimir(k);
     plan(camino, k, i);
   fsi
 fproc

Para obtener lo pedido hacemos:

imprimir(1); plan(camino, 1, n); imprimir(n);

[editar] Referencias

• Martí Oliet, N,; Ortega Mallén, Y.; Verdejo López, J.A.; ESTRUCTURAS DE DATOS Y MÉTODOS ALGORÍTMICOS. Ejercicios resueltos. Pearson Education 2004