Programación dinámica

Problem optimization method

Figura 1. Encontrar el camino más corto en un gráfico usando una 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 mostrados, que comparten los mismos dos vértices); la línea en negrita es el camino más corto general desde el inicio hasta el objetivo.

La programación dinámica es a la vez un método de optimización matemática y un paradigma algorítmico . 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 descomponiéndolo en subproblemas más simples de manera recursiva . Si bien algunos problemas de decisión no se pueden descomponer de esta manera, las decisiones que abarcan varios puntos en el tiempo a menudo se descomponen de manera recursiva. Del mismo modo, en informática, si un problema se puede resolver de manera óptima dividiéndolo en subproblemas y luego encontrando recursivamente las soluciones óptimas para 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. ^[1] En la literatura de optimización, esta relación se denomina ecuación de Bellman .

Descripción general

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 los tiempos i desde 1 hasta n .

La definición de V _n ( y ) es el valor obtenido en el estado y en el último tiempo n .

Los valores V _i en tiempos anteriores i  =  n  −1,  n  − 2, ..., 2, 1 se pueden encontrar trabajando al revé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 momento i  − 1 y la función V _i en el nuevo estado del sistema si se toma esta decisión.

Dado que V _i ya se ha 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, siguiendo los cálculos ya realizados.

Teoría del control

En la teoría de control , un problema típico es encontrar un control admisible que haga que el sistema siga una trayectoria admisible en un intervalo de tiempo continuo que minimice una función de costo. ${\displaystyle \mathbf {u} ^{\ast }}$ ${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$ ${\displaystyle \mathbf {x} ^{\ast }}$ ${\displaystyle t_{0}\leq t\leq t_{1}}$

${\displaystyle J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t}$

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

${\displaystyle -J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}}$

una ecuación diferencial parcial conocida como ecuación de Hamilton–Jacobi–Bellman , en la que y . Se encuentra que al minimizar en términos de , , y la función desconocida y luego se sustituye el resultado en la ecuación de Hamilton–Jacobi–Bellman para obtener la ecuación diferencial parcial que se resolverá con la condición de contorno . ^[2] En la práctica, esto generalmente requiere técnicas numéricas para alguna aproximación discreta a la relación de optimización exacta. ${\displaystyle J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}}$ ${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$ ${\displaystyle \mathbf {u} }$ ${\displaystyle t}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle J_{x}^{\ast }}$ ${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$

Alternativamente, el proceso continuo puede aproximarse 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 J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {\mathbf {g} }}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}}$

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

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

En economía, el objetivo es generalmente maximizar (en lugar de minimizar) alguna función dinámica de bienestar social . En el problema de Ramsey, esta función relaciona las cantidades de consumo con los niveles de utilidad . En términos generales, el planificador se enfrenta a la disyuntiva entre el consumo contemporáneo y el consumo futuro (a través de la inversión en stock de capital que se utiliza en la producción), conocida como elección intertemporal . El consumo futuro se descuenta a una tasa constante . Una aproximación discreta a la ecuación de transición del capital está dada por ${\displaystyle \beta \in (0,1)}$

${\displaystyle k_{t+1}={\hat {g}}\left(k_{t},c_{t}\right)=f(k_{t})-c_{t}}$

donde es el consumo, es el capital y es una función de producción que satisface las condiciones de Inada . Se supone un stock de capital inicial. ${\displaystyle c}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle k_{0}>0}$

Sea el consumo en el periodo t , y supongamos que el consumo produce utilidad mientras el consumidor vive. Supongamos que el consumidor es impaciente, de modo que descuenta la utilidad futura por un factor b cada periodo, donde . Sea el capital en el periodo t . Supongamos que el capital inicial es una cantidad dada , y supongamos que el capital y el consumo de este periodo determinan el capital del siguiente periodo como , donde A es una constante positiva y . Supongamos que el capital no puede ser negativo. Entonces el problema de decisión del consumidor puede escribirse de la siguiente manera: ${\displaystyle c_{t}}$ ${\displaystyle u(c_{t})=\ln(c_{t})}$ ${\displaystyle 0<b<1}$ ${\displaystyle k_{t}}$ ${\displaystyle k_{0}>0}$ ${\displaystyle k_{t+1}=Ak_{t}^{a}-c_{t}}$ ${\displaystyle 0<a<1}$

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

Escrito de esta manera, el problema parece complicado, porque implica resolver todas las variables de elección (el capital no es una variable de elección: el capital inicial del consumidor se considera dado). ${\displaystyle c_{0},c_{1},c_{2},\ldots ,c_{T}}$ ${\displaystyle k_{0}}$

El enfoque de programación dinámica para resolver este problema implica dividirlo en una secuencia de decisiones más pequeñas. Para ello, definimos una secuencia de funciones de valor , para las cuales , representa el valor de tener cualquier cantidad de capital k en cada momento t . No hay (por supuesto) utilidad alguna por tener capital después de la muerte, . ${\displaystyle V_{t}(k)}$ ${\displaystyle t=0,1,2,\ldots ,T,T+1}$ ${\displaystyle V_{T+1}(k)=0}$

El valor de cualquier cantidad de capital en cualquier momento anterior se puede calcular por inducción hacia atrás utilizando la ecuación de Bellman . En este problema, para cada , la ecuación de Bellman es ${\displaystyle t=0,1,2,\ldots ,T}$

${\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 involucra solo dos variables de decisión, y . Intuitivamente, en lugar de elegir todo su plan de vida al nacer, el consumidor puede tomar las cosas paso a paso. En el momento t , su capital actual está dado y solo necesita elegir el consumo actual y el ahorro . ${\displaystyle c_{t}}$ ${\displaystyle k_{t+1}}$ ${\displaystyle k_{t}}$ ${\displaystyle c_{t}}$ ${\displaystyle k_{t+1}}$

Para resolver este problema, trabajamos al revés. Para simplificar, el nivel actual de capital se denota como k . ya se conoce, por lo que utilizando la ecuación de Bellman una vez podemos calcular , y así sucesivamente hasta llegar a , que es el valor del problema de decisión inicial para toda la vida. En otras palabras, una vez que sabemos , podemos calcular , que es el máximo de , donde es la variable de elección y . ${\displaystyle V_{T+1}(k)}$ ${\displaystyle V_{T}(k)}$ ${\displaystyle V_{0}(k)}$ ${\displaystyle V_{T-j+1}(k)}$ ${\displaystyle V_{T-j}(k)}$ ${\displaystyle \ln(c_{T-j})+bV_{T-j+1}(Ak^{a}-c_{T-j})}$ ${\displaystyle c_{T-j}}$ ${\displaystyle Ak^{a}-c_{T-j}\geq 0}$

Trabajando a la inversa, se puede demostrar que la función de valor en el momento es ${\displaystyle t=T-j}$

${\displaystyle V_{T-j}(k)\,=\,a\sum _{i=0}^{j}a^{i}b^{i}\ln k+v_{T-j}}$

donde cada uno es una constante y la cantidad óptima a consumir en cada momento es ${\displaystyle v_{T-j}}$ ${\displaystyle t=T-j}$

${\displaystyle c_{T-j}(k)\,=\,{\frac {1}{\sum _{i=0}^{j}a^{i}b^{i}}}Ak^{a}}$

que puede simplificarse a

${\displaystyle {\begin{aligned}c_{T}(k)&=Ak^{a}\\c_{T-1}(k)&={\frac {Ak^{a}}{1+ab}}\\c_{T-2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}}}\\&\dots \\c_{2}(k)&={\frac {Ak^{a}}{1+ab+a^{2}b^{2}+\ldots +a^{T-2}b^{T-2}}}\\c_{1}(k)&={\frac {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}b^{T}}}\end{aligned}}}$

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

Ciencias de la Computación

Hay dos atributos clave que un problema debe tener para que la programación dinámica sea aplicable: subestructura óptima y subproblemas superpuestos . Si un problema se puede resolver combinando soluciones óptimas con subproblemas que no se superponen , la estrategia se denomina " dividir y vencer ". ^[1] Es por esto 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 puede obtenerse mediante la combinación de soluciones óptimas a sus subproblemas. Tales subestructuras óptimas se describen usualmente por medio de recursión . Por ejemplo, dado un grafo G=(V,E) , el camino más corto p desde un vértice u a un vértice v exhibe subestructura óptima: tome cualquier vértice intermedio w en este camino más corto p . Si p es verdaderamente el camino más corto, entonces puede dividirse en subcaminos p ₁ desde u a w y p ₂ desde 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, uno puede formular fácilmente la solución para encontrar caminos más cortos de manera recursiva, que es lo que hace el algoritmo Bellman-Ford o el algoritmo Floyd-Warshall .

La superposición de subproblemas significa que el espacio de subproblemas debe ser pequeño, es decir, cualquier algoritmo recursivo que resuelva el problema debería resolver los mismos subproblemas una y otra vez, en lugar de generar nuevos subproblemas. Por ejemplo, considere la formulación recursiva para generar la secuencia 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 solo una vez.

Figura 2. Gráfico de subproblemas de la secuencia de Fibonacci. El hecho de que no sea un árbol indica que hay subproblemas superpuestos.

Esto se puede lograr de dos maneras: ^{[ cita requerida ]}

• Enfoque de arriba hacia abajo : esta es la consecuencia directa de la formulación recursiva de cualquier problema. Si la solución de cualquier problema se puede formular recursivamente utilizando la solución de sus subproblemas, y si sus subproblemas se superponen, entonces uno puede memorizar o almacenar fácilmente las soluciones de los subproblemas en una tabla. Siempre que intentamos resolver un nuevo subproblema, primero revisamos la tabla para ver si ya está resuelto. Si se ha registrado una solución, podemos usarla directamente; de ​​lo contrario, resolvemos el subproblema y agregamos su solución a la tabla.
• Enfoque de abajo hacia arriba : una vez que formulamos la solución a un problema de forma recursiva en términos de sus subproblemas, podemos intentar reformular el problema de forma de abajo hacia arriba: intentar resolver primero los subproblemas y usar sus soluciones para desarrollar y llegar a soluciones para subproblemas más grandes. Esto también suele hacerse en forma de tabla generando iterativamente soluciones para subproblemas cada vez más grandes mediante el uso de las soluciones de subproblemas pequeños. Por ejemplo, si ya conocemos los valores de F ₄₁ y F ₄₀ , podemos calcular directamente el valor de F ₄₂ .

Algunos lenguajes de programación pueden memorizar automáticamente el resultado de una llamada a una 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 lenguajes lo hacen posible de forma portátil (por ejemplo, Scheme , Common Lisp , Perl o D ). Algunos lenguajes tienen memorización automática incorporada, como Prolog y J , que admiten la memorización con el adverbio M. ^[4] En cualquier caso, esto solo 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 lenguajes basados ​​en reescritura de términos, como Wolfram Language .

Bioinformática

La programación dinámica se utiliza ampliamente en bioinformática para tareas como la alineación de secuencias , el plegamiento de proteínas , la predicción de la estructura del ARN y la unión proteína-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 los EE. UU. ^[5] y por Georgii Gurskii y Alexander Zasedatelev en la Unión Soviética . ^[6] 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 un punto de vista de programación dinámica, el algoritmo de Dijkstra para el problema de la ruta más corta es un esquema de aproximación sucesiva que resuelve la ecuación funcional de programación dinámica para el problema de la ruta más corta mediante el método Reaching . ^{[7] [8] [9]}

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

Problema 2. Encuentra la ruta de longitud total mínima entre dos nodos dados y . ${\displaystyle P}$ ${\displaystyle Q}$

Utilizamos el hecho de que, si es un nodo en la ruta mínima de a , el conocimiento de este último implica el conocimiento de la ruta mínima de a . ${\displaystyle R}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle P}$ ${\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

El uso de programación dinámica en el cálculo del miembro n de la sucesión de Fibonacci mejora considerablemente su rendimiento. A continuación se muestra una implementación sencilla, basada directamente en la definición matemática:

función fib(n) si n <= 1 devuelve n devuelve fib(n − 1) + fib(n − 2)

Tenga en cuenta 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 vuelven a calcular muchos más valores de fib, o subproblemas , lo que da lugar a un algoritmo de tiempo exponencial.

Ahora, supongamos que tenemos un objeto de mapa simple, m , que asigna cada valor de fibque ya se ha calculado a su resultado, y modificamos nuestra función para usarlo y actualizarlo. La función resultante requiere solo O ( n ) tiempo en lugar de tiempo exponencial (pero requiere O ( n ) espacio):

var m := map (0 → 0, 1 → 1) función fib(n) si la clave n no está en el mapa m m[n] := fib(n − 1) + fib(n − 2) devuelve m[n]

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

En el enfoque ascendente , calculamos fibprimero los valores más pequeños y luego construimos valores más grandes a partir de ellos. Este método también utiliza tiempo O( n ), ya que contiene un bucle que se repite n − 1 veces, pero solo ocupa un espacio constante (O(1)), a diferencia del enfoque descendente que requiere espacio O( n ) para almacenar el mapa.

función fib(n) si n = 0 devuelve 0 de lo contrario  var previousFib := 0, currentFib := 1 repite n − 1 veces  // el bucle se omite si n = 1  var newFib := previousFib + currentFib FibAnterior := FibActual actualFib := nuevaFib Devuelve la 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 equilibrada 0-1

Consideremos el problema de asignar valores, ya sea cero o uno, a las posiciones de una matriz n × n , con n par, de modo que cada fila y cada columna contenga exactamente n /2 ceros y n /2 unos. Nos preguntamos cuántas asignaciones diferentes hay para un determinado . Por ejemplo, cuando n = 4 , hay cinco posibles soluciones ${\displaystyle n}$

${\displaystyle {\begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}0&0&1&1\\0&0&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&1&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&0&0&1\\0&1&1&0\\0&1&1&0\\1&0&0&1\end{bmatrix}}{\text{ and }}{\begin{bmatrix}1&1&0&0\\1&1&0&0\\0&0&1&1\\0&0&1&1\end{bmatrix}}.}$

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 unos y contar aquellas que tienen filas y columnas equilibradas ( n /2 ceros y n /2 unos). Como hay asignaciones posibles y asignaciones sensatas, esta estrategia no es práctica excepto quizás hasta . ${\displaystyle 2^{n^{2}}}$ ${\displaystyle {\tbinom {n}{n/2}}^{n}}$ ${\displaystyle n=6}$

El retroceso para este problema consiste en elegir un orden de los elementos de la matriz y colocar recursivamente unos o ceros, mientras se comprueba 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 sean ambos al 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 mayor que seis, ya que el número 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. Imaginemos que retrocedemos los valores de la primera fila: ¿qué información necesitaríamos sobre las filas restantes para poder contar con precisión las soluciones obtenidas para cada valor de la primera fila? Consideramos k × n tableros, donde 1 ≤ k ≤ n , cuyas filas contienen ceros y unos. La función f a la que se aplica la memorización asigna vectores de n pares de números enteros al número de tableros admisibles (soluciones). Hay un par para cada columna, y sus dos componentes indican respectivamente el número de ceros y unos que aún deben colocarse en esa columna. Buscamos el valor de ( argumentos o un vector de elementos). El proceso de creación de subproblemas implica iterar sobre cada una de las asignaciones posibles para la fila superior del tablero y recorrer 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 un uno en esa posición. Si alguno de los resultados es negativo, entonces la asignación no es válida y no contribuye al conjunto de soluciones (la recursión se detiene). De lo contrario, tenemos una asignación para la fila superior del tablero k × n y calculamos recursivamente el número de soluciones para el tablero ( k − 1) × n restante , sumando los números de soluciones para cada asignación admisible de la fila superior y devolviendo la suma, que se está memorizando. El caso base es el subproblema trivial, que ocurre para un tablero 1 × n . El número de soluciones para este tablero es cero o uno, dependiendo de si el vector es una permutación de n / 2 y n / 2 pares o no. ${\displaystyle k}$ ${\displaystyle n/2}$ ${\displaystyle n/2}$ ${\displaystyle f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {n}{n/2}}}$ ${\displaystyle (0,1)}$ ${\displaystyle (1,0)}$

Por ejemplo, en los dos primeros tableros mostrados 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 1 0 0 1 1((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3 1 0 1 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 1 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 la 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 damas

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 (i,j)( isiendo la fila, jsiendo la columna). Por ejemplo (en un tablero de ajedrez de 5 × 5),

De este modoc(1, 3) = 5

Digamos que hay una ficha que puede empezar en cualquier casilla de la primera fila (es decir, fila) y quieres saber el camino más corto (la suma de los costes mínimos en cada fila visitada) para llegar a la última fila; suponiendo que la ficha solo puede moverse en diagonal hacia la izquierda hacia adelante, en diagonal hacia la derecha hacia adelante o en línea recta. Es decir, una ficha en (1,3)puede moverse (2,2)a (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 coste mínimo para alcanzar el cuadrado ( i , j ).

Comenzando por el rango ny descendiendo hasta el 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 ny el rango 1.

La función q(i, j)es igual al costo mínimo para llegar a cualquiera de los tres cuadrados que se encuentran debajo (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>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}}$

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

función minCost(i, j) si j < 1 o j > n devuelve infinito de lo contrario si i = 1 devuelve c(i, j) de lo contrario  devuelve  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. Analizaremos 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 de 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 manera 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 sea necesario.

También necesitamos saber cuál es el camino más corto real. Para ello, utilizamos otra matriz p[i, j]; una matriz predecesora . Esta matriz registra la ruta a cualquier cuadrado s. El predecesor de sse modela como un desplazamiento relativo al índice (en q[i, j]) del costo de ruta precalculado 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 que llegamos al cuadrado inicial. Considere el siguiente pseudocódigo:

Función calculateShortestPathArrays() para x de 1 a n q[1, x] := c(1, x) para y de 1 a n q[y, 0] := infinito q[y, n + 1] := infinito para y de 2 a n para x de 1 a n m := mín(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 de lo contrario si m = q[y-1, x] p[y, x] := 0 demás p[y, x] := 1

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

Función calculateShortestPath() calcularArraysDePathMásCortas() índice mínimo := 1 mín := q[n, 1] para i de 2 a n si q[n, i] < min índice mínimo := i mín := q[n, i] printPath(n, minÍndice)

función printPath(y, x) imprimir (x) imprimir ("<-") si y = 2 imprimir (x + p[y, x]) de lo contrario imprimirRuta(y-1, x + p[y, x])

Alineación de secuencias

En genética , el alineamiento de secuencias es una aplicación importante donde la programación dinámica es esencial. ^[11] 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 menor costo total .

El problema se puede plantear de forma natural como una recursión: una secuencia A se edita de forma óptima en una secuencia B mediante:

1. insertando el primer carácter de B y realizando una alineación óptima de A y la cola de B
2. eliminando el primer carácter de A y realizando la alineación óptima de la cola de A y B
3. reemplazando el primer carácter 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 las celdas vecinas y seleccionando la óptima.

Existen diferentes variantes, véase algoritmo Smith-Waterman y algoritmo Needleman-Wunsch .

Rompecabezas de la Torre de Hanoi

Un juego de maquetas de las Torres de Hanoi (con 8 discos)

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

La Torre de Hanoi o Torres de Hanoi es un juego matemático o rompecabezas . Consiste en tres varillas y una serie de discos de diferentes tamaños que se pueden deslizar sobre cualquier varilla. El rompecabezas comienza con los discos en una pila ordenada en orden ascendente de tamaño sobre una varilla, 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 varilla, obedeciendo las siguientes reglas:

• Sólo se puede mover un disco a la vez.
• Cada movimiento consiste en tomar el disco superior de una de las varillas y deslizarlo sobre otra varilla, encima de los otros discos que ya puedan estar presentes en esa varilla.
• No se podrá colocar ningún disco encima de otro 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, no(h,t)); S(1,h,t); S(n-1,no(h,t),t)

donde n denota el número de discos a mover, h denota la varilla de origen, t denota la varilla de destino, not(h,t) denota la tercera varilla (ni h ni t), ";" denota concatenación, y

S(n, h, t) := solución a un problema que consta de n discos que se deben mover de la varilla h a la varilla t.

Para n=1 el problema es trivial, es decir, S(1,h,t) = "mover un disco de la varilla h a la varilla t" (sólo queda un disco).

El número de movimientos requeridos por esta solución es 2 ⁿ  − 1. Si el objetivo es maximizar el número de movimientos (sin ciclar), entonces la ecuación funcional de programación dinámica es ligeramente más complicada y  se requieren 3 ^{n − 1 movimientos. [12]}

Rompecabezas de la caída de huevos

A continuación se describe la instancia de este famoso rompecabezas que involucra N=2 huevos y un edificio con H=36 pisos: ^[13]

Supongamos que queremos saber desde qué pisos de un edificio de 36 pisos es seguro arrojar huevos y cuáles harán que los huevos se rompan al caer (usando la terminología del inglés estadounidense , en la que el primer piso está al nivel del suelo). Hacemos algunas suposiciones:

• Un huevo que sobrevive a una caída puede volver a usarse.
• Un huevo roto debe desecharse.
• El efecto de una caída es el mismo para todos los huevos.
• Si un huevo se rompe al caerse, también se rompería si se dejara caer desde una ventana alta.
• Si un huevo sobrevive a una caída, entonces sobreviviría a una caída más corta.
• No se descarta que las ventanas del primer piso rompan huevos, ni tampoco se descarta que los huevos puedan sobrevivir a las ventanas del piso 36.

Si sólo se dispone de un huevo y queremos estar seguros de obtener el resultado correcto, el experimento sólo se puede llevar a cabo de una manera. Se deja caer el huevo desde la ventana del primer piso; si sobrevive, se deja caer desde la ventana del segundo piso. Se continúa hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 36 caídas. Supongamos que se dispone de 2 huevos. ¿Cuál es el número mínimo de caídas de huevos que se garantiza que funcionará en todos los casos?

Para derivar una ecuación funcional de programación dinámica para este rompecabezas, sea el estado del modelo de programación dinámica 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 quedan por probar, k = 0, 1, 2, ..., H  − 1.

Por ejemplo, s = (2,6) indica que hay dos huevos de prueba disponibles y que aún quedan 6 pisos (consecutivos) por probar. El estado inicial del proceso es s = ( N , H ) donde N denota la cantidad 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, dejemos que

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

Entonces se puede demostrar que ^[14]

W ( n , k ) = 1 + mín{máx( W ( n − 1, x − 1), W ( n , k − x )): x = 1, 2, ..., k }

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

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

Tenga en cuenta que la solución anterior lleva tiempo con una solución DP. Esto se puede mejorar a tiempo mediante una búsqueda binaria en el óptimo en la recurrencia anterior, ya que es creciente en mientras que es decreciente en , por lo tanto, un mínimo local de es un mínimo global. Además, al almacenar el óptimo para cada celda en la tabla DP y hacer referencia a su valor para la celda anterior, se puede encontrar el óptimo para cada celda en tiempo constante, lo que lo mejora a tiempo. Sin embargo, existe una solución aún más rápida que implica una parametrización diferente del problema: ${\displaystyle O(nk^{2})}$ ${\displaystyle O(nk\log k)}$ ${\displaystyle x}$ ${\displaystyle W(n-1,x-1)}$ ${\displaystyle x}$ ${\displaystyle W(n,k-x)}$ ${\displaystyle x}$ ${\displaystyle \max(W(n-1,x-1),W(n,k-x))}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle O(nk)}$

Sea el número total de pisos tales que los huevos se rompen al caer desde el piso (el ejemplo anterior es equivalente a tomar ). ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k=37}$

Sea el piso mínimo desde el cual se debe dejar caer el huevo para romperlo. ${\displaystyle m}$

Sea el número máximo de valores de que se pueden distinguir utilizando tries y eggs. ${\displaystyle f(t,n)}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle n}$

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

Sea el piso desde el que se deja caer el primer huevo en la estrategia óptima. ${\displaystyle a}$

Si el primer huevo se rompe, es de a y distinguible usando como máximo intentos y huevos. ${\displaystyle m}$ ${\displaystyle 1}$ ${\displaystyle a}$ ${\displaystyle t-1}$ ${\displaystyle n-1}$

Si el primer huevo no se rompe, se puede distinguir entre intentos y huevos. ${\displaystyle m}$ ${\displaystyle a+1}$ ${\displaystyle k}$ ${\displaystyle t-1}$ ${\displaystyle n}$

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 tal que . ${\displaystyle x}$ ${\displaystyle f(x,n)\geq k}$

Para ello, podríamos calcular en orden creciente , lo que llevaría tiempo. ${\displaystyle \{f(t,i):0\leq i\leq n\}}$ ${\displaystyle t}$ ${\displaystyle O(nx)}$

Por lo tanto, si tratamos por separado el caso de , el algoritmo tomaría tiempo. ${\displaystyle n=1}$ ${\displaystyle O(n{\sqrt {k}})}$

Pero la relación de recurrencia de hecho se puede resolver, dando , que se puede calcular en el tiempo usando la identidad para todo . ${\displaystyle f(t,n)=\sum _{i=0}^{n}{\binom {t}{i}}}$ ${\displaystyle O(n)}$ ${\displaystyle {\binom {t}{i+1}}={\binom {t}{i}}{\frac {t-i}{i+1}}}$ ${\displaystyle i\geq 0}$

Dado que para todos , podemos realizar una búsqueda binaria para encontrar , obteniendo un algoritmo. ^[15] ${\displaystyle f(t,n)\leq f(t+1,n)}$ ${\displaystyle t\geq 0}$ ${\displaystyle t}$ ${\displaystyle x}$ ${\displaystyle O(n\log k)}$

Multiplicación de cadenas de matrices

La multiplicación de matrices en cadena es un ejemplo bien conocido que demuestra la utilidad de la 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 . La ${\displaystyle A_{1},A_{2},....A_{n}}$ multiplicación de matrices no es conmutativa, sino asociativa; y podemos multiplicar solo dos matrices a la vez. Por lo tanto, podemos multiplicar esta cadena de matrices de muchas formas diferentes, por ejemplo:

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

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

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

y así sucesivamente. Existen numerosas formas de multiplicar esta cadena de matrices. Todas ellas producirán el mismo resultado final, sin embargo, llevarán más o menos tiempo calcularlas, en función de qué matrices en particular 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á multiplicaciones escalares m*n*q (usando un algoritmo de multiplicación de matrices simplista para fines ilustrativos).

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 tendrá un tamaño m×s y se puede calcular de dos maneras, como se muestra a continuación:

1. Ax(B×C) Este orden de multiplicación de matrices requerirá nps + mns multiplicaciones escalares.
2. (A×B)×C Este orden de multiplicación de matrices requerirá cálculos escalares 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 utilizando esa disposición de paréntesis.

Por lo tanto, nuestra conclusión es que el orden de los paréntesis importa 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 divida el problema en problemas superpuestos y calcule la disposición óptima de los paréntesis. La solución de programación dinámica se presenta a continuación.

Llamemos m[i,j] al 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 intentamos averiguar qué combinación produce el mínimo m[i,j].

La fórmula es:

 si i = j, m[i,j]= 0 si i < 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 MatrizÓptimaCadenaParéntesis(cadena) n = longitud(cadena) para i = 1, n m[i,i] = 0 // Dado que no se necesitan cálculos para multiplicar una matriz  para len = 2, n para i = 1, n - len + 1 j = i + len -1 m[i,j] = infinito // Para que el primer cálculo se actualice  para k = i, j-1 q = m[i, k] + m[k+1, j] +  ${\displaystyle p_{i-1}*p_{k}*p_{j}}$ si q < m[i, j] // El nuevo orden de paréntesis es mejor que el que teníamos m[i, j] = q // Actualizar s[i, j] = k // Registrar en qué k dividir, es decir, dónde colocar el paréntesis

Hasta ahora, hemos calculado valores para todos los m [ i , j ] posibles , el número mínimo de cálculos para multiplicar una cadena de la matriz i a la matriz j , y hemos registrado el "punto de división" correspondiente s [ 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 ubicación óptima de los paréntesis para las matrices 1 a 3 es ⁠ ⁠ ${\displaystyle (A_{1}\times A_{2})\times A_{3}}$ y para multiplicar esas matrices se requerirán 100 cálculos escalares.

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]. El desenlace de la solución será recursivo, comenzando desde arriba y continuando hasta llegar al caso base, es decir, la multiplicación de matrices individuales.

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

función PrintOptimalParenthesis(s, i, j) si i = j imprimir "A"i demás imprimir "(" ImprimirParéntesisÓptimo(s, i, s[i, j]) ImprimirParéntesisÓptimo(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 sencilla de ver cómo se ve el resultado.

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

 función MatrixChainMultiply ( cadena de 1 a n ) // devuelve la matriz final, es decir A1×A2×... ×An OptimalMatrixChainParenthesis ( cadena de 1 a n ) // esto producirá s[ . ] y m[ . ] "tablas" OptimalMatrixMultiplication ( s , cadena de 1 a n ) // en realidad multiplica                    function OptimalMatrixMultiplication ( s , i , j ) // devuelve el resultado de multiplicar una cadena de matrices de Ai a Aj de forma óptima si i < j // sigue 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 ) return MatrixMultiply ( LeftSide , RightSide ) else if i = j return Ai // matriz en la posición i else print "error, i <= j debe cumplirse"                                        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 ] devuelve C de lo contrario imprime "error, dimensiones incompatibles".                                            

Historia del nombre

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 en los que se necesita encontrar las mejores decisiones una tras otra. En 1953, lo perfeccionó hasta alcanzar el significado moderno, refiriéndose específicamente a la anidación de problemas de decisión más pequeños dentro de decisiones más grandes, ^[16] y, a partir de entonces, el campo fue reconocido por el IEEE como un tema de análisis e ingeniería de sistemas . La contribución de Bellman se recuerda con 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 fue encontrar un nombre para los procesos de decisión de múltiples etapas. Una pregunta interesante es: "¿De dónde surgió el nombre, programación dinámica?". Los años 50 no fueron buenos para la investigación matemática. Teníamos un caballero muy interesante en Washington llamado Wilson . Era Secretario de Defensa, y en realidad tenía un miedo y un odio patológicos a la palabra "investigación". No estoy usando el término a la ligera; lo estoy usando con precisión. Su rostro se ponía rojo y se ponía violento si la gente usaba el término investigación en su presencia. Pueden imaginar cómo se sentía, entonces, sobre el término matemático. La Corporación RAND estaba 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 a la Fuerza Aérea del hecho de que en realidad estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre, podía elegir? En primer lugar, estaba interesado en la planificación, en la toma de decisiones, en el pensamiento. Pero planificación no es una buena palabra por varias razones. Por eso decidí utilizar la palabra "programación". Quería transmitir la idea de que se trataba de algo dinámico, de varias etapas, que variaba con el tiempo. Pensé: matemos dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente preciso, es decir, dinámico, en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y es que es imposible utilizar la palabra dinámico en un sentido peyorativo. Trate de pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por eso pensé que "programación dinámica" era un buen nombre. Era algo a lo que ni siquiera un congresista podría oponerse. Así que lo usé como un paraguas para mis actividades.

—  Richard Bellman, El ojo del huracán: una autobiografía (1984, página 159)

Bellman eligió la palabra dinámica para captar el aspecto variable en el tiempo de los problemas y porque sonaba impresionante. ^[11] La palabra programación se refería al uso del método para encontrar un programa óptimo , en el sentido de un cronograma militar para entrenamiento o logística. Este uso es el mismo que en las frases programación lineal y programación matemática , un sinónimo de optimización matemática . ^[17]

La explicación anterior sobre el origen del término puede ser inexacta: según Russell y Norvig, la historia anterior "no puede ser estrictamente cierta, porque su primer artículo que utilizó el término (Bellman, 1952) apareció antes de que Wilson se convirtiera en Secretario de Defensa en 1953". ^[18] Además, Harold J. Kushner afirmó en un discurso que, "Por otro lado, cuando le hice [a Bellman] la misma pregunta, respondió que estaba tratando de eclipsar la programación lineal de Dantzig agregando dinámica. Quizás ambas motivaciones eran verdaderas". ^[19]

Véase también

• Portal de ciencia de sistemas
• Portal de matemáticas

• La convexidad en la economía  : un tema importante en la economía
• Algoritmo voraz  : secuencia de elecciones óptimas a nivel local
• No convexidad (economía)  – Violaciones de los supuestos de convexidad de la economía elemental
• Programación estocástica  : marco para modelar problemas de optimización que involucran incertidumbre
• Programación dinámica estocástica  : técnica de 1957 para modelar problemas de toma de decisiones en condiciones de incertidumbre
• Aprendizaje por refuerzo  : campo del aprendizaje automático

Referencias

1. Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C. (2001), Introducción a los algoritmos (2ª ed.), MIT Press & McGraw-Hill, ISBN  0-262-03293-7 . págs.344.
2. Kamien, MI ; Schwartz, NL (1991). Optimización dinámica: el cálculo de variaciones y el control óptimo en economía y gestión (segunda edición). Nueva York: Elsevier. pág. 261. ISBN 978-0-444-01609-6.
3. Kirk, Donald E. (1970). Teoría del control óptimo: una introducción. Englewood Cliffs, Nueva Jersey: Prentice-Hall. pp. 94-95. ISBN 978-0-13-638098-6.
4. "M. Memo". J Vocabulary . J Software . Consultado el 28 de octubre de 2011 .
5. Delisi, Charles (julio de 1974), "Fenómenos cooperativos en homopolímeros: una formulación alternativa de la función de partición", Biopolymers , 13 (7): 1511–1512, doi :10.1002/bip.1974.360130719
6. Gurskiĭ, GV; Zasedatelev, AS (septiembre de 1978), "Relaciones precisas para calcular la unión de proteínas reguladoras y otros ligandos reticulares en polinucleótidos bicatenarios", Biofizika , 23 (5): 932–946, PMID  698271
7. Sniedovich, M. (2006), "El algoritmo de Dijkstra revisitado: la conexión de programación dinámica" (PDF) , Journal of Control and Cybernetics , 35 (3): 599–620.Versión en línea del artículo con módulos computacionales interactivos.
8. Denardo, EV (2003), Programación dinámica: modelos y aplicaciones , Mineola, NY: Dover Publications , ISBN 978-0-486-42810-9
9. Sniedovich, M. (2010), Programación dinámica: fundamentos y principios , Taylor & Francis , ISBN 978-0-8247-4099-3
10. Dijkstra, EW (diciembre de 1959). "Una nota sobre dos problemas relacionados con los grafos". Numerische Mathematik . 1 (1): 269–271. doi :10.1007/BF01386390.
11. Eddy, SR (2004). "¿Qué es la programación dinámica?". Nature Biotechnology . 22 (7): 909–910. doi :10.1038/nbt0704-909. PMID  15229554. S2CID  5352062.
12. Moshe Sniedovich (2002), "Juegos OR/MS: 2. El problema de las Torres de Hanoi", INFORMS Transactions on Education , 3 (1): 34–51, doi : 10.1287/ited.3.1.45 .
13. Konhauser JDE, Velleman, D., y Wagon, S. (1996). ¿Hacia dónde se fue la bicicleta? Exposiciones matemáticas de Dolciani – N.º 18. Asociación Matemática de Estados Unidos .
14. Sniedovich, Moshe (2003). "Juegos OR/MS: 4. La alegría de dejar caer huevos en Braunschweig y Hong Kong". INFORMS Transactions on Education . 4 : 48–64. doi : 10.1287/ited.4.1.48 .
15. Dean Connable Wills, Conexiones entre la combinatoria de permutaciones y algoritmos y la geometría
16. Stuart Dreyfus. "Richard Bellman sobre el nacimiento de la programación dinámica".
17. Nocedal, J.; Wright, SJ (2006). Optimización numérica . Springer. pág. 9. ISBN. 9780387303031.
18. Russell, S.; Norvig, P. (2009). Inteligencia artificial: un enfoque moderno (3.ª ed.). Prentice Hall. ISBN 978-0-13-207148-2.
19. Kushner, Harold J. (1 de julio de 2004). "Premio Richard E. Bellman al control del patrimonio". Archivado desde el original el 19 de octubre de 2014.

Lectura adicional

• Adda, Jerome; Cooper, Russell (2003), Economía dinámica, MIT Press, ISBN 9780262012010Una introducción accesible a la programación dinámica en economía. Código MATLAB para el libro Archivado el 9 de octubre de 2020 en Wayback Machine .
• Bellman, Richard (1954), "La teoría de la programación dinámica", Boletín de la Sociedad Matemática Americana , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , MR  0067459Incluye una extensa bibliografía de la literatura en el área, hasta el año 1954.
• Bellman, Richard (1957), Programación dinámica , Princeton University PressEdición de bolsillo de Dover (2003), ISBN 0-486-42809-5 . 
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw–Hill, ISBN 978-0-262-03293-3. Especialmente las páginas 323–69.
• Dreyfus, Stuart E.; Law, Averill M. (1977), El arte y la teoría de la programación dinámica , Academic Press, ISBN 978-0-12-221860-6.
• Giegerich, R.; Meyer, C.; Steffen, P. (2004), "Una disciplina de programación dinámica sobre datos de secuencias" (PDF) , Science of Computer Programming , 51 (3): 215–263, doi : 10.1016/j.scico.2003.12.005.
• Meyn, Sean (2007), Técnicas de control para redes complejas, Cambridge University Press, ISBN 978-0-521-88441-9, archivado desde el original el 19 de junio de 2010.
• Sritharan, SS (1991). "Programación dinámica de las ecuaciones de Navier-Stokes". Systems and Control Letters . 16 (4): 299–307. doi :10.1016/0167-6911(91)90020-f.
• Stokey, Nancy ; Lucas, Robert E .; Prescott, Edward (1989), Métodos recursivos en dinámica económica , Harvard Univ. Press, ISBN 978-0-674-75096-8.

Enlaces externos

• Un tutorial sobre programación dinámica
• Curso del MIT sobre algoritmos: incluye 4 videoconferencias sobre PD, lecciones 15 a 18
• Programación matemática aplicada de Bradley, Hax y Magnanti, capítulo 11
• Más notas de DP
• King, Ian, 2002 (1987), "Una introducción sencilla a la programación dinámica en modelos macroeconómicos". Una introducción a la programación dinámica como una herramienta importante en la teoría económica.
• Programación dinámica: de principiante a avanzado Un artículo de Dumitru en TopCoder.com sobre programación dinámica
• Programación dinámica algebraica: un marco formalizado para la programación dinámica, que incluye un curso de nivel de entrada al PD, Universidad de Bielefeld
• Dreyfus, Stuart, "Richard Bellman sobre el nacimiento de la programación dinámica. Archivado el 13 de octubre de 2020 en Wayback Machine ."
• Tutorial de programación dinámica
• Una introducción sencilla a la programación dinámica y al algoritmo de Viterbi
• Tabled Prolog BProlog, XSB, SWI-Prolog
• IFORS online interactive dynamic programming modules including, shortest path, traveling salesman, knapsack, false coin, egg dropping, bridge and torch, replacement, chained matrix products, and critical path problem.