Procedimiento de solución Ejemplo prototipo (VI)

En este punto se puede identificar la solución óptima. Los resultados del problema para n=1 indican que el cazafortunas debe elegir como primer destino inmediato el estado C o el estado D. Supóngase que elige xi* = C. Con n = 2, el resultado para s = C es x2* = E. Este resultado conduce al problema con n =3, que da x3* = H para s = E y el problema con n = 4 indica que x*4 = J para s = H. Así, una ruta óptima es A →D→E → H → J y A → D → F → I → J. Todas tienen un costo total de f1*(A) = 11.

En la siguiente sección se verá que los términos especiales que describen el contexto particular de este problema - etapa, estado, política- en realidad son parte de la terminología general de programación dinámica con una interpretación análoga en otros contextos.