jueves, 28 de mayo de 2009

Camino de coste mínimo en un grafo multietapa.

Un grafo multietapa G = {N, A} es un grafo dirigido en el que se puede hacer una partición del conjunto de nodos o vértices N en k(≥ 2) conjuntos disjuntos Ci , 1 ≤ i ≤ k, donde todo arco del grafo (n, m) es tal que n pertenece a Ci y m pertenece a Ci+1 para algún i, 1 ≤ i ≤ k − 1. El coste de cada arco (i, j) lo proporciona la función c. Los conjuntos C1 y Ck tienen un sólo nodo, llamándose al primero nodo origen (o) y al segundo nodo destino (d). Si el número de conjuntos Ci es k se dice que es un grafo k-etapa.
El problema consiste en encontrar un camino de coste mínimo que vaya desde el nodo origen o al nodo destino d. Por las restricciones impuestas, un camino de coste mínimo tendrá exactamente un sólo nodo en cada conjunto Ci , de ahí que cada Ci defina una etapa del grafo. También puede decirse que cada arco del camino une una etapa con la siguiente.
Este problema tiene gran importancia en la práctica ya que muchos de los problemas de reparto óptimo de recursos pueden formularse en términos de un grafo multietapa.
Veamos cómo aplicar programación dinámica a esta situación:
Se satisface el principio de optimalidad ya que el camino de coste mínimo debe contener subcaminos de coste mínimo; en caso contrario, podrá sustituirse dichos subcaminos por otros mejores, resultando un camino total de coste menor. Además, la solución final será una secuencia de decisiones, y cada decisión depende del resultado de otras. En general, la i-ésima decisión consiste en determinar, a partir de un nodo ni de Ci , un arco que tenga a ni como nodo origen y a algún ni+1 de Ci+1 como nodo destino, siendo 1 ≤ i ≤ k − 2. El número mínimo de decisiones para un grafo k-etapa es k − 2 ya que cada camino consta de k − 1 arcos, y el ultimo queda determinado por la decisión tomada en la etapa anterior.

Sea CA(i, j) un camino de coste mínimo COST E(i, j) desde el nodo origen o hasta el nodo j de Ci . Usando una formulación hacia atrás tenemos




De igual forma, podemos analizar el coste mediante una formulación hacia adelante:
Si CA(i, j) es un camino de coste mínimo COSTE(i, j) desde el nodo j del conjunto Ci hasta el nodo destino d , entonces:



En general, se podrán utilizar indistintamente cualquiera de las dos formulaciones. Veamos a continuación el algoritmo que nos permite construir la trayectoria de coste mínimo con una formulación hacia atrás. (Hemos suprimido el primer índice de la variable COSTE ya que considerábamos que no era trascendente para el algoritmo.)

algoritmo multigrafo (ENT A :arcos; k, n :entero; C :tabla[1..n,1..n]; SAL P :tabla[1..k])
{Este algoritmo construye a partir de un grafo de k etapas, con n vértices,
conjunto de arcos A y costes C, la trayectoria P de coste mínimo}






Para estudiar la complejidad de este algoritmo hay que tener en cuenta que la complejidad del primer bucle sera O(max(n, a)) = O(n + a) siendo n el número de vértices y a el número de aristas, y la del segundo O(k), donde k siempre es menor que n. Por tanto, la complejidad total del algoritmo es O(n + a).

No hay comentarios:

Publicar un comentario en la entrada