Programación dinámica - Dynamic programming

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

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

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

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

Visió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 tiempo n . Los valores V _i en tiempos anteriores i  =  n  −1,  n  - 2, ..., 2, 1 se pueden encontrar trabajando hacia atrás, usando una relación recursiva llamada ecuación de Bellman . Para i  = 2, ...,  n , V _{i −1} en cualquier estado y se calcula a partir de V _i maximizando una función simple (generalmente la suma) de la ganancia de una decisión en el tiempo i  - 1 y la función V _i en el nuevo estado del sistema si 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, rastreando los cálculos ya realizados.

Teoría de control

En la 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 produce 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 )\Derecha\}}$

una ecuación diferencial parcial conocida como ecuación de Hamilton-Jacobi-Bellman , en la que y . Uno encuentra que se minimiza 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 resuelve con la condición de contorno . En la práctica, esto generalmente requiere técnicas numéricas para una aproximación discreta a la relación de optimización exacta. ${\ Displaystyle J_ {x} ^ {\ ast} = {\ frac {\ parcial J ^ {\ ast}} {\ parcial \ mathbf {x}}} = \ izquierda [{\ frac {\ parcial J ^ {\ ast}} {\ parciales x_ {1}}} ~~~~ {\ frac {\ parciales J ^ {\ ast}} {\ parciales x_ {2}}} ~~~~ \ puntos ~~~~ {\ frac {\ parcial J ^ {\ ast}} {\ parcial x_ {n}}} \ derecha] ^ {\ mathsf {T}}}$${\ displaystyle J_ {t} ^ {\ ast} = {\ frac {\ parcial J ^ {\ ast}} {\ parcial 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 una siguiente relación de recurrencia análoga a la ecuación de Hamilton-Jacobi-Bellman:

${\ Displaystyle J_ {k} ^ {\ ast} \ left (\ mathbf {x} _ {nk} \ right) = \ min _ {\ mathbf {u} _ {nk}} \ left \ {{\ hat { f}} \ left (\ mathbf {x} _ {nk}, \ mathbf {u} _ {nk} \ right) + J_ {k-1} ^ {\ ast} \ left ({\ hat {\ mathbf { g}}} \ left (\ mathbf {x} _ {nk}, \ mathbf {u} _ {nk} \ right) \ right) \ right \}}$

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

Ejemplo de economía: el problema de 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 compensación entre el consumo contemporáneo y el consumo futuro (a través de la inversión en el capital social que se utiliza en la producción), lo que se conoce 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 asume un capital social inicial . ${\ Displaystyle c}$${\ Displaystyle k}$${\ Displaystyle f}$${\ Displaystyle k_ {0}> 0}$

Sea el consumo en el período t , y suponga que el consumo produce utilidad mientras viva el consumidor. Suponga que el consumidor está impaciente, por lo que descuenta la utilidad futura por un factor b en cada período, donde . Vamos a ser de capital en el periodo t . Suponga que el capital inicial es una cantidad dada , y suponga que el capital y el consumo de este período determinan el capital del período siguiente como , donde A es una constante positiva y . Suponga 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 toma como 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 representamos el valor de tener cualquier cantidad de capital k en cada tiempo t . No hay (por supuesto) ninguna utilidad de 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 uno , 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 anotamos antes, porque involucra solo dos variables de decisión, y . Intuitivamente, en lugar de elegir todo su plan de por vida al nacer, el consumidor puede tomar las cosas paso a paso. En el momento t , se le da su capital actual y solo necesita elegir el consumo y el ahorro actuales . ${\ 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 conoce, 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 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_ {Tj} (k)}$${\ Displaystyle \ ln (c_ {Tj}) + bV_ {T-j + 1} (Ak ^ {a} -c_ {Tj})}$${\ Displaystyle c_ {Tj}}$${\ Displaystyle Ak ^ {a} -c_ {Tj} \ geq 0}$

Trabajando hacia atrás, se puede mostrar que la función de valor en el momento es ${\ Displaystyle t = Tj}$

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

donde cada uno es una constante, y la cantidad óptima para consumir en el momento es ${\ Displaystyle v_ {Tj}}$${\ Displaystyle t = Tj}$

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

que se puede simplificar a

${\ Displaystyle {\ begin {alineado} 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 {alineado}}}$

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

Programación de computadoras

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 ". 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 dado puede obtenerse mediante la combinación de soluciones óptimas a sus subproblemas. Estas subestructuras óptimas suelen describirse mediante recursividad . Por ejemplo, dado un gráfico G = (V, E) , el camino más corto p desde un vértice u hasta un vértice v exhibe una subestructura óptima: tome cualquier vértice intermedio w en este camino más corto p . Si p es realmente el camino más corto, entonces se puede dividir en subtrayectos p ₁ desde u hasta w y p ₂ desde w hasta v, de modo que estos, a su vez, sean de hecho los caminos más cortos entre los vértices correspondientes (por el simple argumento de cortar y pegar descrito en Introducción a los algoritmos ). Por lo tanto, se puede formular fácilmente la solución para encontrar 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 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 (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 para la secuencia de Fibonacci. El hecho de que no sea un árbol indica subproblemas superpuestos.

Esto se puede lograr de dos maneras:

• Enfoque de arriba hacia abajo : esta es la consecuencia directa de la formulación recursiva de cualquier problema. Si la solución a cualquier problema puede formularse de forma recursiva utilizando la solución a sus subproblemas , y si sus subproblemas se superponen, entonces se pueden memorizar o almacenarfácilmentelas soluciones a 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 como en términos de sus subproblemas, podemos intentar reformular el problema de una manera de abajo hacia arriba: intente resolver los subproblemas primero y use sus soluciones para construir y llegar a soluciones a subproblemas mayores. Esto también se hace generalmente en forma de tabla generando iterativamente soluciones para subproblemas cada vez más grandes utilizando las soluciones para pequeños subproblemas. 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, con el fin de 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 incorporada la memorización automática , como Prolog en tabla y J , que admite la memorización con el adverbio M. 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 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 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 EE. UU. Y Georgii Gurskii y Alexander Zasedatelev en la URSS. Recientemente, estos algoritmos se han vuelto muy populares en bioinformática y biología computacional , particularmente en los estudios de posicionamiento de nucleosomas y unión de factores de transcripción .

Ejemplos: algoritmos informáticos

Algoritmo de Dijkstra para el problema de la ruta más corta

Desde el punto de vista de la 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 .

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

Problema 2. Encuentre 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 desde a , el conocimiento de este último implica el conocimiento de la ruta mínima desde a . ${\ 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 de la n º miembro de la secuencia de Fibonacci mejora su rendimiento en gran medida. Aquí hay una implementación ingenua, basada directamente en la definición matemática:

function fib(n)
    if n <= 1 return n
    return fib(n − 1) + fib(n − 2)

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

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

En particular, fib(2)se calculó tres veces desde cero. En ejemplos más grandes , se recalculan muchos más valores 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 del 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)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return 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 los valores.

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

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib  := newFib
    return currentFib

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

El método anterior en realidad lleva tiempo para n grandes porque la suma de dos enteros con bits cada uno lleva tiempo. (El n- ^ésimo número de Fibonacci tiene bits). Además, existe una forma cerrada para la secuencia de Fibonacci, conocida como fórmula de Binet , a partir de la cual se puede calcular el -ésimo término en aproximadamente tiempo, que es más eficiente que la técnica de programación dinámica anterior. . Sin embargo, la recurrencia simple da directamente la forma matricial que conduce a un algoritmo aproximadamente por exponenciación matricial rápida . ${\ Displaystyle \ Omega (n ^ {2})}$${\ Displaystyle \ Omega (n)}$${\ Displaystyle \ Omega (n)}$${\ Displaystyle \ Omega (n)}$${\ Displaystyle n}$${\ Displaystyle O (n (\ log n) ^ {2})}$${\ Displaystyle O (n \ log n)}$

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 , cuatro 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 & 1 & end & 0 {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 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 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 las que tienen filas y columnas equilibradas ( n / 2 ceros y n / 2 unos). Como hay asignaciones posibles y asignaciones razonables, esta estrategia no es práctica excepto tal vez hasta . ${\ Displaystyle 2 ^ {n ^ {2}}}$${\ Displaystyle {\ tbinom {n} {n / 2}} ^ {n}}$${\ Displaystyle n = 6}$

El retroceso para este problema consiste en elegir algún orden de los elementos de la matriz y colocar recursivamente unos o ceros, comprobando 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 son ambos al menos n / 2 . Si bien es más sofisticado que la fuerza bruta, este enfoque visitará todas las soluciones una vez, por lo que no será práctico para n mayor que seis, dado 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 valores para 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 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 revisar cada columna, restando una del elemento apropiado del par para esa columna, dependiendo de si la asignación para la fila superior contenía un cero o uno en esa posición. Si alguno de los resultados es negativo, la asignación no es válida y no contribuye al conjunto de soluciones (paradas de recursión). De lo contrario, tenemos una asignación para la fila superior del tablero k × n y calculamos recursivamente el número de soluciones al tablero restante ( 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 1 × n . El número de soluciones para esta placa 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 las dos primeras tablas 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 la OEIS ) es

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

Los enlaces a la implementación de 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),

Por lo tanto c(1, 3) = 5

Supongamos que hay un verificador que puede comenzar en cualquier casilla del primer rango (es decir, una fila) y desea conocer el camino más corto (la suma de los costos mínimos en cada rango visitado) para llegar al último rango; asumiendo que el corrector solo puede moverse diagonalmente hacia la izquierda hacia adelante, hacia la derecha en diagonal hacia adelante o hacia adelante. Es decir, un corrector en (1,3)puede moverse a (2,2), (2,3)o (2,4).

Este problema presenta una subestructura óptima . Es decir, la solución a todo el problema se basa en soluciones a 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 al rango 1, calculamos el valor de esta función para todos los cuadrados en cada rango sucesivo. Elegir el cuadrado que tiene 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 de ella (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)) + do (A) \,}$

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

${\ Displaystyle q (i, j) = {\ begin {cases} \ infty & j <1 {\ text {o}} 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 {de otro modo.}} \ End {cases}} }$

La primera línea de esta ecuación trata con un tablero modelado como cuadrados indexados 1en el límite más bajo y nen el límite más alto. 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. 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 varios valores:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

Esta función solo calcula el costo de la ruta, no la ruta real. Discutimos el camino real a continuación. Esto, como el ejemplo de los números de Fibonacci, es horriblemente 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 forma ascendente si almacenamos los costos de ruta en una matriz bidimensional en q[i, j]lugar de utilizar 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 siempre que sea necesario.

También necesitamos saber cuál es el camino más corto real. Para hacer esto, usamos 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 llegar al cuadrado inicial. Considere el siguiente código:

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

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

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if q[n, i] < min
            minIndex := i
            min := q[n, i]
    printPath(n, minIndex)

function printPath(y, x)
    print(x)
    print("<-")
    if y = 2
        print(x + p[y, x])
    else
        printPath(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. 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 por:

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

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

Rompecabezas de la torre de Hanoi

Un conjunto de modelos 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, la más pequeña en la parte superior, creando así una forma cónica.

El objetivo del rompecabezas es mover todo el montón a otra barra, obedeciendo las siguientes reglas:

• Solo 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 pueden estar presentes en esa varilla.
• No se puede 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 moverán, h denota la barra de inicio, t denota la barra de destino, no (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 barra h a la barra t.

Para n = 1, el problema es trivial, a saber, 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 ciclismo), entonces la ecuación funcional de programación dinámica es un poco más complicada y  se requieren 3 ⁿ - 1 movimientos.

Rompecabezas de caída de huevos

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

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

• Un huevo que sobrevive 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ía si se dejara caer desde una ventana más alta.
• Si un huevo sobrevive a una caída, sobreviviría a una caída más corta.
• No se descarta que las ventanas del primer piso rompan huevos, ni se descarta que los huevos sobrevivan a las ventanas del piso 36.

Si solo hay un huevo disponible y queremos estar seguros de obtener el resultado correcto, el experimento se puede realizar de una sola manera. Suelta el huevo desde la ventana del primer piso; si sobrevive, déjelo caer desde la ventana del segundo piso. Continúe hacia arriba hasta que se rompa. En el peor de los casos, este método puede requerir 36 excrementos. Suponga que hay 2 huevos disponibles. ¿Cuál es el número más bajo de excrementos de huevos que se garantiza que funcione 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 no se han probado 6 pisos (consecutivos). El estado inicial del proceso es s = ( N , H ) donde N indica el número de huevos de prueba disponibles al comienzo del experimento. El proceso termina cuando no hay más huevos de prueba ( n = 0) o cuando k = 0, lo que ocurra primero. Si la terminación ocurre en el estado s = (0, k ) yk  > 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 se encuentra en el estado s = ( n , k ).

Entonces se puede demostrar que

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

con W ( n , 0) = 0 para 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 con una parametrización diferente

Tenga en cuenta que la solución anterior lleva tiempo con una solución de DP. Esto se puede mejorar en el tiempo mediante la búsqueda binaria en el óptimo en la recurrencia anterior, ya que aumenta en mientras disminuye 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 de 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 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, kx)}$${\ Displaystyle x}$${\ Displaystyle \ max (W (n-1, x-1), W (n, kx))}$${\ Displaystyle x}$${\ Displaystyle x}$${\ Displaystyle O (nk)}$

Sea el número total de pisos en los que los huevos se rompen cuando se caen desde el piso (el ejemplo anterior equivale a tomar ). ${\ Displaystyle k}$${\ Displaystyle k}$${\ Displaystyle k = 37}$

Sea el piso mínimo desde el que se debe dejar caer el huevo para que se rompa. ${\ Displaystyle m}$

Sea el número máximo de valores de que se pueden distinguir mediante intentos 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 piso 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 se puede distinguir utilizando como máximo los intentos y los huevos. ${\ Displaystyle m}$${\ Displaystyle 1}$${\ Displaystyle a}$${\ Displaystyle t-1}$${\ Displaystyle n-1}$

Si el primer huevo no se rompió, es de a y se puede distinguir mediante ensayos 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 la relación de recurrencia se puede resolver de hecho, 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 {ti} {i + 1}}}$${\ Displaystyle i \ geq 0}$

Dado que para todos , podemos buscar binarios para encontrar , dando un algoritmo. ${\ 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 podemos multiplicar solo 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}}$

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

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án más o menos tiempo para calcular, en función de qué matrices particulares se multiplican. Si la matriz A tiene dimensiones m × ny 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 propósitos de ilustración).

Por ejemplo, multipliquemos las matrices A, B y C. Supongamos que sus dimensiones son m × n, n × p y p × s, respectivamente. La matriz A × B × C tendrá un tamaño de m × sy se puede calcular de las dos formas que se muestran 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 mnp + mps.

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

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

En este punto, tenemos varias opciones, una de las cuales es diseñar un algoritmo de programación dinámica que dividirá el problema en problemas superpuestos y calculará la disposición óptima de 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, y tratamos de averiguar qué combinación produce el mínimo m [i, j].

La formula es:

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of 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}}$

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + ${\displaystyle p_{i-1}*p_{k}*p_{j}}$
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update
                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

Hasta ahora, hemos calculado los valores para todos los posibles m [ i , j ] , el número mínimo de cálculos para multiplicar una cadena desde la matriz i a la matriz j , y hemos registrado el correspondiente "punto de división" s [ i , j ] . Por ejemplo, si estamos multiplicando cadena A ₁ × A ₂ × A ₃ × A ₄ , y resulta que m [1, 3] = 100 y s [1, 3] = 2 , lo que significa que la colocación óptima de paréntesis para las matrices 1 a 3 es y para multiplicar esas matrices se requerirá un cálculo escalar de 100. ${\ Displaystyle (A_ {1} \ times A_ {2}) \ times A_ {3}}$

Este algoritmo producirá "tablas" m [,] ys [,] 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 realmente la cadena, es decir, colocar el paréntesis donde (óptimamente) pertenecen. Para ello podríamos utilizar el siguiente algoritmo:

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 
        print ")"

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

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

   function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         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   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 
          print "error, incompatible dimensions."

Historia

El término programación dinámica fue utilizado originalmente en la década de 1940 por Richard Bellman para describir el proceso de resolución de problemas donde se necesita encontrar las mejores decisiones una tras otra. En 1953, refinó esto al significado moderno, refiriéndose específicamente a anidar problemas de decisión más pequeños dentro de decisiones más grandes, y el campo fue reconocido a partir de entonces por el IEEE como un tema de análisis e ingeniería de sistemas . La contribución de Bellman se recuerda en el nombre de la ecuación de Bellman , un resultado central de la programación dinámica que reafirma 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?" La década de 1950 no fue una buena época para la investigación matemática. Tuvimos un caballero muy interesante en Washington llamado Wilson . Era secretario de Defensa y, de hecho, 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 precisamente. Su rostro se ensuciaría, se enrojecería y se volvería violento si la gente usara el término investigación en su presencia. Puede imaginarse cómo se sintió, entonces, sobre el término matemático. La Corporación RAND fue empleada por la Fuerza Aérea, y la Fuerza Aérea tenía a Wilson como su jefe, esencialmente. Por lo tanto, sentí que tenía que hacer algo para proteger a Wilson y la Fuerza Aérea del hecho de que realmente estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre, podría elegir? En primer lugar me interesaba planificar, tomar decisiones, pensar. Pero planificación no es una buena palabra por varias razones. Por tanto, decidí utilizar la palabra "programación". Quería transmitir la idea de que esto era dinámico, esto era de varias etapas, esto variaba en el tiempo. Pensé, matemos dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente preciso, a saber, dinámico, en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y es que es imposible usar la palabra dinámica en un sentido peyorativo. Intente pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por lo tanto, pensé que la programación dinámica era un buen nombre. Era algo a lo que ni siquiera un congresista podría objetar. Así que lo usé como paraguas para mis actividades.

-  Richard Bellman, Eye of the Hurricane: An Autobiography (1984, página 159)

Bellman eligió la palabra dinámica para captar el aspecto variable de los problemas con el tiempo y porque sonaba impresionante. La palabra programación se refería al uso del método para encontrar un programa óptimo , en el sentido de un horario 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 .

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

Algoritmos que utilizan programación dinámica

• Soluciones recurrentes a modelos de celosía para la unión proteína-ADN
• La inducción hacia atrás como método de solución para problemas de optimización dinámica de tiempo discreto de horizonte finito
• Método de coeficientes indeterminados se puede utilizar para resolver el ecuación de Bellman en el horizonte infinito, tiempo discreto, descontado , invariantes en el tiempo los problemas de optimización dinámica
• Muchos algoritmos de cadena , incluida la subsecuencia común más larga , la subsecuencia creciente más larga , la subcadena común más larga , la distancia de Levenshtein (distancia de edición)
• Muchos problemas algorítmicos en gráficos se pueden resolver de manera eficiente para gráficos de ancho de árbol limitado o ancho de camarilla limitado mediante el uso de programación dinámica en una descomposición de árbol del gráfico.
• El algoritmo Cocke-Younger-Kasami (CYK) que determina si una determinada cadena puede generarse mediante una gramática libre de contexto determinada y cómo
• Algoritmo de ajuste de palabras de Knuth que minimiza la irregularidad al ajustar el texto de palabras
• El uso de tablas de transposición y tablas de refutación en el ajedrez por computadora
• El algoritmo de Viterbi (utilizado para modelos ocultos de Markov y, en particular, en parte del etiquetado de voz )
• El algoritmo de Earley (un tipo de analizador de gráficos )
• El algoritmo de Needleman-Wunsch y otros algoritmos usados en la bioinformática , incluyendo la alineación de secuencias , alineación estructural , la estructura del ARN de predicción
• Algoritmo de ruta más corta de todos los pares de Floyd
• Optimización del orden para la multiplicación de matrices en cadena
• Tiempo pseudo-polinomial algoritmos para la suma de subconjuntos , de mochila y la partición problemas
• El algoritmo dinámico de deformación del tiempo para calcular la distancia global entre dos series de tiempo
• El algoritmo de Selinger (también conocido como System R ) para la optimización de consultas de bases de datos relacionales
• Algoritmo de De Boor para evaluar curvas B-spline
• Método de Duckworth-Lewis para resolver el problema cuando se interrumpen los juegos de cricket
• El método de iteración de valor para resolver los procesos de decisión de Markov
• Algunos bordes de la imagen gráfica siguiendo métodos de selección, como la herramienta de selección "imán" en Photoshop
• Algunos métodos para resolver problemas de programación de intervalos
• Algunos métodos para resolver el problema del viajante , ya sea exactamente (en tiempo exponencial ) o aproximadamente (por ejemplo, a través del recorrido bitónico )
• Método recursivo de mínimos cuadrados
• Beat tracking en la recuperación de información musical
• Estrategia de entrenamiento adaptativo-crítico para redes neuronales artificiales
• Algoritmos estéreo para resolver el problema de correspondencia utilizado en la visión estéreo
• Tallado de costuras (cambio de tamaño de imagen en función del contenido)
• El algoritmo de Bellman-Ford para encontrar la distancia más corta en un gráfico
• Algunos métodos de solución aproximada para el problema de búsqueda lineal
• Algoritmo de Kadane para el problema de subarreglo máximo
• Optimización de planes de expansión de generación eléctrica en el paquete Wein Automatic System Planning (WASP)

Ver también

• Convexidad en economía
• Algoritmo codicioso
• No convexidad (economía)
• Programación estocástica
• Programación dinámica estocástica
• Aprendizaje reforzado

Referencias

Otras lecturas

• Adda, Jerome; Cooper, Russell (2003), Economía dinámica , MIT Press. Una introducción accesible a la programación dinámica en economía. Código MATLAB para el libro .
• Bellman, Richard (1954), "La teoría de la programación dinámica", Boletín de la American Mathematical Society , 60 (6): 503–516, doi : 10.1090 / S0002-9904-1954-09848-8 , MR  0067459. Incluye una extensa bibliografía de la literatura de la zona, 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 y McGraw – Hill, ISBN 978-0-262-03293-3. Especialmente págs. 323–69.
• Dreyfus, Stuart E .; Derecho, 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), "A Discipline of Dynamic Programming over Sequence Data" (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". 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 una conferencia en video sobre DP junto con notas de lectura, consulte la lección 15.
• Programación matemática aplicada por Bradley, Hax y Magnanti, Capítulo 11
• Más notas de DP
• King, Ian, 2002 (1987), " Una introducción simple 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 TopCoder.com de Dumitru 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 " .
• Tutorial de programación dinámica
• Una suave introducción a la programación dinámica y al algoritmo de Viterbi
• Prolog en tabla BProlog , XSB , SWI-Prolog
• Módulos de programación dinámica interactiva en línea de IFORS que incluyen, ruta más corta, vendedor ambulante, mochila, moneda falsa, caída de huevos, puente y antorcha, reemplazo, productos de matriz encadenada y problema de ruta crítica.