Siguiente:Características ComunesArriba:Tutorial Anterior:Primer Ejemplo

Segundo Ejemplo

Programación Dinámica tiene similitudes con PERT/CPM y con algoritmos específicos de grafos, como por ejemplo el algoritmo de la ruta más corta.
Veamos el siguiente problema de la ruta más corta. Suponga que se desea ir desde A hasta J en la carretera mostrada en la red de la figura 2.

Figura 2: Red Carreteras

Los números en los arcos representan las distancias. Debido a la estructura especial del problema, éste se puede dividir en niveles. El nivel 1 contiene el nodo A, nivel 2 los nodos B,C y D, el nivel 3 contiene los nodos E, F y G, el nivel 4 contiene H e I y el nivel 5 contiene el nodo J. Los estados en cada nivel corresponden a los nombres de los nodos. Así, el nivel 3 contiene los estados E, F y G.

Sea S un nodo en el nivel  j y sea  la distancia más corta desde el nodo S al destino J, se puede escribir

donde  denota el largo del arco SZ. Esto nos da la recursividad para poder resolver el problema. Se parte entonces con  .
A continuación se muestra el resto de los cálculos:

Nivel  4.

En el nivel 4, realmente no hay decisiones que tomar, hay que ir hasta el destino J.

• para ir a J,
•   para ir a J.

Nivel 3.

Aquí hay más decisiones. Calcular  . Desde F se puede ir a H o a I. El costo inmediato de ir de H es 6. El siguiente costo es  . El costo total es 9. El costo inmediato de ir a I es 3. El siguiente costo es  con un total de 7. Luego, encontrándose en F la mejor decisión a tomar es ir a I. Con un costo total de 7, así  .

 

 
 
 
 
 

La siguiente tabla resume los otros cálculos:

 
 

Se calcula hacia atrás nivel por nivel, cada vez completando el cálculo por nivel antes de continuar al nivel que lo precede. Los resultados son:

Nivel 2.

 

 
 
 
 
 

Nivel  1.

 

 
 
 
 
 

 
 

Siguiente:Características ComunesArriba:Tutorial Anterior:Primer Ejemplo