En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.

El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Introducción Una «subestructura óptima» implica que la solución óptima de un problema puede obtenerse a partir de las soluciones óptimas de sus subproblemas. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos: Dividir el problema en subproblemas más pequeños. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente. Usar estas soluciones óptimas para construir una solución óptima al problema original. Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Decir que un problema tiene subproblemas superpuestos es decir que se usa un mismo subproblema para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci (F3 = F1 + F2 y F4 = F2 + F3) calcular cada término supone calcular F2. Como para calcular F5 hacen falta tanto F3 como F4, una mala implementación para calcular F5 acabará calculando F2 dos o más veces. Esto sucede siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a problemas que ya han sido resueltos anteriormente.

Esto se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memoización (no confundir con memorización; en inglés es llamado memoization, véase en). Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que de antemano sabemos que vamos a necesitar.

En resumen, la programación hace uso de: Subproblemas superpuestos Subestructuras óptimas Memoización

La programación toma normalmente uno de los dos siguientes enfoques: Top-down: El problema se divide en subproblemas, y estos se resuelven recordando las soluciones por si fueran necesarias nuevamente. Es una combinación de memoización y recursión. Bottom-up: Todos los problemas que puedan ser necesarios se resuelven de antemano y después se usan para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

Originalmente, el término de programación dinámica se refería a la resolución de ciertos problemas y operaciones fuera del ámbito de la Ingeniería Informática, al igual que hacía la programación lineal. Aquel contexto no tiene relación con la programación en absoluto; el nombre es una coincidencia. El término también lo usó en los años 40 Richard Bellman, un matemático estadounidense, para describir el proceso de resolución de problemas donde hace falta calcular la mejor solución consecutivamente.

Algunos lenguajes de programación funcionales, sobre todo Haskell, pueden usar la memoización automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan efectos secundarios, algo que ocurre en Haskell, pero no tanto en otros lenguajes.

Origen y definición La programación dinámica es un método cuantitativo desarrollado por Richard Bellman alrededor de la década de los años 50, con la finalidad de optimizar procesos, ya que en ese momento esa era su función como trabajador de RAND Corporation. Bellman decidió emplear la palabra dinámica a esta técnica, ya que deseaba analizar las variables de los problemas con respecto al tiempo. Siendo así Dasgupta, Papadimitriou y Vazirani (2006), entendieron a la programación dinámica como “optimización de procesos con etapa múltiples”. La idea de Bellman sobre la teoría de programación dinámica se basa en una estructura de optimización, la cual consiste en descomponer el problema en subproblemas (más manejables). Los cálculos se realizan entonces recursivamente donde la solución óptima de un subproblema se utiliza como dato de entrada al siguiente problema. Por lo cual, se entiende que el problema es solucionado en su totalidad, una vez se haya solucionado el último subproblema. Dentro de esta teoría, Bellman desarrolla el Principio de Optimalidad, el cual es fundamental para la resolución adecuada de los cálculos recursivos. Lo cual quiere decir que las etapas futuras desarrollan una política óptima independiente de las decisiones de las etapas predecesoras. Es por ello, que se define a la programación dinámica como una técnica matemática que ayuda a resolver decisiones secuenciales interrelacionadas, combinándolas para obtener de la solución óptima.

Características El problema se puede dividir por etapas, y cada una de las etapas requiere de una política de decisión.

Cada etapa tiene cierto número de estados, los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa.

El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa, entonces podemos decir que un estado es una columna de nodos, cada nodo representa un estado y cada rama una política de decisión.

El procedimiento de resolución de la programación dinámica está diseñado para encontrar una política óptima para cada etapa logrando así la política óptima general.

Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores, por ende, la decisión inmediata óptima solo depende del estado actual y no de cómo se llegó ahí, esto es el principio de optimalidad de la programación dinámica.

Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1.

Cuando se hace uso de la relación recursiva, el procedimiento de solución comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la política óptima en cada etapa hasta la etapa inicial.

Tipos de Enfoque Existen dos tipos de programación dinámica: La programación Dinámica determinística se utilizan datos que se conocen con certeza y la programación dinámica probabilística donde se usan datos que no se conocen con certeza pero que se determinan a través de distribuciones de probabilidad.

1) Programación Dinámica Determinística: El enfoque determinístico consiste en que el estado de la siguiente etapa se encuentra determinado por completo con respecto al estado y la decisión que posee la etapa actual. En la etapa n el proceso se encontrará en algún estado Sn. Al tomar la decisión xn se mueve a algún estado Sn+1 en la etapa n+1. El valor de la función objetiva para la política óptima de ese punto en adelante se calculó previamente como f*n+1(Sn+1). La política de decisión también hace una contribución a la función objetivo. Al combinar estas dos cantidades en la forma apropiada se proporciona a la función objetivo fn(Sn,xn) la contribución de la etapa n en adelante. La optimización respecto a xn proporciona entonces f*n(Sn)= fn(Sn,xn). Una vez encontrados xn y fn*(Sn) para cada valor posible de Sn, el procedimiento de solución se mueve hacia atrás una etapa.

Los problemas de programación dinámica determinística se pueden clasificar según su función objetivo (minimizar la suma de las contribuciones de cada una de las etapas individuales, maximizar esa suma, minimizar el producto de los términos, etc.) y según la naturaleza del conjunto de estados (variables discretas o variables continuas).

2) Programación Dinámica Probabilística: En este enfoque, el valor del estado de la siguiente etapa y política de decisión queda completamente determinado mediante una distribución probabilística. Sea S el número de estados posibles en la etapa n+1 y etiquete estos estados al lado derecho por 1,2…,S. El sistema cambia al estado i con probabilidad pi (i=1,2…,S) dados el estado Sn y la decisión xn en la etapa n. Si el sistema cambia al estado i, Ci es la contribución de la etapa n a la función objetivo.

Cuando se expande el diagrama para incluir todos los estados y las decisiones posibles en todas las etapas, se obtiene lo que con frecuencia se conoce como un árbol de decisión. Si este árbol de decisión no es muy grande, proporciona una forma útil de resumir estas posibilidades. La programación dinámica probabilística difiere de la determinística, en que el estado de la siguiente etapa no está completamente determinado por el estado y la política de decisión de la etapa actual. En este caso, existe una distribución de probabilidad para determinar cuál será el estado en la siguiente etapa. Debido a la estructura probabilística, la relación entre fn(Sn,xn) y fn+1*(Sn+1) dependerá de la forma global de la función objetivo.

Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar la mejor solución de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz. En otros casos, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima». En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en problemas más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a la de programación dinámica. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:

Una enorme cantidad de problemas. Problemas cuyas soluciones parciales se solapan. Grupos de problemas de muy distinta complejidad.

Ejemplos

Sucesión de Fibonacci

Esta sucesión puede expresarse mediante la siguiente recurrencia:

Una implementación de una función que encuentre el n-ésimo término de la sucesión de Fibonacci basada directamente en la definición matemática de la sucesión realizando llamadas recursivas hace mucho trabajo redundante, obteniéndose una complejidad exponencial:

FUNC fib(↓n: NATURAL): NATURAL INICIO SI n = 0 ENTONCES DEVOLVER 0 SI NO, SI n = 1 ENTONCES DEVOLVER 1 SI NO devolver fib(n-1) + fib(n-2) FIN SI FIN

Si llamamos, por ejemplo, a fib(5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces: fib(5) fib(4) + fib(3) (fib(3) + fib(2)) + (fib(2) + fib(1)) ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))