Programación dinámica

Programación Dinámica Determinística
La programación dinámica encuentra la solución óptima de un problema con n variables descomponiéndolo en n etapas, siendo cada etapa un subproblema de una solavariable. Sin embargo, como la naturaleza de la etapa difiere de acuerdo con el problema de optimización, la programación dinámica no proporciona los detalles de cómputo para optimizar cada etapa.
Loscálculos de programación dinámica se hacen en forma recursiva, ya que la solución óptima de un subproblema se usa como dato para el siguiente subproblema. Para cuando se resuelve el últimosubproblema queda a la mano la solución óptima de todo el problema. En particular, los subproblemas se vinculan normalmente mediante restricciones comunes. Al pasar de un subproblema al siguiente se debemantener la factibilidad de esas restricciones comunes.
Existe la recursión en avance y la recursión en reversa; ambas recursiones producen la misma solución y no es otra cosa que el orden en el que se hande realizar los cálculos, es decir, si se va a resolver primero la etapa inicial, o si se empezará por la etapa final. Al visualizar la recursión en avance, ésta parece más lógica, sin embargo, enlas publicaciones sobre programación dinámica se usa la recursión en reversa de modo invariable. La razón de ésta preferencia es que, en general, la recursión en reversa es más eficiente desde el puntode vista computacional.
Problema de Aplicación (Problema de la ruta más corta)
Se trata de seleccionar la ruta más corta entre dos ciudades. La siguiente red muestra las rutas posibles entre elinicio en el nodo 1 y el destino en el nodo 7. Las rutas pasan por ciudades intermedias, representadas por los nodos 2 a 6.

Para resolver el problema con programación dinámica e descomponer el problemaen etapas. A continuación se hacen los cálculos para cada etapa por separado.

Resultados de la etapa 1
Distancia más corta al nodo 2 = 5 millas (de nodo 1)
Distancia más corta al nodo 3 = 9...