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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

• La solución al problema ha de ser alcanzada a través de una secuencia de
decisiones, una en cada etapa.

• Dicha secuencia de decisiones ha de cumplir el principio de optimalidad de
Bellman.

En general, el diseño de un algoritmo de programación dinámica consta de los siguientes pasos:

1. Planteamiento de la solución como una sucesión de decisiones y verificación
de que esta cumple el principio de optimalidad de Bellman.

2. Definición recursiva de la solución.

3. Cálculo del valor de la solución óptima mediante una tabla en la cual se alma-
cenan soluciones de problemas parciales para reutilizar los cálculos.

4. Construcción de la solución óptima usando la información contenida en la tabla
anterior.

gráfIcaS de MúltIpleS etapaS (MultIStage grapHS)

Es una gráfica dirigida en el cual los vértices son particionados en K ≥ 2 conjuntos disjuntos V, 1 ≤
i
i ≤ k (cada V es una de las etapas con una determinada cantidad de nodos). En adición, si < u, v >
i
son una arista en E, entonces u V y v V para algún i, 1 ≤ i < k. Los conjuntos V y V son tales que
i i+1 1 k
| V | = | V | =1. Sea s y t respectivamente el vértice en V y V , donde s es la fuente y t es la meta
1 k 1 k
para llegar. Sea c (i, j) el costo de la arista <i, j>. El costo del trayecto de s a t iniciando en el estado
1, va la etapa 2, posteriormente a la etapa 3, a la etapa 4, etc. Y eventualmente termina en la etapa
k. En la figura 4.1 se muestra una gráfica de cinco etapas. El trayecto de mínimo costo de s a t se
muestra en negrita.

88