Método de optimización recursiva para problemas de decisión multinivel que descompone el problema en subproblemas solapados, utiliza una representación de estado y el principio de optimalidad para expresar el valor de un estado en función de estados sucesores, y calcula políticas óptimas mediante iteración de valor o política, memorización o inducción hacia atrás.

Principio

Una solución óptima de un problema multinivel puede construirse a partir de soluciones óptimas de sus subproblemas (principio de optimalidad); por tanto, computar una función de valor sobre un espacio de estados adecuado produce decisiones globalmente óptimas cuando existen separabilidad por etapas y la propiedad de Markov.

Demostración

Escenario ilustrativo: enrutamiento de tiempo mínimo en una red dirigida acíclica. Situación: cada nodo es una etapa, las aristas tienen costos por etapa. Reconocimiento: los costos son aditivos por etapas y los costos futuros dependen solo del nodo actual. Acción: calcular el costo mínimo hasta el destino para todos los nodos por inducción hacia atrás (memorizar resultados). Consecuencia: la política calculada proporciona el camino más corto sin enumerar todas las rutas completas.

Aplicación incorrecta

Aplicar programación dinámica cuando el estado seleccionado no codifica todo el historial relevante (viola la propiedad de Markov) o cuando los subproblemas no se solapan; esto produce decisiones incorrectas o un crecimiento exponencial del espacio de estados que anula las ventajas computacionales.

Consecuencia

Si es aplicable, la programación dinámica ofrece políticas con optimalidad demostrable y reduce cálculos redundantes mediante memorización; mal aplicada, produce óptimos incorrectos o costos computacionales inabordables (maldición de la dimensionalidad).

Inversión

Si la separabilidad por etapas, la aditividad de costos o la propiedad de Markov no se cumplen (por ejemplo, cuando los costos futuros dependen de trayectorias completas o existen objetivos no separables), debe reemplazarse o complementarse por reformulación, aproximación o expansión del estado que incluya historial.

Límite

Claramente dentro: procesos de decisión markovianos de horizonte finito con costos aditivos por etapa y estados definidos. Caso límite: problemas estocásticos parcialmente observables que exigen transformar a un estado de creencias. Claramente fuera: optimización de una sola etapa sin estructura secuencial o problemas cuya óptima depende de un pasado no acotado.

Tensión semántica

Optimalidad frente a tratabilidad — lograr óptimo global exacto mediante enumeración de estados choca con límites de memoria y cálculo, forzando frecuentemente métodos aproximados.

Síntesis

La programación dinámica explota la estructura (descomposición en etapas y definición compacta del estado) para hacer un problema soluble: su eficacia depende de elegir una representación de estado que haga markovianos los costos futuros y mantenga manejable el espacio de estados.