Page 95 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 4.1. Gráfica de cinco etapas (Horowitz y Sahni, 1978)

Una formulación de programación dinámica para un problema gráfico de k etapas se obtiene, pri-
mero, al darse cuenta de que todos los caminos de s a t son el resultado de una secuencia de k-2
decisiones. La i-ésima decisión consiste en determinar cuál vértice en V , 1 ≤ i ≤ k – 2 va a estar en
i+1
el trayecto. Es fácil de observar que el principio de optimización se cumple. Sea COSTO(i, j) (donde i
indica la etapa y j determina el número de nodo) el costo de este trayecto. Usando el enfoque hacia
adelante, se obtiene:

Resolviendo la gráfica de cinco etapas indicada en la figura 4.1, se obtienen los siguientes valores:

COSTO (3,6) = min {6 + COSTO (4,9), 5 + COSTO (4,10)} = min {6+4, 5+2} = 7

COSTO (3,7) = min {4 + COSTO (4,9), 3 + COSTO (4,10)} = min {4+4, 3+2} = 5

COSTO (3,8) = min {5 + COSTO (4,10), 6 + COSTO (4,11)} = min {5+2, 6+5} = 7

COSTO (2,2) = min {4 + COSTO (3,6), 2+COSTO (3,7), 1+ COSTO (3,8)} = 7
COSTO (2,3) = 9

COSTO (2,4) = 18
COSTO (2,5) = 15

COSTO (1,1) = min {9+COSTO (2,2), 7 + COSTO (2,3), 3+COSTO(2,4), 2+COSTO(2,5)}=16.
Por lo anterior, el mínimo costo de s a t es 16.

89