## [Programación Dinámica](/es/node/65939) Definición 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 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 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 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 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 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 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 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 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.