Programación dinámica

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. ^{[ 2 ]}

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

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

Los valores V _i en tiempos 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 .        

For i = 2, ..., n, V_i−1 at any state y is calculated from V_i by maximizing a simple function (usually the sum) of the gain from a decision at time i − 1 and the function V_i at the new state of the system if this decision is made.

Since V_i has already been calculated for the needed states, the above operation yields V_i−1 for those states.

Finally, V₁ at the initial state of the system is the value of the optimal solution. The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed.

In control theory, a typical problem is to find an admissible control ${\displaystyle \mathbf {u} ^{\ast }}$ which causes the system ${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$ to follow an admissible trajectory ${\displaystyle \mathbf {x} ^{\ast }}$ on a continuous time interval ${\displaystyle t_{0}\leq t\leq t_{1}}$ that minimizes a cost function

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

The solution to this problem is an optimal control law or policy ${\displaystyle \mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)}$, which produces an optimal trajectory ${\displaystyle \mathbf {x} ^{\ast }}$ and a cost-to-go function${\displaystyle J^{\ast }}$. The latter obeys the fundamental equation of dynamic programming:

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

a partial differential equation known as the Hamilton–Jacobi–Bellman equation, in which ${\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}}}$ and ${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$. One finds that minimizing ${\displaystyle \mathbf {u} }$ in terms of ${\displaystyle t}$, ${\displaystyle \mathbf {x} }$, and the unknown function ${\displaystyle J_{x}^{\ast }}$ and then substitutes the result into the Hamilton–Jacobi–Bellman equation to get the partial differential equation to be solved with boundary condition ${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$.^[3] In practice, this generally requires numerical techniques for some discrete approximation to the exact optimization relationship.

Alternatively, the continuous process can be approximated by a discrete system, which leads to a following recurrence relation analog to the Hamilton–Jacobi–Bellman equation:

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

at the ${\displaystyle k}$-th stage of ${\displaystyle n}$ equally spaced discrete time intervals, and where ${\displaystyle {\hat {f}}}$ and ${\displaystyle {\hat {\mathbf {g} }}}$ denote discrete approximations to ${\displaystyle f}$ and ${\displaystyle \mathbf {g} }$. This functional equation is known as the Bellman equation, which can be solved for an exact solution of the discrete approximation of the optimization equation.^[4]

Para que un problema sea aplicable a la programación dinámica, debe poseer dos atributos clave: una subestructura óptima y subproblemas superpuestos . Si un problema se puede resolver combinando soluciones óptimas de subproblemas que no se superponen , la estrategia se denomina « divide y vencerás ». ^{[ 1 ]} Por esta razón, la ordenación por fusión y la ordenación rápida no se clasifican como problemas de programación dinámica.

Una subestructura óptima significa que la solución a un problema de optimización dado se puede obtener mediante la combinación de soluciones óptimas a sus subproblemas. Estas subestructuras óptimas se suelen describir mediante recursión . Por ejemplo, dado un grafo G=(V,E) , el camino más corto p desde un vértice u a un vértice v presenta una subestructura óptima: tomemos 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 subcaminos p₁ de u a _w y p₂ de w a v, _de modo que estos, a su vez, sean efectivamente los caminos más cortos entre los vértices correspondientes (mediante el sencillo argumento de cortar y pegar descrito en la 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 implica que el espacio de subproblemas debe ser pequeño; es decir, cualquier algoritmo recursivo que resuelva el problema debería resolver los mismos subproblemas repetidamente, en lugar de generar nuevos subproblemas. Por ejemplo, consideremos la formulación recursiva para generar la secuencia 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 bien, F ₄₁ se resuelve en los subárboles recursivos tanto de F ₄₃ como de F ₄₂ . Aunque el número total de subproblemas es pequeño (solo 43), 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.         

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

• Enfoque descendente : Este es el resultado directo de la formulación recursiva de cualquier problema. Si la solución a un problema puede formularse recursivamente utilizando la solución a sus subproblemas, y si estos subproblemas se superponen, entonces se pueden memorizar o almacenar fácilmente las soluciones de los subproblemas en una tabla (generalmente un array o una tabla hash ). Cada vez que intentamos resolver un nuevo subproblema, primero consultamos 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 recursivamente en términos de sus subproblemas, podemos intentar reformular el problema de forma ascendente: intentar resolver primero los subproblemas y usar sus soluciones para construir y llegar a soluciones para subproblemas más grandes. Esto también se suele hacer en forma tabular generando iterativamente soluciones para subproblemas cada vez mayores utilizando las soluciones de subproblemas pequeños. Por ejemplo, si ya conocemos los valores de F ₄₁ y F ₄₀ , podemos calcular directamente el valor de F ₄₂ .

Algunos lenguajes de programación pueden memorizar automáticamente el resultado de una llamada a función con un conjunto particular de argumentos, para acelerar la evaluación por nombre (este mecanismo se conoce como llamada por necesidad ). Algunos lenguajes lo hacen posible de forma portable (por ejemplo, Scheme , Common Lisp , Perl o D ). Algunos lenguajes tienen memorización automática integrada, como Prolog tabulado y J , que admite memorización con el adverbio M. ^{[ 6 ]} 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 fácilmente accesible dentro de lenguajes basados ​​en reescritura de términos como Wolfram Language .

La programación dinámica se utiliza ampliamente en bioinformática para tareas como el alineamiento 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 Estados Unidos ^{[ 7 ]} y por Georgii Gurskii y Alexander Zasedatelev en la Unión Soviética ^{[ 8 ]} . 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 .

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 de alcance . ^{[ 9 ] [ 10 ] [ 11 ]}

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

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

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

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

El uso de programación dinámica en el cálculo del enésimo término de la secuencia de Fibonacci mejora considerablemente su rendimiento. He aquí una implementación sencilla, basada directamente en la definición matemática:

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

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

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

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

Ahora bien, supongamos que tenemos un objeto de mapa simple, m , que asigna a cada valor fibque ya se ha calculado 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) devolver m[n]

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

función fib(n) si n = 0 devuelve 0 sino var previousFib := 0, currentFib := 1 repetir n − 1 veces // el bucle se omite si n = 1 var newFib := previousFib + currentFib Fibrosis anterior := Fibrosis actual Fibrilación actual := Fibrilación nueva devolver la fibrilación actual

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

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

${\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}}.}$

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

La fuerza bruta consiste en comprobar todas las asignaciones de ceros y unos y contar aquellas que tienen filas y columnas equilibradas ( n /2 ceros y n /2 unos). Como hay${\displaystyle 2^{n^{2}}}$posibles asignaciones y${\displaystyle {\tbinom {n}{n/2}}^{n}}$asignaciones sensatas, esta estrategia no es práctica para valores arbitrariamente grandes de${\displaystyle n}$.

El método de retroceso para este problema consiste en elegir un orden determinado 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 se han asignado más el número de unos o ceros sean ambos al menos n / 2. Si bien es más sofisticado que la fuerza bruta, este enfoque visitará cada solución una vez, lo que lo hace poco práctico para n mayor que seis, ya que el número de soluciones ya es116 963 796 250 para n  =  8, como veremos.

La programación dinámica permite contar el número de soluciones sin visitarlas todas. Imaginemos 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 de k × n , donde 1 ≤ k ≤ n , cuyas k filas contienen${\displaystyle n/2}$ceros y${\displaystyle n/2}$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${\displaystyle f((n/2,n/2),(n/2,n/2),\ldots (n/2,n/2))}$( n argumentos o un vector de n elementos). El proceso de creación de subproblemas implica iterar sobre cada uno de ellos. ${\displaystyle {\tbinom {n}{n/2}}}$posibles asignaciones para la fila superior del tablero, y recorriendo cada columna, restando uno al 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 es inválida y no contribuye al conjunto de soluciones (la recursión se detiene). De lo contrario, tenemos una asignación para la fila superior del tablero k × n y calculamos recursivamente el número de soluciones para el tablero restante ( k − 1) × n , sumando los números de soluciones para cada asignación admisible de la fila superior y devolviendo la suma, que se está memorizando. El caso base es el subproblema trivial, que ocurre para un tablero 1 × n . El número de soluciones para este tablero es cero o uno, dependiendo de si el vector es una permutación de n / 2 (0, 1) y n / 2 (1, 0) pares o no.

Por ejemplo, en los dos primeros tableros mostrados arriba, las secuencias de vectores serían:

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

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

1, 2, 90,297 200 ,116 963 796 250 ,6 736 218 287 430 460 752 , ...

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

Consideremos un tablero de ajedrez con n × n casillas y una función de costo c(i, j)que devuelve un costo asociado a cada casilla (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 de la primera fila y queremos saber el camino más corto (la suma de los costos mínimos en cada fila visitada) para llegar a la última fila; suponiendo que la ficha solo puede moverse en diagonal hacia la izquierda, en diagonal hacia la derecha o en línea recta. Es decir, una ficha en (1,3)puede moverse a (2,2), (2,3)o (2,4).

Este problema presenta una subestructura óptima . Es decir, la solución 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 llegar al 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. Eligiendo el cuadrado que tiene el valor mínimo en cada rango obtenemos el camino más corto entre el rango ny el rango 1.

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

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

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

${\displaystyle q(i,j)={\begin{cases}\infty &j<1{\text{ or }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\text{otherwise.}}\end{cases}}}$

La primera línea de esta ecuación trata sobre un tablero modelado como casillas indexadas en 1el 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 recursión, es la parte importante. Representa los A,B,C,Dtérminos del ejemplo. A partir de esta definición, podemos derivar un código recursivo directo para . En el siguiente pseudocódigo, es el tamaño del tablero, es la función de costo y devuelve el mínimo de varios valores:q(i, j)nc(i, j)min()

función minCost(i, j) si j < 1 o j > n devuelve infinito sino si i = 1 devuelve c(i, j) sino devuelve min ( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

Esta función solo calcula el costo de la ruta, no la ruta en sí. Analizaremos la ruta en sí más adelante. Esto, al igual que el ejemplo de los números de Fibonacci, es terriblemente lento porque también presenta el atributo de subproblemas superpuestos . Es decir, recalcula 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 consultan cuando sea necesario.

También necesitamos saber cuál es el camino más corto real. Para ello, utilizamos otro arreglo p[i, j]; un arreglo de predecesores . Este arreglo registra el camino a cualquier casilla s. El predecesor de sse modela como un desplazamiento relativo al índice (en q[i, j]) del costo de camino precalculado de s. Para reconstruir el camino completo, buscamos el predecesor de s, luego el predecesor de esa casilla, luego el predecesor de esa casilla, y así sucesivamente de forma recursiva, hasta llegar a la casilla de inicio. Considere el siguiente pseudocódigo:

función computeShortestPathArrays() para x desde 1 hasta 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 := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1]) q[y, x] := m + c(y, x) si m = q[y-1, x-1] p[y, x] := -1 de lo contrario, si m = q[y-1, x] p[y, x] := 0 de lo contrario p[y, x] := 1

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

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

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

En genética , el alineamiento de secuencias es una aplicación importante donde la programación dinámica es esencial. ^{[ 13 ]} Típicamente, el problema consiste en transformar una secuencia en otra usando operaciones de edición que reemplazan, insertan o eliminan un elemento. Cada operación tiene un costo asociado, y el objetivo es encontrar la secuencia de ediciones con el menor costo total .

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

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

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

Existen diferentes variantes; véanse el algoritmo de Smith-Waterman y el algoritmo de Needleman-Wunsch .

La Torre de Hanoi es un juego matemático o rompecabezas . Consta de tres varillas y varios discos de diferentes tamaños que se deslizan sobre cualquiera de ellas. El juego comienza con los discos apilados ordenadamente en orden ascendente de tamaño sobre una varilla, con el más pequeño en la parte superior, formando así una figura cónica.

El objetivo del rompecabezas es mover toda la pila 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 demás discos que ya puedan 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 a mover, h denota la varilla de inicio, t denota la varilla objetivo, not(h,t) denota la tercera varilla (ni h ni t), ";" denota concatenación, y

S(n, h, t)  := solución a un problema que consiste en n discos que deben moverse de la varilla h a la varilla t.

Para n=1 el problema es trivial, a saber S(1,h,t) = "mover un disco de la varilla h a la varilla t" (solo 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 compleja y se requieren 3 ⁿ − 1 movimientos. ^{[ 14 ]}    

Un famoso acertijo consiste en dejar caer huevos desde un edificio para determinar a qué altura comienzan a romperse. La siguiente es una descripción que involucra N=2 huevos y un edificio con H=36 pisos: ^{[ 15 ]}

Supongamos que queremos saber desde qué pisos de un edificio de 36 plantas se pueden dejar caer huevos sin peligro, y desde cuáles se romperán al caer (usando la terminología del inglés estadounidense , donde la primera planta está a nivel del suelo). Partimos de algunas suposiciones:

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

Si solo disponemos de un huevo y queremos asegurarnos de obtener el resultado correcto, el experimento solo puede realizarse de una manera. Dejamos caer el huevo desde la ventana del primer piso; si sobrevive, lo dejamos caer desde la ventana del segundo piso. Continuamos subiendo hasta que se rompa. En el peor de los casos, este método puede requerir 36 intentos. Supongamos que disponemos de 2 huevos. ¿Cuál es el número mínimo de intentos que garantizan el éxito en todos los casos?

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

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

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

Por ejemplo, s = (2,6) indica que hay dos huevos de prueba disponibles y que quedan 6 pisos (consecutivos) por probar. El estado inicial del proceso es s = ( N , H ), donde N representa la cantidad de huevos de prueba disponibles al comienzo del experimento. El proceso finaliza cuando no quedan huevos de prueba ( n = 0) o cuando k = 0, lo que ocurra primero. Si la finalización se produce en el estado s = (0, k ) y k  >  0, entonces la prueba ha fallado.

Ahora, dejemos

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

Entonces se puede demostrar que ^{[ 16 ]}

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 iterativamente aumentando sistemáticamente los valores de n y k .  

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 sorprendente encontrar matrices de grandes dimensiones, por ejemplo 100×100. Por lo tanto, nuestra tarea es multiplicar matrices${\displaystyle A_{1},A_{2},....A_{n}}$La multiplicación de matrices no es conmutativa, sino asociativa; y solo podemos multiplicar dos matrices a la vez. Por lo tanto, podemos multiplicar esta cadena de matrices de muchas maneras diferentes, por ejemplo :

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

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

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

y así sucesivamente. Existen numerosas maneras de multiplicar esta cadena de matrices. Todas producirán el mismo resultado final, aunque el tiempo de cálculo variará según las matrices que se multipliquen. Si la matriz A tiene dimensiones m×n y la matriz B tiene dimensiones n×q, entonces la matriz C=A×B tendrá dimensiones m×q y requerirá m*n*q multiplicaciones escalares (utilizando un algoritmo simplificado de multiplicación de matrices a modo de ejemplo).

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×s y se puede calcular de dos maneras, como se muestra a continuación:

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

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

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

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

Llamemos m[i,j] al número mínimo de multiplicaciones escalares necesarias para multiplicar una cadena de matrices desde la matriz i hasta la matriz j (es decir, A _i × ... × A _j , es decir, i ≤ j). Dividimos la cadena en alguna matriz k, de modo que i ≤ k < j, e intentamos encontrar 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 columna de la matriz k,
• ⁠${\displaystyle p_{j}}$es la dimensión de columna de la matriz j.

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

función OptimalMatrixChainParenthesis(cadena) n = longitud(cadena) para i = 1, n m[i,i] = 0 // Dado que no se requieren cálculos para multiplicar una matriz para len = 2, n para i = 1, n - len + 1 j = i + len -1 m[i,j] = infinito // De modo que el primer cálculo se actualiza para k = i, j-1 q = m[i, k] + m[k+1, j] +${\displaystyle p_{i-1}*p_{k}*p_{j}}$Si q < m[i, j] // El nuevo orden de paréntesis es mejor que el que teníamos m[i, j] = q // Actualizar s[i, j] = k // Registrar en qué k dividir, es decir, dónde colocar el paréntesis

Hasta ahora, hemos calculado valores para todos los 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 "punto de división" correspondiente s [ i , j ] . Por ejemplo, si estamos multiplicando la cadena A ₁ × A ₂ × A ₃ × A ₄ , y resulta que m [1, 3] = 100 y s [1, 3] = 2 , eso significa que la colocación óptima de paréntesis para las matrices 1 a 3 es${\displaystyle (A_{1}\times A_{2})\times A_{3}}$y multiplicar esas matrices requerirá 100 cálculos escalares.

Este algoritmo generará las tablas m [, ] y s [, ] que contendrán entradas para todos los valores posibles de i y j. La solución final para toda la cadena es m[1, n], con la división correspondiente en s[1, n]. El desarrollo de la solución será recursivo, comenzando desde el principio y continuando hasta llegar al caso base, es decir, la multiplicación de matrices individuales.

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

función ImprimirParéntesisÓptimos(s, i, j) si i = j imprimir "A"i demás imprimir "(" ImprimirParéntesisÓptimo(s, i, s[i, j]) ImprimirParéntesisÓptimo(s, s[i, j] + 1, j) imprimir ")"

Por supuesto, este algoritmo no sirve para realizar multiplicaciones reales. Simplemente es una forma sencilla de visualizar el resultado.

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

función MatrixChainMultiply ( cadena de 1 a n ) // devuelve la matriz final, es decir, A1×A2×... ×An OptimalMatrixChainParenthesis ( cadena de 1 a n ) // esto producirá las "tablas" s[.] y m[.] OptimalMatrixMultiplication ( s , cadena de 1 a n ) // realmente multiplicafunción MultiplicaciónMatricesÓptima ( s , i , j ) // devuelve el resultado de multiplicar una cadena de matrices desde Ai hasta Aj de forma óptima si i < j // continúa dividiendo la cadena y multiplicando las matrices en los lados izquierdo y derecho LadoIzquierdo = MultiplicaciónMatricesÓptima ( s , i , s [ i , j ]) LadoDerecho = MultiplicaciónMatricesÓptima ( s , s [ i , j ] + 1 , j ) return MultiplicaciónMatrices ( LadoIzquierdo , LadoDerecho ) else if i = j return Ai // matriz en la posición i else print "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 ] retornar C sino imprimir "error, dimensiones incompatibles."