Programación dinámica

Método de optimización de problemas

Figura 1. Encontrar el camino más corto en un gráfico utilizando 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 en general desde el principio hasta la meta.

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 dividiéndolo en subproblemas más simples de manera recursiva . Si bien algunos problemas de decisión no pueden descomponerse de esta manera, las decisiones que abarcan varios momentos en el tiempo a menudo se descomponen de forma 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 a los subproblemas, entonces se dice que tiene una subestructura óptima .

Si los subproblemas pueden anidarse recursivamente dentro de problemas más grandes, de modo que sean aplicables los métodos de programación dinámica, entonces existe una relación entre el valor del problema más grande y los valores de los subproblemas. ^[1] En la literatura sobre 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 momentos i de 1 a n .

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

Los valores V _i en momentos anteriores i  =  n  −1,  n  − 2, ..., 2, 1 se pueden encontrar trabajando hacia atrás, utilizando una relación recursiva llamada ecuación de Bellman .

Para i  = 2, ...,  n , Vi ₋₁ en cualquier estado y se calcula a partir de _Vi maximizando una función simple (generalmente la suma) de la ganancia de una decisión en el momento _i −  1 y la _función Vi en el nuevo estado del sistema si se toma esta decisión.

Como Vi ya _se ha calculado para los estados necesarios, la operación anterior produce _{Vi −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 teoría del 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 produzca una trayectoria óptima y una función de costo total . Este último 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 minimizar en términos de , y la función desconocida y luego sustituir 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 frontera . ^[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 -ésima etapa de intervalos de tiempo discretos igualmente espaciados, y donde y denota aproximaciones discretas a y . Esta ecuación funcional se conoce como ecuación de Bellman , que puede resolverse 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 generalmente es 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 con niveles de utilidad . En términos generales, el planificador se enfrenta al equilibrio entre el consumo contemporáneo y el consumo futuro (a través de la inversión en capital social que se utiliza en la producción), conocido 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 viene 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 capital social inicial . ${\displaystyle c}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle k_{0}>0}$

Sea el consumo en el período t y supongamos que el consumo genera utilidad mientras viva el consumidor. Supongamos que el consumidor es impaciente, de modo que descuenta la utilidad futura en un factor b en cada período, donde . Sea el capital en el periodo t . Suponga que el capital inicial es una cantidad determinada y suponga que el capital y el consumo de este período determinan el capital del siguiente período como , donde A es una constante positiva y . Supongamos que el capital no puede ser negativo. Entonces el problema de decisión del consumidor se puede escribir 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 da por sentado). ${\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 hacerlo, definimos una secuencia de funciones de valor , para las cuales representan el valor de tener cualquier cantidad de capital k en cada momento t . (Por supuesto) no hay utilidad en 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 mediante 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 su plan de por vida al nacer, el consumidor puede ir paso a paso. En el momento t , se da su capital actual y sólo 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 realmente este problema, trabajamos al revés. Para simplificar, el nivel actual de capital se denota como k . ya se sabe, así que usando 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 cuál es el máximo de , dónde está 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 hacia atrás, se puede demostrar que la función de valor en el tiempo 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 un momento dado 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 se puede simplificar 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 lo óptimo es 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 debe tener un problema para que la programación dinámica sea aplicable: subestructura óptima y subproblemas superpuestos . Si un problema puede resolverse combinando soluciones óptimas a subproblemas que no se superponen , la estrategia se denomina " divide y vencerás ". ^[1] Esta es la razón por la que la clasificación por combinación y la clasificació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 determinado 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 a un vértice v exhibe una subestructura óptima: tome cualquier vértice intermedio w en este camino más corto p . Si p es realmente el camino más corto, entonces se puede dividir en sub-caminos p ₁ de u a w y p ₂ de w a v de modo que estos, a su vez, sean de hecho los caminos más cortos entre los vértices correspondientes (por la 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 caminos más cortos de manera recursiva, que es lo que hacen el algoritmo de Bellman-Ford o el algoritmo de Floyd-Warshall .

La superposición de subproblemas significa que el espacio de los 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 subproblemas. Por ejemplo, considere la formulación recursiva para generar la serie de Fibonacci: F _i = F _{i −1} + F _{i −2} , con el 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 (sólo 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 sólo una vez.

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

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

• Enfoque de arriba hacia abajo : Ésta es la consecuencia directa de la formulación recursiva de cualquier problema. Si la solución a cualquier problema se puede formular de forma recursiva utilizando la solución de sus subproblemas, y si sus subproblemas se superponen, entonces se pueden 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 ascendente : una vez que formulamos la solución a un problema de forma recursiva, es decir, en términos de sus subproblemas, podemos intentar reformular el problema de abajo hacia arriba: intentar resolver los subproblemas primero y utilizar sus soluciones para construir. y llegar a soluciones para subproblemas mayores. Esto también se suele hacer en forma tabular generando de forma iterativa soluciones para subproblemas cada vez más grandes utilizando las soluciones para subproblemas más 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 la 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 idiomas tienen memorización automática incorporada, como tabled Prolog y J , que admite la memorización con el adverbio M. ^[4] 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 en 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 alineación de secuencias , plegamiento de proteínas , predicción de la estructura del ARN y unión proteína-ADN. Los primeros algoritmos de programación dinámica para la unión proteína-ADN fueron desarrollados de forma independiente en la década de 1970 por Charles DeLisi en EE. UU. ^[5] y Georgii Gurskii y Alexander Zasedatelev en la URSS. ^[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 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 programación dinámica para el problema del camino más corto mediante el método Reaching . ^{[7] [8] [9]}

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

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

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

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

secuencia Fibonacci

El uso de programación dinámica en el cálculo del enésimo miembro de la secuencia 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 <= 1 devolver n devolver fib(n − 1) + fib(n − 2)

Observe que si llamamos, digamos fib(5), generamos un árbol de llamadas que llama a la función con 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 amplios, se recalculan muchos más valores de fibo 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 fibque ya ha sido calculado a su resultado, y modificamos nuestra función para usarlo y actualizarlo. La función resultante requiere solo tiempo O ( n ) en lugar de tiempo exponencial (pero requiere espacio O ( n )):

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) devolver m[n]

Esta técnica de guardar valores que ya han sido calculados se llama memorizació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 ascendente , primero calculamos los valores más pequeños de fiby luego construimos valores más grandes a partir de ellos. Este método también utiliza el tiempo O( n ) ya que contiene un bucle que se repite n − 1 veces, pero solo requiere un espacio constante (O(1)), en contraste con el enfoque de arriba hacia abajo que requiere un espacio O( n ) para almacenar el mapa.

función fib(n) si n = 0 devuelve 0 en caso contrario  var anteriorFib := 0, actualFib := 1 repetir n − 1 veces  // el bucle se omite si n = 1  var nuevaFib := anteriorFib + actualFib Fib anterior: = Fib actual Fibactual: = nuevoFib retorno actualFib

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

Un tipo de matriz equilibrada 0-1

Considere 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. Preguntamos cuántas asignaciones diferentes hay para un determinado . Por ejemplo, cuando n = 4 , cinco posibles soluciones son ${\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 tengan 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}$

Retroceder para este problema consiste en elegir algún 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 al menos n / 2 . Si bien es más sofisticado que la fuerza bruta, este método 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. Imagine retroceder 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 tableros k × n , 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 no se han colocado 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 posibles asignaciones 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 resto del tablero ( k − 1) × n , sumando el número 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 de 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 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 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 el OEIS ) es

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

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

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 comenzar en cualquier casilla del primer rango (es decir, fila) y usted desea saber el camino más corto (la suma de los costos mínimos en cada rango visitado) para llegar al último rango; suponiendo que la ficha pueda moverse solo en diagonal hacia la izquierda, hacia la derecha o hacia adelante. Es decir, una ficha (1,3)puede moverse hacia (2,2), (2,3)o (2,4).

Este problema exhibe una subestructura óptima . Es decir, la solución al problema completo depende de las soluciones a los subproblemas. Definamos una función q(i, j)como

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

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

La función q(i, j)es igual al costo mínimo para llegar a cualquiera de los tres cuadrados debajo (ya que esos son los únicos cuadrados que pueden alcanzarlo) 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 trata de un tablero modelado como cuadrados indexados 1en el límite inferior y nen 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 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 si no i = 1 devuelve c(i, j) de lo contrario  devuelve  min ( minCost(i-1, j-1), minCost(i-1, j), costomínimo(i-1, j+1) ) + c(i, j)

Esta función solo calcula el costo de la ruta, no la ruta real. Discutimos el camino real a continuación. Esto, como el ejemplo de los números de Fibonacci, es terriblemente lento porque también presenta 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 abajo hacia arriba 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 de antemano 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 el camino a cualquier cuadrado s. El predecesor de sse modela como una compensación relativa 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, hasta llegar al cuadrado inicial. Considere el siguiente pseudocódigo:

función calcularShortestPathArrays() 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 simplemente cuestión de encontrar el mínimo e imprimirlo.

función calcularRutaCortaCorta() calcularShortestPathArrays() índice mínimo := 1 mín := q[n, 1] para i de 2 a n si q[n, i] < min índicemínimo := i mín := q[n,i] printPath(n, minIndex)

función printPath(y, x) print (x) print ("<-") si y = 2 print (x + p[y, x]) else imprimirRuta(y-1, x + p[y, x])

Alineación de secuencia

En genética , la alineación 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 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. 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 alineamientos óptimos de las colas de A y B.

Los alineamientos parciales se pueden tabular en una matriz, donde la celda (i,j) contiene el costo del alineamiento óptimo 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 el óptimo.

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

Rompecabezas de la Torre de Hanoi

Un modelo 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 o rompecabezas matemático . Consta de tres varillas y varios 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 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 puedan estar ya presentes en esa varilla.
• No se podrá colocar ningún disco encima 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, no(h,t)); S(1,h,t); S(n-1,no(h,t),t)

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

S(n, h, t):= solución a un problema que consta de n discos que se van a 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 barra h a la barra 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 ciclos), entonces la ecuación funcional de programación dinámica es un poco más complicada y  se requieren 3 ^{n − 1 movimientos. [12]}

Rompecabezas de dejar caer huevos

La siguiente es una descripción del ejemplo de este famoso rompecabezas que involucra N=2 huevos y un edificio con H=36 pisos: ^[13]

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

• Un huevo que sobreviva a una caída se puede volver a utilizar.
• Un huevo roto debe desecharse.
• El efecto de una caída es el mismo para todos los huevos.
• Si un huevo se rompe al caer, se romperá si se cae desde una ventana más alta.
• Si un huevo sobrevive a una caída, sobrevivirá a una caída más corta.
• No se descarta que las ventanas del primer piso rompan los huevos, ni tampoco 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 realizar de una manera. Deja caer el huevo desde la ventana del primer piso; Si sobrevive, déjelo caer desde la ventana del segundo piso. Continuar hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 36 excrementos. Supongamos que hay 2 huevos disponibles. ¿Cuál es el número más bajo de excrementos de huevo 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) aún 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 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 necesarios para identificar el valor del piso crítico en el peor de los casos dado que el proceso está en el estado s = ( n , k ).

Entonces se puede demostrar que ^[14]

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 todo n  > 0 y W (1, k ) = k para todo  k . Es fácil resolver esta ecuación de forma iterativa aumentando sistemáticamente los valores de n y  k .

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

Tenga en cuenta que la solución anterior lleva tiempo con una solución DP. Esto se puede mejorar en el tiempo mediante una búsqueda binaria del óptimo en la recurrencia anterior, ya que aumenta en mientras que disminuye en , por lo que 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, mejorándolo en el tiempo. Sin embargo, existe una solución aún más rápida que pasa por 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 en los que los huevos se rompen al caer desde el piso 1 (el ejemplo anterior equivale 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 distinguen usando pruebas y huevos. ${\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 suelo desde el que se deja caer el primer huevo en la estrategia óptima. ${\displaystyle a}$

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

Si el primer huevo no se rompió, se distingue mediante pruebas 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 equivale a encontrar el mínimo tal que . ${\displaystyle x}$ ${\displaystyle f(x,n)\geq k}$

Para hacerlo, 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 manejamos por separado el caso de , el algoritmo tomaría tiempo. ${\displaystyle n=1}$ ${\displaystyle O(n{\sqrt {k}})}$

Pero, de hecho, la relación de recurrencia se puede resolver, dando , que se puede calcular en el tiempo utilizando la identidad para todos . ${\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 buscar binariamente para encontrar , dando 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 cadenas de matrices 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 de extrañar encontrar matrices de grandes dimensiones, por ejemplo 100×100. Por tanto, nuestra tarea es multiplicar matrices . La multiplicación de matrices no es conmutativa, sino asociativa; y sólo podemos multiplicar dos matrices a la vez. Entonces, podemos multiplicar esta cadena de matrices de muchas formas diferentes, por ejemplo: ${\displaystyle A_{1},A_{2},....A_{n}}$

((Un ₁ × Un ₂ ) × Un ₃ ) × ... Un _norte

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

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

etcétera. Existen numerosas formas de multiplicar esta cadena de matrices. Todos producirán el mismo resultado final, sin embargo, tomará más o menos tiempo calcularlos, en función de qué matrices particulares se multiplican. 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 simplista de multiplicación de matrices para fines 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 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á multiplicaciones escalares nps + mns.
2. (A×B)×C Este orden de multiplicación de matrices requerirá cálculos escalares de mnp + mps.

Supongamos que m = 10, n = 100, p = 10 y s = 1000. Entonces, la primera forma de multiplicar la cadena requerirá 1.000.000 + 1.000.000 de cálculos. La segunda forma requerirá sólo 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 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 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 m[i,j] al número mínimo de multiplicaciones escalares necesarias para multiplicar una cadena de matrices desde la matriz i hasta 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 descubrir 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 OptimalMatrixChainParenthesis(cadena) n = longitud (cadena) para yo = 1, norte 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 los paréntesis es mejor que el que teníamos m[i, j] = q // Actualizar s[i, j] = k // Registra en qué k dividir, es decir, dónde colocar el paréntesis

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

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 demás imprimir "(" 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 sólo una forma fácil de usar de ver cómo se ve el resultado.

Para multiplicar realmente las matrices usando 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 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 // continúa 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 ) devuelve MatrixMultiply ( LeftSide , RightSide ) de lo contrario si i = j devuelve Ai // matriz en la posición i else imprimir "error, i <= j debe mantenerse"                                        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 es necesario 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, ^{[16] y posteriormente el} IEEE reconoció el campo como un tema de ingeniería y análisis 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 varias etapas. Una pregunta interesante es: "¿De dónde viene el nombre programación dinámica?" Los años cincuenta no fueron buenos años 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 hacia la palabra "investigación". No estoy usando el término a la ligera; Lo estoy usando precisamente. Su rostro se iluminaría, se pondría rojo y se pondría violento si la gente usara el término investigación en su presencia. Puedes imaginar cómo se sentía, entonces, acerca del término matemático. La RAND Corporation 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 a la Fuerza Aérea del hecho de que yo realmente estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre podría elegir? En primer lugar me interesaba planificar, tomar decisiones, pensar. Pero planificar no es una buena palabra por varias razones. Por eso decidí utilizar la palabra "programación". Quería transmitir la idea de que esto era dinámico, de múltiples etapas, que variaba en el tiempo. Pensé, matemos dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente preciso, es decir, dinámica, 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ámica en sentido peyorativo. Intenta pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por tanto, pensé que la programación dinámica era un buen nombre. Era algo a lo que ni siquiera un congresista podría oponerse. Entonces lo usé como paraguas para mis actividades.

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

Bellman eligió la palabra dinámica para captar el aspecto de los problemas que varía en el tiempo 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 el de las frases programación lineal y programación matemática , sinónimo de optimización matemática . ^[17]

La explicación anterior del 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 usando el término (Bellman, 1952) apareció antes de que Wilson se convirtiera en Secretario de Defensa en 1953. " ^[18] Además, Harold J. Kushner Archivado el 1 de marzo de 2017 en Wayback Machine declaró en un discurso que, "Por otro lado, cuando le hice [a Bellman] la misma pregunta, respondió que estaba tratando de eclipsar la obra de Dantzig. programación lineal agregando dinámica. Quizás ambas motivaciones eran ciertas".

Ver también

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

• Convexidad en economía  : tema importante en economía
• Algoritmo codicioso  : secuencia de elecciones localmente óptimas
• 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, Michigan ; Schwartz, NL (1991). Optimización dinámica: el cálculo de variaciones y el control óptimo en economía y gestión (Segunda ed.). Nueva York: Elsevier. pag. 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. págs. 94–95. ISBN 978-0-13-638098-6.
4. "M. Nota". J Vocabulario . Software J. Consultado el 28 de octubre de 2011 .
5. DeLisi, Biopolymers, 1974, volumen 13, número 7, páginas 1511-1512, julio de 1974
6. Gurskiĭ GV, Zasedatelev AS, Biofizika, septiembre-octubre de 1978; 23 (5): 932-46
7. Sniedovich, M. (2006), "Revisión del algoritmo de Dijkstra: 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, Nueva York: 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 en relación con los gráficos". Matemática numérica . 1 (1): 269–271. doi :10.1007/BF01386390.
11. Eddy, SR (2004). "¿Qué es la programación dinámica?". Biotecnología de la Naturaleza . 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", INFORMA Transacciones sobre educación , 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 Dolciani - No 18. Asociación Matemática de América .
14. Sniedovich, Moshe (2003). "Juegos OR/MS: 4. La alegría de dejar caer huevos en Braunschweig y Hong Kong". INFORMA Transacciones en Materia de Educación . 4 : 48–64. doi : 10.1287/ited.4.1.48 .
15. Dean Connable Wills, Conexiones entre combinatoria de permutaciones y algoritmos y geometría
16. Estuardo Dreyfus. "Richard Bellman sobre el nacimiento de la programación dinámica".
17. Nocedal, J.; Wright, SJ (2006). Optimización numérica . Saltador. pag. 9.ISBN​ 9780387303031.
18. Russell, S.; Norvig, P. (2009). Inteligencia artificial: un enfoque moderno (3ª ed.). Prentice Hall. ISBN 978-0-13-207148-2.

Otras lecturas

• Adda, Jerónimo; Cooper, Russell (2003), Economía dinámica, MIT Press, ISBN 9780262012010. Una 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 Estadounidense , 60 (6): 503–516, doi : 10.1090/S0002-9904-1954-09848-8 , SEÑOR  0067459. Incluye una extensa bibliografía de la literatura del área, hasta el año 1954.
• Bellman, Richard (1957), Programación dinámica , Princeton University Press. Edició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 & McGraw–Hill, ISBN 978-0-262-03293-3. Especialmente págs. 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 secuencia" (PDF) , Ciencia de la programación informática , 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". Sistemas y Cartas de Control . 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 , Universidad de Harvard. Prensa, ISBN 978-0-674-75096-8.

enlaces externos

• Un tutorial sobre programación dinámica
• Curso del MIT sobre algoritmos: incluye 4 videoconferencias sobre el PD, conferencias 15 a 18
• Programación matemática aplicada de Bradley, Hax y Magnanti, Capítulo 11
• Más notas de PD
• 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 básico para el 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 suave introducción a la programación dinámica y el algoritmo de Viterbi
• Prólogo presentado BProlog, XSB, SWI-Prolog
• Módulos de programación dinámica interactiva en línea de IFORS que incluyen el camino más corto, el vendedor ambulante, la mochila, la moneda falsa, la caída de huevos, el puente y la antorcha, el reemplazo, los productos de matriz encadenados y el problema de ruta crítica.