Programación dinámica

Gráfico 1 Encontrar el camino más corto en un gráfico usando subestructura óptima; una línea recta indica un solo borde; una línea ondulada indica un camino más corto entre los dos vértices que conecta (entre otros caminos, no mostrado, compartiendo los mismos dos vértices); la línea atrevida es el camino más corto de principio a meta.

La programación dinámica es tanto un método de optimización matemática como un método de programación informática. El método fue desarrollado por Richard Bellman en la década de 1950 y ha encontrado aplicaciones en numerosos campos, desde la ingeniería aeroespacial hasta la economía.

En ambos contextos se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples de manera recursiva. Si bien algunos problemas de decisión no se pueden separar de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se separan recursivamente. Del mismo modo, en informática, si un problema se puede resolver de manera óptima dividiéndolo en subproblemas y luego recursivamente encontrando las soluciones óptimas a los subproblemas, entonces se dice que tiene una subestructura óptima.

Si los subproblemas se pueden anidar recursivamente dentro de problemas más grandes, de modo que los métodos de programación dinámica sean aplicables, entonces existe una relación entre el valor del problema más grande y los valores de los subproblemas. En la literatura de optimización, esta relación se denomina ecuación de Bellman.

Resumen

Optimización matemática

En términos de optimización matemática, la programación dinámica generalmente se refiere a simplificar una decisión dividiéndola en una secuencia de pasos de decisión a lo largo del tiempo. Esto se hace definiendo una secuencia de funciones de valor V₁, V₂,..., V_n tomando y como argumento que representa el estado del sistema en tiempos i de 1 a n. La definición de V_n(y) es el valor obtenido en el estado y en la última vez n. Los valores V_i en tiempos anteriores i = n −1, n − 2,..., 2, 1 se puede encontrar trabajando hacia atrás, usando una relación recursiva llamada ecuación de Bellman. Para i = 2,..., n, V_i−1 en cualquier estado, y se calcula a partir de V_i maximizando una función simple (generalmente la suma) de la ganancia de una decisión en el tiempo i − 1 y la función V_i en el nuevo estado del sistema si esto se toma la decisión. Dado que V_i ya ha sido calculado para los estados necesarios, la operación anterior produce V_i−1 para esos estados. Finalmente, V₁ en el estado inicial del sistema es el valor de la solución óptima. Los valores óptimos de las variables de decisión se pueden recuperar, uno por uno, rastreando los cálculos ya realizados.

Teoría del control

En la teoría del control, un problema típico es encontrar un control admisible ${displaystyle mathbf {u}.$ que causa el sistema ${displaystyle {dot {mathbf {x}}(t)=mathbf {g} left(mathbf {x} (t),mathbf {u} (t),tright)}$ para seguir una trayectoria admisible ${displaystyle mathbf {x}.$ en un intervalo de tiempo continuo ${displaystyle T_{0}leq tleq T_{1}$ que minimiza una función de coste

${displaystyle J=bleft(mathbf {x}),t_{1}right)+int ¿Por qué?$

La solución a este problema es una ley o política de control óptima ${displaystyle mathbf {u} {ast}=h(mathbf {x} (t),t)}$, que produce una trayectoria óptima ${displaystyle mathbf {x}.$ y una función costo-a-go ${displaystyle J.$. Este último obedece a la ecuación fundamental de la programación dinámica:

${displaystyle -J_{t} {m} {m}m} {f}m}mf} {cHFF} {cHFF} {cHFF} {cHFF} {cHFF} {cHFF} {cHFF} {cHFF} {cHFF}cHFF}cH00}cHFF}cHFF} {cHFF}cHFF}cHFF}cHFF}cHFF}cHFF}cHFF}}cH}cHFF}cH}cHFF}cHFF}cH}cH}cHFF}cHFF} {cHFF}}cHFF}cH}cHFF}}cHFF}cHFF}cHFF}cHFF}}cHFF}cHFF}cHFF}cHFF}cHFF}}cHFF}$

una ecuación diferencial parcial conocida como la ecuación Hamilton–Jacobi–Bellman, en la que ${displaystyle ¿Por qué? J^{ast}{partial mathbf {x}=left[{frac {partial} - ¿Qué? ###### {fnMicroc {fnMicrosoft Sans Serif} }{partial ################################################################################################################################################################################################################################################################ ~~~~{frac {partial Oh, Dios mío.$ y ${displaystyle ¿Por qué? - ¿Qué? }$. Uno encuentra que minimizar ${displaystyle mathbf {u}$ en términos de ${displaystyle t}$, ${displaystyle mathbf {x}$, y la función desconocida ${displaystyle J.$ y luego sustituye el resultado en la ecuación Hamilton–Jacobi–Bellman para conseguir la ecuación diferencial parcial que se resolverá con la condición de límite ${displaystyle Jleft(t_{1}right)=bleft(mathbf {x} (t_{1}),t_{1}right)}$. En la práctica, esto generalmente requiere técnicas numéricas para cierta aproximación discreta a la relación de optimización exacta.

Alternativamente, el proceso continuo se puede aproximar mediante un sistema discreto, lo que conduce a la siguiente relación de recurrencia análoga a la ecuación de Hamilton-Jacobi-Bellman:

${displaystyle ¿Por qué? ¿Qué? ¿Qué? ¿Por qué? ¿Qué? - Bien.$

en el ${displaystyle k}$-a etapa de ${displaystyle n}$ intervalos de tiempo discretos igualmente espaciados, y donde ${displaystyle {hat {f}}$ y ${displaystyle {hat {mathbf} }$ aproximaciones discretas a ${displaystyle f}$ y ${displaystyle mathbf {g}$. Esta ecuación funcional se conoce como la ecuación Bellman, que se puede resolver para una solución exacta de la aproximación discreta de la ecuación de optimización.

Ejemplo de economía: el problema del ahorro óptimo de Ramsey

En la economía, el objetivo es en general maximizar (en lugar de minimizar) alguna función dinámica de bienestar social. En el problema de Ramsey, esta función relaciona cantidades de consumo a niveles de utilidad. En términos muy parecidos, el planificador se enfrenta al intercambio entre el consumo contemporáneo y el consumo futuro (a través de la inversión en acciones de capital que se utiliza en la producción), conocida como opción intertemporal. El consumo futuro se desconta a un ritmo constante ${displaystyle beta in (0,1)}$. Una aproximación discreta a la ecuación de transición del capital es dada por

${displaystyle ¿Qué?$

Donde ${displaystyle c}$ es consumo, ${displaystyle k}$ es capital, y ${displaystyle f}$ es una función de producción que satisface las condiciones Inada. Un capital inicial ${displaystyle ¿Qué?$ es asumido.

Vamos ${displaystyle c_{t}$ consumo en el período t, y asumir rendimientos de consumo utilidad ${displaystyle u(c_{t}=ln(c_{t}}$ mientras el consumidor viva. Supongamos que el consumidor es impaciente, por lo que descuentos utilidad futura por un factor b cada período, donde ${displaystyle 0 realizadasb$. Vamos ${displaystyle k_{t}$ capital en el período t. Assume capital inicial es una cantidad dada ${displaystyle ¿Qué?$, y suponer que el capital y el consumo de este período determinan el capital del próximo período como ${displaystyle K_{t+1}=Ak_{t} {a}-c_{t}$, donde A es una constante positiva y ${displaystyle 0 realizadasa$. El capital no puede ser negativo. Entonces el problema de decisión del consumidor se puede escribir de la siguiente manera:

${displaystyle max sum _{t=0} {T}b^{t}ln(c_{t}}$ sujeto a ${displaystyle K_{t+1}=Ak_{t} {a}-c_{t}geq 0}$ para todos ${displaystyle t=0,1,2,ldotsT}$

Escrito de esta manera, el problema se ve complicado, porque implica resolver todas las variables de elección ${displaystyle c_{0},c_{1},c_{2},ldotsc_{T}$. (La capital) ${displaystyle K_{0}$ no es una variable de elección: el capital inicial del consumidor se toma como se da.)

El enfoque dinámico de programación para resolver este problema implica dividirlo en una secuencia de decisiones más pequeñas. Para hacerlo, definimos una secuencia de funciones de valor ${displaystyle V_{t}(k)}$, para ${displaystyle t=0,1,2,ldotsT,T+1}$ que representan el valor de tener cualquier cantidad de capital k en cada momento t. No hay (por suposición) utilidad de tener capital después de la muerte, ${displaystyle V_{T+1}(k)=0}$.

El valor de cualquier cantidad de capital en cualquier momento anterior se puede calcular por inducción atrasada utilizando la ecuación Bellman. En este problema, para cada uno ${displaystyle t=0,1,2,ldotsT}$, la ecuación de Bellman es

${displaystyle V_{t}(k_{t}),=,max left(ln(c_{t})+bV_{t+1}(k_{t+1})right)}$ sujeto a ${displaystyle K_{t+1}=Ak_{t} {a}-c_{t}geq 0}$

Este problema es mucho más simple que el que escribimos antes, porque implica sólo dos variables de decisión, ${displaystyle c_{t}$ y ${displaystyle K_{t+1}$. Intuitivamente, en lugar de elegir todo su plan de vida al nacer, el consumidor puede dar un paso a la vez. At time t, su actual capital ${displaystyle k_{t}$ se da, y sólo necesita elegir el consumo actual ${displaystyle c_{t}$ y ahorro ${displaystyle K_{t+1}$.

Para resolver este problema, trabajamos hacia atrás. Para la simplicidad, el nivel actual del capital se denota como k. ${displaystyle V_{T+1}(k)}$ ya se sabe, así que usando la ecuación de Bellman una vez que podamos calcular ${displaystyle V_{T}(k)}$, y así sucesivamente hasta que lleguemos ${displaystyle V_{0}(k)}$, que es el valor del problema de decisión inicial para toda la vida. En otras palabras, una vez que sabemos ${displaystyle V_{T-j+1}(k)}$, podemos calcular ${displaystyle V_{T-j}(k)}$, que es el máximo de ${displaystyle ln(c_{T-j})+bV_{T-j+1}(Ak^{a}-c_{T-j})}$, donde ${displaystyle C_{T-J}$ es la variable de elección y ${displaystyle Ak^{a}-c_{T-j}geq 0}$.

Trabajando hacia atrás, se puede demostrar que la función de valor a la vez ${displaystyle t=T-j}$ es

${displaystyle V_{T-j}(k),=,asum ¿Qué? k+v_{T-j}$

donde cada ${displaystyle v.$ es una constante, y la cantidad óptima para consumir a la vez ${displaystyle t=T-j}$ es

${displaystyle c_{T-j}(k),=,{frac {1}{sum ¿Qué?$

que se puede simplificar a

${displaystyle {begin{aligned}c_{T}(k) limit=Ak^{a}c_{T-1}(k) limit={frac {Ak^{a}{1+ab}c_{T-2}(k) Due={frac} {Ak^{a}{1+ab+a^{2}}}\\cdots \c_{2}(k) limit={frac {Ak^{a}{1+ab+a^{2}b^{2}+ldots +a^{T-2}b^{T-2}}}\c_{1}(k) {Ak^{a}{1+ab+a^{2}b^{2}+ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}}c_{0}(k)}={frac {Ak^{a}{1+ab+a^{2}b^{2}+ldots +a^{T-2}b^{T-2}+a^{T-1}b^{T-1}+a^{T} {T} {T}}}end{aligned}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}} {}}}}}} {}}}}}}}}}}}} {}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}$

Vemos que es óptimo consumir una fracción mayor de la riqueza actual a medida que uno envejece, consumiendo finalmente toda la riqueza restante en el período T< /span>, el último período de la vida.

Programación informática

Hay dos atributos clave que debe tener un problema para que la programación dinámica sea aplicable: subestructura óptima y subproblemas superpuestos. Si un problema se puede resolver combinando soluciones óptimas a subproblemas que no se superponen, la estrategia se llama "divide y vencerás" en cambio. Esta es la razón por la que la ordenación por fusión y la ordenación rápida no se clasifican como problemas de programación dinámica.

Subestructura óptima significa que la solución a un problema de optimización dado se puede obtener mediante la combinación de soluciones óptimas a sus subproblemas. Estas subestructuras óptimas se suelen describir mediante recursividad. Por ejemplo, dado un gráfico G=(V,E), el camino más corto p desde un vértice u hasta un vértice v exhibe una subestructura óptima: tome cualquier vértice intermedio w en este camino más corto p. Si p es verdaderamente la ruta más corta, entonces se puede dividir en sub-rutas p₁ desde u hasta w y p₂ de w a v tales que estos, a su vez, son de hecho los caminos más cortos entre los vértices correspondientes (por el simple argumento de cortar y pegar descrito en Introducción a los algoritmos). Por lo tanto, se puede formular fácilmente la solución para encontrar los caminos más cortos de manera recursiva, que es lo que hace el algoritmo de Bellman-Ford o el algoritmo de Floyd-Warshall.

Subproblemas superpuestos significa que el espacio de subproblemas debe ser pequeño, es decir, cualquier algoritmo recursivo que resuelva el problema debe resolver los mismos subproblemas una y otra vez, en lugar de generar nuevos. sub-problemas. Por ejemplo, considere la formulación recursiva para generar la serie de Fibonacci: F_i = F_i−1 + F_i−2, con caso base F ₁ = F₂ = 1. Entonces F₄₃ = F ₄₂ + F₄₁, y F₄₂ = F₄₁ + F₄₀. Ahora F₄₁ se está resolviendo en los subárboles recursivos tanto de F₄₃ como de F₄₂. Aunque el número total de subproblemas es realmente pequeño (solo 43 de ellos), terminamos resolviendo los mismos problemas una y otra vez si adoptamos una solución recursiva ingenua como esta. La programación dinámica tiene en cuenta este hecho y resuelve cada subproblema una sola vez.

Gráfico 2 El gráfico subproblema para la secuencia Fibonacci. El hecho de que no sea un árbol indica subproblemas superpuestos.

Esto se puede lograr de dos maneras:

• Enfoque superior: Esta es la caída directa de la formulación recursiva de cualquier problema. Si la solución a cualquier problema se puede formular recursivamente utilizando la solución a sus subproblemas, y si sus subproblemas se superponen, entonces se puede memoizar o almacenar fácilmente las soluciones a los subproblemas en una tabla. Cada vez que intentamos resolver un nuevo subproblema, primero revisamos la tabla para ver si ya está resuelto. Si se ha registrado una solución, podemos utilizarla directamente, de lo contrario resolvemos el subproblema y agregamos su solución a la tabla.
• Enfoque básico: Una vez que formulamos la solución a un problema recursivamente como en términos de sus subproblemas, podemos intentar reformular el problema de una manera de fondo: tratar de resolver los subproblemas primero y utilizar sus soluciones para construir y llegar a soluciones a subproblemas más grandes. Esto también se hace generalmente en forma tabular mediante la generación iterativa de soluciones a subproblemas más grandes y grandes utilizando las soluciones a pequeños subproblemas. Por ejemplo, si ya conocemos los valores F₄₁ y F₄₀, podemos calcular directamente el valor de F₄₂.

Algunos lenguajes de programación pueden memorizar automáticamente el resultado de una llamada de función con un conjunto particular de argumentos, para acelerar la evaluación de llamada por nombre (este mecanismo se conoce como llamada por necesidad). Algunos idiomas lo hacen posible de forma portátil (por ejemplo, Scheme, Common Lisp, Perl o D). Algunos idiomas tienen incorporada la memorización automática, como Tabled Prolog y J, que admiten la memorización con el adverbio M.. En cualquier caso, esto sólo es posible para una función referencialmente transparente. La memorización también se encuentra como un patrón de diseño de fácil acceso dentro de los lenguajes basados en la reescritura de términos, como Wolfram Language.

Bioinformática

La programación dinámica se usa ampliamente en bioinformática para tareas como la alineación de secuencias, el plegamiento de proteínas, la predicción de estructuras de ARN y la unión de proteínas y ADN. Los primeros algoritmos de programación dinámica para la unión proteína-ADN fueron desarrollados en la década de 1970 de forma independiente por Charles DeLisi en EE. UU. y Georgii Gurskii y Alexander Zasedatelev en la URSS. Recientemente, estos algoritmos se han vuelto muy populares en bioinformática y biología computacional, particularmente en los estudios de posicionamiento de nucleosomas y unión de factores de transcripción.

Ejemplos: algoritmos informáticos

Algoritmo de Dijkstra para el problema del camino más corto

Desde el punto de vista de la programación dinámica, el algoritmo de Dijkstra para el problema del camino más corto es un esquema de aproximación sucesiva que resuelve la ecuación funcional de la programación dinámica para el problema del camino más corto mediante el método Reaching.

De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, a saber

Problema 2. Encontrar el camino de la longitud total mínima entre dos nodos dados ${displaystyle P}$ y ${displaystyle Q}$.

Usamos el hecho de que, si ${displaystyle R.$ es un nodo en el camino mínimo desde ${displaystyle P}$ a ${displaystyle Q}$, el conocimiento de este último implica el conocimiento del camino mínimo desde ${displaystyle P}$ a ${displaystyle R.$.

es una paráfrasis del famoso Principio de Optimalidad de Bellman en el contexto del problema del camino más corto.

Secuencia de Fibonacci

Usar programación dinámica en el cálculo del nésimo miembro de la sucesión de Fibonacci mejora enormemente su rendimiento. Aquí hay una implementación ingenua, basada directamente en la definición matemática:

función fib(n)
 si n retorno n
 retorno fib(n −1) + fib(n − 2)

Observe que si llamamos, digamos, fib(5), producimos un árbol de llamadas que llama a la función en el mismo valor muchas veces diferentes:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib(2) se calculó tres veces desde cero. En ejemplos más grandes, se recalculan muchos más valores de fib, o subproblemas, lo que lleva a un algoritmo de tiempo exponencial.

Ahora, supongamos que tenemos un objeto de mapa simple, m, que asigna cada valor de fib que ya ha sido calculado a su resultado, y modificamos nuestra función para úsalo y actualízalo. La función resultante requiere solo tiempo O(n) en lugar de tiempo exponencial (pero requiere espacio O(n)):

Var m:= mapa(0 → 0, 1 → 1)
función fib(n)
 si clave n no está mapa m
m[n]:= fib(n −1) + fib(n - 2)
 retorno m[n]

Esta técnica de guardar valores que ya han sido calculados se llama memoización; este es el enfoque de arriba hacia abajo, ya que primero dividimos el problema en subproblemas y luego calculamos y almacenamos valores.

En el enfoque de abajo hacia arriba, primero calculamos los valores más pequeños de fib y luego construimos valores más grandes a partir de ellos. Este método también usa el tiempo O(n) ya que contiene un bucle que se repite n − 1 veces, pero solo ocupa un espacio constante (O(1)), en contraste con el enfoque de arriba hacia abajo que requiere espacio O(n) para almacenar el mapa.

función fib(n)
 si n = 0
 retorno 0
 más Var anteriorFib:= 0, corrienteFib:= 1
 repetición n − 1 veces // lazo se salta si n = 1 Var nuevo Fib:= anterior Fib + corriente Fib
anterior Fib:= corriente Fib
corriente Fib:= nuevo Fib
 retorno corriente Fib

En ambos ejemplos, solo calculamos fib(2) una vez y luego lo usamos para calcular tanto fib(4) como fib(3) , en lugar de calcularlo cada vez que se evalúa cualquiera de ellos.

Un tipo de matriz 0-1 balanceada

Considere el problema de asignar valores, ya sea cero o uno, a las posiciones de un n × n matriz, con n incluso, para que cada fila y cada columna contenga exactamente n / 2 ceros y n / 2 Unos. Preguntamos cuántas asignaciones diferentes hay para un dado ${displaystyle n}$. Por ejemplo, cuando n = 4, cinco posibles soluciones

${0} {0} {0}$

Hay al menos tres enfoques posibles: fuerza bruta, retroceso y programación dinámica.

La fuerza bruta consiste en comprobar todas las asignaciones de ceros y de aquellos que tienen filas y columnas equilibradas (n / 2 ceros y n / 2). Como hay ${displaystyle 2^{n^{2}}}$ posibles asignaciones y ${displaystyle {tbinom} {n}{n/2} {n}}} {n} {n} {n} {n} {n} {n} {n}} {n} {n} {n} {n} {n} {n}{n} {n}{n} {n} {n} {n} {n} {n} {n} {n} {n} {n} {n} {n} {n}{n} {n} {n} {n}}}}}}}}}}}} {n} {n}{n} {n} {n} {n}} {n}{n}{n}{n} {n}}}}} {n}}}}}}}}}}}}}}}}}} {n}}} {n}}}}}} {n}}}}} {n}}}}}}}}}}}}} {n}}}}}}}}}}}}} {n}{n} {n}}}}}}}}}}}} {n}}}}}}$ asignaciones sensibles, esta estrategia no es práctica excepto tal vez hasta ${displaystyle n=6}$.

Retroceder para este problema consiste en elegir algún orden de los elementos de la matriz y colocar recursivamente unos o ceros, mientras se verifica que en cada fila y columna el número de elementos que no han sido asignados más el número de unos o ceros están ambos en menos n / 2. Si bien es más sofisticado que la fuerza bruta, este enfoque visitará cada solución una vez, lo que lo hace poco práctico para n mayores de seis, ya que la cantidad de soluciones ya es 116,963,796,250 para n = 8, como veremos.

La programación dinámica permite contar el número de soluciones sin visitarlas todas. Imagínese valores de retroceso para la primera fila – ¿qué información requeriríamos sobre las filas restantes, para poder contar con precisión las soluciones obtenidas para cada valor de primera fila? Consideramos k × n tableros, donde 1 ≤ k ≤ n, cuyo ${displaystyle k}$ filas contienen ${displaystyle n/2}$ ceros y ${displaystyle n/2}$ Unos. La función f a los que se aplica la memoización mapas vectores de n pares de enteros al número de tablas admisibles (soluciones). Hay un par para cada columna, y sus dos componentes indican respectivamente el número de ceros y los que aún no se han colocado en esa columna. Buscamos el valor de ${displaystyle f(n/2,n/2),(n/2,n/2),ldots (n/2,n/2)}$ ()${displaystyle n}$ argumentos o un vector de ${displaystyle n}$ elementos). El proceso de creación de subproblema implica la iteración sobre cada uno de los ${displaystyle {tbinom} {n}{n/2}}$ posibles asignaciones para la fila superior del tablero, y pasando por cada columna, restando uno del elemento apropiado del par para esa columna, dependiendo de si la asignación para la fila superior contenía un cero o uno en esa posición. Si alguno de los resultados es negativo, entonces la asignación es inválida y no contribuye al conjunto de soluciones (paradas de recusión). De lo contrario, tenemos una asignación para la fila superior de la k × n y computar de forma recurrente el número de soluciones al resto ()k −1) n tabla, agregando el número de soluciones para cada asignación admisible de la fila superior y devolviendo la suma, que se está memoizando. El caso base es el subproblema trivial, que ocurre para un 1 × n Junta. El número de soluciones para este tablero es cero o uno, dependiendo de si el vector es una permutación n / 2 ${displaystyle (0,1)}$ y n / 2 ${displaystyle (1,0)}$ pares o no.

Por ejemplo, en los primeros dos tableros que se muestran arriba, las secuencias de vectores serían

(2, 2) (2, 2) (2, 2) (2, 2)) (2, 2) (2, 2) (2, 2) (2, 2) k = 4
0 1 0 0 0 1 1

((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3
1 0 0 0 0 1 1

(1, 1) (1, 1) (1, 1) (1, 1)) (0, 2) (0, 2) (2, 0) (2, 0))) k = 2
0 1 0 1 1 1 0 0

(0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0))) k = 1
1 0 1 0 1 0 0 0

(0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0), (0, 0) (0, 0)))

El número de soluciones (secuencia A058527 en el OEIS) es

${displaystyle 1,,2,,90,,297200,,116963796250,,6736218287430460752,ldots }$

Los enlaces a la implementación MAPLE del enfoque de programación dinámica se pueden encontrar entre los enlaces externos.

Tablero de ajedrez

Considere un tablero de ajedrez con n × n cuadrados y una función de costo c(i, j) que devuelve un costo asociado con el cuadrado < código>(i,j) (i siendo la fila, j siendo la columna). Por ejemplo (en un tablero de ajedrez de 5 × 5),

Así c(1, 3) = 5

Digamos que hay una ficha que puede comenzar en cualquier casilla de la primera fila (es decir, la fila) y desea saber el camino más corto (la suma de los costos mínimos en cada fila visitada) para llegar a la última rango; suponiendo que la ficha pueda moverse solo en diagonal hacia la izquierda hacia adelante, en diagonal hacia la derecha hacia adelante o hacia adelante. Es decir, una ficha en (1,3) puede moverse a (2,2), (2,3) o (2,4).

Este problema presenta una subestructura óptima. Es decir, la solución de todo el problema depende de las soluciones de los subproblemas. Definamos una función q(i, j) como

q()i, j) = el costo mínimo para alcanzar cuadrado (i, j).

Comenzando en el rango n y descendiendo al rango 1, calculamos el valor de esta función para todos los cuadrados en cada rango sucesivo. Elegir el cuadrado que contiene el valor mínimo en cada rango nos da el camino más corto entre el rango n y el rango 1.

La función q(i, j) es igual al costo mínimo para llegar a cualquiera de los tres cuadrados debajo de ella (ya que esos son los únicos cuadrados que pueden alcanzarla) más c(i, j). Por ejemplo:

${displaystyle q(A)=min(q(B),q(C),q(D)))+c(A),}$

Ahora, definamos q(i, j) en términos algo más generales:

${displaystyle q(i,j)={begin{cases}infty &j贸1{text{ or }j confidencialnc(i,j) limiti=1min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j) {textotherwise}}} {displaystyle qq {i}} {i}$

La primera línea de esta ecuación se trata de un tablero modelado como cuadrados indexados en 1 en el límite inferior y n en el límite superior. La segunda línea especifica lo que sucede en el primer rango; proporcionando un caso base. La tercera línea, la recursividad, es la parte importante. Representa los términos A,B,C,D del ejemplo. A partir de esta definición, podemos derivar un código recursivo directo para q(i, j). En el siguiente pseudocódigo, n es el tamaño del tablero, c(i, j) es la función de costo y min() devuelve el mínimo de un número de valores:

función minCost(i, j)
 si j) o j
 retorno infinity
 si i = 1
 retorno c(i, j)
 más retorno min(minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1)) + c(i, j)

Esta función solo calcula el costo de la ruta, no la ruta real. Discutimos la ruta real a continuación. Esto, como el ejemplo de los números de Fibonacci, es terriblemente lento porque también exhibe el atributo subproblemas superpuestos. Es decir, vuelve a calcular los mismos costos de ruta una y otra vez. Sin embargo, podemos calcularlo mucho más rápido de forma ascendente si almacenamos los costos de ruta en una matriz bidimensional q[i, j] en lugar de usar una función. Esto evita el recálculo; todos los valores necesarios para la matriz q[i, j] se calculan con anticipación solo una vez. Los valores precalculados para (i,j) simplemente se buscan cuando se necesitan.

También necesitamos saber cuál es la ruta más corta real. Para hacer esto, usamos otra matriz p[i, j]; una matriz predecesora. Esta matriz registra la ruta a cualquier s cuadrado. El predecesor de s se modela como un desplazamiento relativo al índice (en q[i, j]) del costo de la ruta precalculada de s. Para reconstruir la ruta completa, buscamos el predecesor de s, luego el predecesor de ese cuadrado, luego el predecesor de ese cuadrado, y así sucesivamente de forma recursiva, hasta llegar al cuadrado inicial. Considere el siguiente pseudocódigo:

función computeShortestPathArrays()
 para x desde 1 a n
q[1, x]:= c(1, x)
 para Sí. desde 1 a n
q[y, 0]:= infinity
q[y, n + 1]:= infinity
 para Sí. desde 2 a n
 para x desde 1 a n
m:= min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
q[y, x]:= m + c(y, x)
 si m = q[y-1, x-1]
p[y, x]:= -1
 si m = q[y-1, x]
p[y, x]:= 0
 másp[y, x]:= 1

Ahora el resto es una simple cuestión de encontrar el mínimo e imprimirlo.

función computeShortestPath()
computeShortestPathArrays()
minIndex:= 1
min:= q[n, 1]
 para i desde 2 a n
 si q[n, i]
minIndex:= i
min:= q[n, i)
printPath(n, minIndex)

función printPath(y, x)
 impresiónx)
 impresión("traducido")
 si y 2
 impresión(x + p[y, x])
 másprintPath(y-1, x + p[y, x])

Alineación de secuencias

En genética, la alineación de secuencias es una aplicación importante donde la programación dinámica es esencial. Normalmente, el problema consiste en transformar una secuencia en otra mediante operaciones de edición que reemplazan, insertan o eliminan un elemento. Cada operación tiene un costo asociado y el objetivo es encontrar la secuencia de ediciones con el costo total más bajo.

El problema se puede plantear naturalmente como una recursividad, una secuencia A se edita de manera óptima en una secuencia B mediante:

1. insertar el primer personaje de B, y realizar una alineación óptima de A y la cola de B
2. eliminando el primer personaje de A, y realizando la alineación óptima de la cola de A y B
3. reemplazando el primer personaje de A con el primer carácter de B, y realizando alineaciones óptimas de las colas de A y B.

Las alineaciones parciales se pueden tabular en una matriz, donde la celda (i,j) contiene el costo de la alineación óptima de A[1..i] a B[1..j]. El costo en la celda (i, j) se puede calcular sumando el costo de las operaciones relevantes al costo de sus celdas vecinas y seleccionando el óptimo.

Existen diferentes variantes, consulte el algoritmo de Smith-Waterman y el algoritmo de Needleman-Wunsch.

Rompecabezas de la Torre de Hanoi

Un modelo de las Torres de Hanoi (con 8 discos)

Una solución animada de la Torre de Hanoi rompecabezas para T(4,3).

La Torre de Hanoi o Torres de Hanoi es un juego o rompecabezas matemático. Consta de tres varillas y una serie de discos de diferentes tamaños que pueden deslizarse sobre cualquier varilla. El rompecabezas comienza con los discos en una pila ordenada en orden ascendente de tamaño en una barra, el más pequeño en la parte superior, formando así una forma cónica.

El objetivo del rompecabezas es mover toda la pila a otra barra, obedeciendo las siguientes reglas:

• Sólo un disco se puede mover a la vez.
• Cada movimiento consiste en tomar el disco superior de una de las varillas y deslizarla sobre otra varilla, en la parte superior de los otros discos que ya pueden estar presentes en esa varilla.
• No se puede colocar ningún disco en la parte superior de un disco más pequeño.

La solución de programación dinámica consiste en resolver la ecuación funcional

S(n,h,t) = S(n-1,h, not(h,t)); S(1,h,t); S(n-1,not(h,t),t)

donde n denota el número de discos que se moverán, h denota la barra de inicio, t denota la barra de destino, not(h,t) denota la tercera barra (ni h ni t), ";&# 34; denota concatenación, y

S(n, h, t):= solución a un problema que consiste en discos n que se van a mover de varilla h a varilla t.

Para n=1 el problema es trivial, concretamente S(1,h,t) = "mover un disco de la barra h a la barra t" (solo queda un disco).

El número de movimientos requerido por esta solución es 2ⁿ − 1. Si el objetivo es maximizar el número de movimientos (sin ciclismo), entonces la ecuación funcional de programación dinámica es un poco más complicada y se requieren 3ⁿ − 1 movimientos.

Rompecabezas que deja caer un huevo

La siguiente es una descripción de la instancia de este famoso rompecabezas que involucra N=2 huevos y un edificio con H=36 pisos:

Supongamos que deseamos saber qué historias en un edificio de 36 pisos son seguras para dejar caer huevos, y que causarán que los huevos se rompan en el aterrizaje (utilizando la terminología inglesa de Estados Unidos, en la que el primer piso está a nivel de tierra). Hacemos algunas suposiciones:

• Un huevo que sobrevive a una caída puede ser utilizado de nuevo.
• Un huevo roto debe ser descartado.
• El efecto de una caída es el mismo para todos los huevos.
• Si un huevo se rompe cuando se cae, entonces se rompería si se deja caer de una ventana superior.
• Si un huevo sobrevive una caída, entonces sobreviviría una caída más corta.
• No se descarta que las ventanas de primera planta rompan los huevos, ni se descarta que los huevos puedan sobrevivir a las ventanas de la planta 36.

Si sólo hay un huevo disponible y queremos estar seguros de obtener el resultado correcto, el experimento se puede llevar a cabo de una sola manera. Suelte el huevo de la ventana del primer piso; si sobrevive, déjalo de la ventana del segundo piso. Continúa hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 36 exenciones. Supongamos que hay 2 huevos disponibles. ¿Cuál es el menor número de goteo de huevo que está garantizado para trabajar en todos los casos?

Para derivar una ecuación funcional de programación dinámica para este rompecabezas, permita que el estado del modelo de programación dinámica sea un par s = (n,k), donde

n = número de huevos de prueba disponibles, n = 0, 1, 2, 3,... N− 1.

k = número de pisos (consecutivos) que aún no se han probado, k = 0, 1, 2,... H− 1.

Por ejemplo, s = (2,6) indica que hay dos huevos de prueba disponibles y que quedan 6 pisos (consecutivos) por probar. El estado inicial del proceso es s = (N,H) donde N indica el número de huevos de prueba disponibles al comienzo del experimento. El proceso termina cuando no hay más huevos de prueba (n = 0) o cuando k = 0, lo que ocurra primero. Si la terminación ocurre en el estado s = (0,k) y k > 0, entonces la prueba falló.

Ahora, deja

W()n,k) = número mínimo de ensayos requeridos para identificar el valor del piso crítico en el peor escenario dado que el proceso está en estado s =n,k).

Entonces se puede demostrar que

W()n,k) = 1 + min{max()W()n, 1, x −1), W()n,k − x) x = 1, 2,... k }

con W(n,0) = 0 para todos los n > 0 y W(1,k) = k para todos k. Es fácil resolver esta ecuación iterativamente aumentando sistemáticamente los valores de n y k.

Solución de DP más rápida usando una parametrización diferente

Observe que la solución anterior requiere ${displaystyle O(nk^{2}}$ tiempo con una solución DP. Esto puede mejorarse ${displaystyle O(nklog k)}$ tiempo por búsqueda binaria en la óptima ${displaystyle x}$ en la repetición anterior, desde ${displaystyle W(n-1,x-1)}$ está aumentando ${displaystyle x}$ mientras ${displaystyle W(n,k-x)}$ está disminuyendo ${displaystyle x}$, por lo tanto un mínimo local ${displaystyle max(W(n-1,x-1),W(n,k-x)}$ es un mínimo global. Además, almacenando lo óptimo ${displaystyle x}$ para cada célula en la tabla DP y refiriéndose a su valor para la célula anterior, el óptimo ${displaystyle x}$ para cada célula se puede encontrar en tiempo constante, mejorando a ${displaystyle O(nk)}$ tiempo. Sin embargo, hay una solución aún más rápida que implica una parametrización diferente del problema:

Vamos ${displaystyle k}$ ser el número total de pisos tales que los huevos se rompen cuando se deja caer del ${displaystyle k}$piso (El ejemplo anterior es equivalente a tomar ${displaystyle k=37}$).

Vamos ${displaystyle m}$ ser el piso mínimo desde el cual el huevo debe ser dejado para ser roto.

Vamos ${displaystyle f(t,n)}$ ser el número máximo de valores ${displaystyle m}$ que se distinguen utilizando ${displaystyle t}$ Intenta y ${displaystyle n}$ huevos.

Entonces... ${displaystyle f(t,0)=f(0,n)=1}$ para todos ${displaystyle t,ngeq 0}$.

Vamos ${displaystyle a}$ ser el piso desde el cual el primer huevo se deja caer en la estrategia óptima.

Si el primer huevo se rompió, ${displaystyle m}$ es de ${displaystyle 1}$ a ${displaystyle a}$ y distinguible usando al máximo ${displaystyle t-1}$ Intenta y ${displaystyle n-1}$ huevos.

Si el primer huevo no se rompió, ${displaystyle m}$ es de ${displaystyle a+1}$ a ${displaystyle k}$ y diferenciable utilizando ${displaystyle t-1}$ Intenta y ${displaystyle n}$ huevos.

Por lo tanto, ${displaystyle f(t,n)=f(t-1,n-1)+f(t-1,n)}$.

Entonces el problema es equivalente a encontrar el mínimo ${displaystyle x}$ tales que ${displaystyle f(x,n)geq k}$.

Para hacerlo, podríamos calcular ${displaystyle {f(t,i):0leq ileq n}$ para aumentar ${displaystyle t}$, que tomaría ${displaystyle O(nx)}$ tiempo.

Así, si nos ocupamos por separado del caso ${displaystyle n=1}$, el algoritmo tomaría ${displaystyle O(n{sqrt {k})}$ tiempo.

Pero la relación de recurrencia puede ser resuelta, dando ${displaystyle f(t,n)=sum ¿Qué? {} {}}}$, que se puede calcular en ${displaystyle O(n)}$ tiempo utilizando la identidad ${displaystyle {binom} {T}{i+1}={binom} {} {fn} {fnMicroc}} {fn}}} {f}} {fn}} {fn}}} {fn}}} {fn}}} {fn}}} {fn}} {f}}} {f}}} {fnMicroc}}} {f}}}}}} {f}}}}} {f}}}}} {f}}}}}} {f}}}}} {f} {f}}} {f}f}}}}}}}}} {f} {f}}}}}} {f} {f}} {f} {f}} {f}f}}}}}}}}} {f} {f}f} {f}f}f}f}f}f}f}}f}f}}f}f}f}}}} {t-i}{i+1}}$ para todos ${displaystyle igeq 0}$.

Desde ${displaystyle f(t,n)leq f(t+1,n)}$ para todos ${displaystyle tgeq 0}$, podemos buscar en binario ${displaystyle t}$ encontrar ${displaystyle x}$, dar una ${displaystyle O(nlog k)}$ algoritmo.

Multiplicación de cadenas de matrices

La multiplicación de cadena de matriz es un ejemplo bien conocido que demuestra utilidad de programación dinámica. Por ejemplo, las aplicaciones de ingeniería a menudo tienen que multiplicar una cadena de matrices. No es sorprendente encontrar matrices de grandes dimensiones, por ejemplo 100×100. Por lo tanto, nuestra tarea es multiplicar matrices ${displaystyle A_{1},A_{2},... A_{n}$. La multiplicación de matriz no es conmutativa, pero es asociativa; y podemos multiplicar sólo dos matrices a la vez. Por lo tanto, podemos multiplicar esta cadena de matrices de muchas maneras diferentes, por ejemplo:

(A₁ × A₂) × A₃) ×... A_n

A₁((A)₂×A₃)×...) × A_n)

(A₁ × A₂) × (A)₃ ×..._n)

y así sucesivamente. Existen numerosas formas de multiplicar esta cadena de matrices. Todos producirán el mismo resultado final, sin embargo, llevará más o menos tiempo calcularlos, según las matrices particulares que se multipliquen. Si la matriz A tiene dimensiones m×n y la matriz B tiene dimensiones n×q, entonces la matriz C=A×B tendrá dimensiones m×q y requerirá m*n*q multiplicaciones escalares (usando un algoritmo de multiplicación de matrices simplista para propósitos de ilustración).

Por ejemplo, multipliquemos las matrices A, B y C. Supongamos que sus dimensiones son m×n, n×p y p×s, respectivamente. La matriz A×B×C será de tamaño m×s y se puede calcular de las dos formas que se muestran a continuación:

1. Ax(B×C) Este orden de multiplicación de matriz requerirá multiplicaciones de escalar nps + mns.
2. (A×B)×C Este orden de multiplicación de matriz requerirá cálculos de escalar mnp + mps.

Supongamos que m = 10, n = 100, p = 10 y s = 1000. Por lo tanto, la primera forma de multiplicar la cadena requerirá 1 000 000 + 1 000 000 de cálculos. La segunda forma requerirá solo 10,000+100,000 cálculos. Obviamente, la segunda forma es más rápida y deberíamos multiplicar las matrices usando esa disposición de paréntesis.

Por lo tanto, nuestra conclusión es que el orden de los paréntesis es importante y que nuestra tarea es encontrar el orden óptimo de los paréntesis.

En este punto, tenemos varias opciones, una de las cuales es diseñar un algoritmo de programación dinámica que dividirá el problema en problemas superpuestos y calculará la disposición óptima de los paréntesis. La solución de programación dinámica se presenta a continuación.

Llamemos a m[i,j] el número mínimo de multiplicaciones escalares necesarias para multiplicar una cadena de matrices desde la matriz i a la matriz j (es decir, A_i ×.... × A_j, es decir, i<=j). Dividimos la cadena en alguna matriz k, tal que i <= k < j, e intente averiguar qué combinación produce el mínimo m[i,j].

La fórmula es:

 si i = j, m[i,j]= 0
 si j, m[i,j]= min sobre todos los valores posibles de k (m[i,k]+m[k+1,j] + ${displaystyle P_{i-1}*p_{k}*p_{j}$) 

donde k varía de i a j − 1.

• ${displaystyle P_{i-1}$ es la dimensión de fila de la matriz i,
• ${displaystyle P_{k}$ es la dimensión de la columna de la matriz k,
• ${displaystyle P_{j}$ es la dimensión de la columna de la matriz j.

Esta fórmula se puede codificar como se muestra a continuación, donde el parámetro de entrada "cadena" es la cadena de matrices, es decir. ${displaystyle A_{1},A_{2},... A_{n}$:

función OptimalMatrixChainParenthesis(chain)
n = longitud(cadena)
 para i = 1, n
m[i,i] = 0 // Puesto que no necesita cálculos para multiplicar una matriz para lino = 2, n
 para i = 1, n - len + 1
j = i + len -1
m[i,j] = infinito // Así que la primera actualización de cálculo para k = i, j-1
 q = m[i, k] + m[k+1, j] + ${displaystyle P_{i-1}*p_{k}*p_{j}$ si [i, j] // El nuevo orden de paréntesis es mejor que lo que teníamosm[i, j] = q // Actualizacións[i, j] = k // Grabar qué k para dividir, es decir, dónde colocar el paréntesis

Hasta ahora, hemos calculado valores para todo lo posible m[i, j], el número mínimo de cálculos para multiplicar una cadena de matriz i a la matriz j, y hemos registrado el "punto de multiplicación" correspondientes[i, j]. Por ejemplo, si estamos multiplicando la cadena A₁×A₂×A₃×A₄, y resulta que m[1, 3] = 100 y s[1, 3] = 2, eso significa que la colocación óptima de paréntesis para matrices 1 a 3 es ${displaystyle (A_{1}times A_{2}times A_{3}$ y multiplicar esas matrices requerirá 100 cálculos de escalar.

Este algoritmo producirá "tablas" m[, ] y s[, ] que tendrán entradas para todos los valores posibles de i y j. La solución final para toda la cadena es m[1, n], con la división correspondiente en s[1, n]. Desentrañar la solución será recursivo, comenzando desde arriba y continuando hasta llegar al caso base, es decir, la multiplicación de matrices simples.

Por lo tanto, el siguiente paso es dividir la cadena, es decir, colocar los paréntesis donde (óptimamente) pertenecen. Para ello podríamos utilizar el siguiente algoritmo:

función PrintOptimalParenthesis(s, i, j)
 si I = j
imprimir "A"i
 másimprimir "("
PrintOptimalParenthesis(s, i, s[i, j])
PrintOptimalParenthesis(s, s[i, j] + 1, j)
imprimir ")"

Por supuesto, este algoritmo no es útil para la multiplicación real. Este algoritmo es solo una forma fácil de usar para ver cómo se ve el resultado.

Para multiplicar las matrices utilizando las divisiones adecuadas, necesitamos el siguiente algoritmo:

 función MatrixChainMultiply()cadena desde 1 a n) // devuelve la matriz final, es decir, A1×A2×... × OptimalMatrixChainParenthesis()cadena desde 1 a n) // esto producirá s [. ] y m [. ] "tables" OptimalMatrixMultiplication()s, cadena desde 1 a n) // realmente multiplicar función OptimalMatrixMultiplication()s, i, j) // devuelve el resultado de multiplicar una cadena de matrices de Ai a Aj de manera óptima si i . j // seguir dividiendo la cadena y multiplicando las matrices en los lados izquierdo y derecho LeftSide = OptimalMatrixMultiplication()s, i, s[i, j]) RightSide = OptimalMatrixMultiplication()s, s[i, j] + 1, j) retorno MatrixMultiply()LeftSide, RightSide) más si i = j retorno Ai // matriz en la posición i más impresión "El terror, yo... función MatrixMultiply()A, B) // función que multiplica dos matrices si columnas()A) = filas()B) para i = 1, filas()A) para j = 1, columnas()B) C[i, j] = 0 para k = 1, columnas()A) C[i, j] = C[i, j] + A[i, k]*B[k, j] retorno C más impresión "error, dimensiones incompatibles".

Historia

El término programación dinámica fue utilizado originalmente en la década de 1940 por Richard Bellman para describir el proceso de resolución de problemas donde uno necesita encontrar las mejores decisiones una tras otra. En 1953, refinó esto al significado moderno, refiriéndose específicamente a anidar problemas de decisión más pequeños dentro de decisiones más grandes, y el IEEE reconoció el campo a partir de entonces como un tema de ingeniería y análisis de sistemas. La contribución de Bellman se recuerda en el nombre de la ecuación de Bellman, un resultado central de la programación dinámica que reformula un problema de optimización en forma recursiva.

Bellman explica el razonamiento detrás del término programación dinámica en su autobiografía, Eye of the Hurricane: An Autobiography:

Pasé el trimestre de otoño (de 1950) en RAND. Mi primera tarea era encontrar un nombre para los procesos de decisión multietapa. Una pregunta interesante es: "¿De dónde vino el nombre, la programación dinámica?" Los años 50 no fueron buenos años para la investigación matemática. Teníamos un caballero muy interesante en Washington llamado Wilson. Fue Secretario de Defensa, y en realidad tuvo un miedo patológico y odio a la palabra "investigación". No estoy usando el término ligeramente; lo estoy usando precisamente. Su cara bastaría, se volvería roja, y se volvería violento si la gente utilizaba el término investigación en su presencia. Puedes imaginar cómo se sentía, entonces, sobre el término matemático. La Corporación RAND fue empleada por la Fuerza Aérea, y la Fuerza Aérea tenía a Wilson como su jefe, esencialmente. Por lo tanto, sentí que tenía que hacer algo para proteger a Wilson y la Fuerza Aérea del hecho de que realmente estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre, podría elegir? En primer lugar me interesaba planear, en la toma de decisiones, pensar. Pero la planificación no es una buena palabra por varias razones. Por lo tanto decidí usar la palabra "programación". Quería cruzar la idea de que esto era dinámico, esto era multietapa, esto era de tiempo. Pensé que mataríamos a dos pájaros con una piedra. Tomemos una palabra que tiene un significado absolutamente preciso, a saber, dinámico, en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y eso es imposible utilizar la palabra dinámica en un sentido peyorativo. Trate de pensar en alguna combinación que posiblemente le dará un significado peyorativo. Es imposible. Así, pensé que la programación dinámica era un buen nombre. Era algo que ni siquiera un congresista podía oponerse. Así que lo usé como paraguas para mis actividades.

—Richard Bellman, Ojo del Huracán: una autobiografía (1984, pág. 159)

La palabra dinámico fue elegida por Bellman para capturar el aspecto variable en el tiempo de los problemas, y porque sonaba impresionante. La palabra programación se refería al uso del método para encontrar un programa óptimo, en el sentido de un calendario militar para entrenamiento o logística. Este uso es el mismo que el de las frases programación lineal y programación matemática, un sinónimo de optimización matemática.

Falta la explicación anterior del origen del término. Como escribieron Russell y Norvig en su libro, refiriéndose a la historia anterior: "Esto no puede ser estrictamente cierto, porque su primer artículo en el que utilizó el término (Bellman, 1952) apareció antes de que Wilson se convirtiera en Secretario de Defensa en 1953". 34; Además, hay un comentario en un discurso de Harold J. Kushner, donde recuerda a Bellman. Citando a Kushner cuando habla de Bellman: “Por otro lado, cuando le hice la misma pregunta, respondió que estaba tratando de eclipsar la programación lineal de Dantzig agregando dinámica. Quizá ambas motivaciones eran ciertas."

Algoritmos que usan programación dinámica

• Soluciones recurrentes a modelos de celosía para la unión proteína-DNA
• Inducción de retroceso como método de solución para problemas de optimización discreta-tiempo finito
• El método de los coeficientes indeterminados se puede utilizar para resolver la ecuación Bellman en problemas de optimización dinámica infinita-horizon, discreto-time, descontado, invariante
• Muchos algoritmos de cuerda incluyendo la subsecuencia común más larga, subsequencia creciente más larga, subestring común más larga, Levenshtein distancia (edit distancia)
• Muchos problemas algorítmicos en los gráficos se pueden resolver eficientemente para gráficos de ancho de árbol atado o ancho de camarilla atada mediante la programación dinámica en una descomposición de árboles del gráfico.
• El algoritmo Cocke-Younger-Kasami (CYK) que determina si una cadena dada puede ser generada por una gramática libre de contexto determinada
• algoritmo de envolvimiento de palabras de Knuth que minimiza la rareza al envolver texto
• El uso de tablas de transposición y tablas de refutación en ajedrez de computadora
• El algoritmo Viterbi (utilizado para los modelos de Markov ocultos, y especialmente en parte de la etiqueta del discurso)
• El algoritmo de Earley (un tipo de parser gráfico)
• El algoritmo Needleman–Wunsch y otros algoritmos utilizados en bioinformática, incluyendo alineación de secuencias, alineación estructural, predicción de la estructura RNA
• El algoritmo de trayectoria más corto de Floyd
• Optimización del orden de multiplicación de matriz de cadena
• Pseudo-polynomial time algoritmos para el subset sum, knapsack y problemas de partición
• El algoritmo de tiempo dinámico para calcular la distancia global entre dos series temporales
• El algoritmo Selinger (a.k.a. System R) para la optimización de las consultas de bases de datos relacionales
• De Boor algoritmo para evaluar curvas B-spline
• Método Duckworth-Lewis para resolver el problema cuando se interrumpen los juegos de cricket
• El método de iteración de valor para resolver los procesos de decisión Markov
• Algunos bordes de imagen gráfica siguiendo métodos de selección como la herramienta de selección "imanet" en Photoshop
• Algunos métodos para resolver problemas de programación de intervalos
• Algunos métodos para resolver el problema de los vendedores ambulantes, ya sea exactamente (en tiempo exponencial) o aproximadamente (por ejemplo, a través de la gira bitónica)
• Método Recursive menos cuadrados
• Rastreo de información musical
• Estrategia de capacitación de crítica adaptativa para redes neuronales artificiales
• algoritmos de estereo para resolver el problema de correspondencia utilizado en la visión estéreo
• Sellado (contenido-consejo para el tamaño de la imagen)
• El algoritmo Bellman-Ford para encontrar la distancia más corta en un gráfico
• Algunos métodos de solución aproximados para el problema de búsqueda lineal
• El algoritmo de Kadane para el problema de subarray máximo
• Optimización de los planes de expansión de generación eléctrica en el paquete de planificación del sistema automático de Wein (WASP)