dynamic-programming Tutorial
Empezando con la programación dinámica.

Observaciones

Introducción a la programación dinámica

La programación dinámica resuelve problemas al combinar las soluciones a los subproblemas. Puede ser análogo al método de dividir y conquistar, donde el problema se divide en subproblemas separados, los subproblemas se resuelven recursivamente y luego se combinan para encontrar la solución del problema original. En contraste, la programación dinámica se aplica cuando los subproblemas se superponen, es decir, cuando los subproblemas comparten subproblemas. En este contexto, un algoritmo de dividir y conquistar hace más trabajo del necesario, resolviendo repetidamente los subproyectos comunes. Un algoritmo de programación dinámica resuelve cada sub-problema solo una vez y luego guarda su respuesta en una tabla, evitando así el trabajo de volver a calcular la respuesta cada vez que resuelve cada sub-problema.

Veamos un ejemplo. El matemático italiano Leonardo Pisano Bigollo , a quien conocemos comúnmente como Fibonacci, descubrió una serie de números considerando el crecimiento idealizado de la población de conejos . La serie es:

1, 1, 2, 3, 5, 8, 13, 21, ......

Podemos notar que cada número después de los dos primeros es la suma de los dos números anteriores. Ahora, formulemos una función F (n) que nos devuelva el número n de Fibonacci, lo que significa que

F(n) = nth Fibonacci Number

Hasta ahora, hemos sabido que,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Podemos generalizarlo por:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Ahora, si queremos escribirlo como una función recursiva, tenemos F(1) y F(2) como nuestro caso base. Así que nuestra función de Fibonacci sería:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Ahora, si llamamos a F(6) , llamará a F(5) y F(4) , que llamará a algunos más. Vamos a representar esto gráficamente:

En la imagen, podemos ver que F(6) llamará a F(5) y F(4) . Ahora F(5) llamará a F(4) y F(3) . Después de calcular F(5) , seguramente podemos decir que todas las funciones que fueron llamadas por F(5) ya se han calculado. Eso significa que ya hemos calculado F(4) . Pero nuevamente estamos calculando F(4) como indica el hijo derecho de F(6) . ¿Realmente necesitamos recalcular? Lo que podemos hacer es que, una vez que hayamos calculado el valor de F(4) , lo almacenaremos en una matriz llamada dp y la reutilizaremos cuando sea necesario. Inicializaremos nuestra matriz dp con -1 (o cualquier valor que no aparezca en nuestro cálculo). Luego llamaremos a F (6) donde se verá nuestra F (n) modificada:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Hemos hecho la misma tarea que antes, pero con una optimización simple. Es decir, hemos utilizado la técnica de memoización . Al principio, todos los valores de dp array serán -1 . Cuando se llama F(4) , verificamos si está vacío o no. Si almacena -1 , calcularemos su valor y lo almacenaremos en dp [4] . Si almacena cualquier cosa menos -1 , eso significa que ya hemos calculado su valor. Así que simplemente devolveremos el valor.

Esta simple optimización utilizando memoización se llama Programación Dinámica .

Un problema se puede resolver utilizando la Programación Dinámica si tiene algunas características. Estos son:

• Subproblemas:
  Un problema de DP se puede dividir en uno o más subproblemas. Por ejemplo: F(4) se puede dividir en subproblemas más pequeños F(3) y F(2) . Como los subproblemas son similares a nuestro problema principal, estos pueden resolverse utilizando la misma técnica.
• Subproblemas superpuestos:
  Un problema de DP debe tener subproblemas superpuestos. Eso significa que debe haber una parte común para la cual la misma función se llama más de una vez. Por ejemplo: F(5) y F(6) tiene F(3) y F(4) en común. Esta es la razón por la que almacenamos los valores en nuestra matriz.

• Subestructura óptima:
  Digamos que se le pide que minimice la función g(x) . Usted sabe que el valor de g(x) depende de g(y) y g(z) . Ahora, si podemos minimizar g(x) minimizando tanto g(y) como g(z) , solo entonces podemos decir que el problema tiene una subestructura óptima. Si se minimiza g(x) minimizando solo g(y) y si minimiza o maximiza g(z) no tiene ningún efecto sobre g(x) , entonces este problema no tiene una subestructura óptima. En palabras simples, si la solución óptima de un problema puede encontrarse a partir de la solución óptima de su subproblema, entonces podemos decir que el problema tiene una propiedad de subestructura óptima.

Entendiendo el estado en la programación dinámica

Vamos a discutir con un ejemplo. De n artículos, ¿de cuántas maneras puede elegir r artículos? Usted sabe que se denota por . Ahora piensa en un solo artículo.

• Si no selecciona el elemento, después de eso tendrá que tomar r elementos de los elementos n-1 restantes, lo cual es dado por .
• Si selecciona el elemento, después de eso tendrá que tomar los elementos r-1 de los elementos n-1 restantes, lo cual es dado por .

La suma de estos dos nos da el número total de formas. Es decir:

Si pensamos nCr(n,r) como una función que toma n y r como parámetro y determina , podemos escribir la relación mencionada anteriormente como:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

Esta es una relación recursiva. Para terminarlo, necesitamos determinar los casos base. Lo sabemos, y . Usando estos dos como casos base, nuestro algoritmo para determinar estarán:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Si observamos el procedimiento gráficamente, podemos ver que algunas recursiones se llaman más de una vez. Por ejemplo: si tomamos n = 8 y r = 5 , obtenemos:

Podemos evitar esta llamada repetida usando una matriz, dp . Como hay 2 parámetros, necesitaremos una matriz 2D. Inicializaremos la matriz dp con -1 , donde -1 denota que el valor aún no se ha calculado. Nuestro procedimiento será:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Para determinar , necesitábamos dos parámetros n y r . Estos parámetros se denominan estado . Simplemente podemos deducir que el número de estados determina el número de dimensión de la matriz dp . El tamaño de la matriz cambiará de acuerdo con nuestra necesidad. Nuestros algoritmos de programación dinámica mantendrán el siguiente patrón general:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Determinar el estado es una de las partes más cruciales de la programación dinámica. Consiste en la cantidad de parámetros que definen nuestro problema y optimizando su cálculo, podemos optimizar todo el problema.

Construyendo una solución de DP

No importa cuántos problemas resuelva utilizando la programación dinámica (DP), todavía puede sorprenderlo. Pero como todo lo demás en la vida, la práctica te hace mejor. Teniendo esto en cuenta, veremos el proceso de construcción de una solución para problemas de DP. Otros ejemplos sobre este tema lo ayudarán a comprender qué es DP y cómo funciona. En este ejemplo, trataremos de comprender cómo crear una solución de DP desde cero.

Iterativo vs recursivo:
Existen dos técnicas de construcción de la solución DP. Son:

• Iterativa (usando para ciclos)
• Recursivo (usando recursión)

Por ejemplo, el algoritmo para calcular la longitud de la Subsecuencia Común Más Larga de dos cadenas s1 y s2 se vería así:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Esta es una solución iterativa. Hay algunas razones por las que se codifica de esta manera:

• La iteración es más rápida que la recursión.
• Determinar el tiempo y la complejidad del espacio es más fácil.
• El código fuente es corto y limpio

Mirando el código fuente, puede comprender fácilmente cómo y por qué funciona, pero es difícil entender cómo encontrar esta solución. Sin embargo, los dos enfoques mencionados anteriormente se traducen en dos pseudocódigos diferentes. Uno usa la iteración (Bottom-Up) y el otro utiliza el enfoque de recursión (Top-Down). La última también se conoce como técnica de memoización. Sin embargo, las dos soluciones son más o menos equivalentes y una puede transformarse fácilmente en otra. Para este ejemplo, mostraremos cómo encontrar una solución recursiva para un problema.

Problema de ejemplo:
Digamos que tiene N ( 1, 2, 3, ...., N ) vinos colocados uno al lado del otro en un estante. El precio del i-ésimo vino es p [i]. El precio de los vinos aumenta cada año. Supongamos que es el año 1 , en el año y el precio del vino i th será: año * precio del vino = y * p [i] . Quiere vender los vinos que tiene, pero tiene que vender exactamente un vino por año, a partir de este año. Una vez más, en cada año, se le permite vender solo el vino más a la izquierda o más a la derecha y no puede reorganizar los vinos, lo que significa que deben permanecer en el mismo orden que al principio.

Por ejemplo: digamos que tiene 4 vinos en la estantería, y sus precios son (de izquierda a derecha):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

La solución óptima sería vender los vinos en el orden 1 -> 4 -> 3 -> 2 , lo que nos dará un beneficio total de:

Enfoque codicioso:
Después de una lluvia de ideas durante un tiempo, puede encontrar la solución para vender el vino caro lo más tarde posible. Entonces tu estrategia codiciosa será:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Aunque la estrategia no menciona qué hacer cuando los dos vinos cuestan lo mismo, la estrategia se siente un poco correcta. Pero desafortunadamente, no lo es. Si los precios de los vinos son:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

La estrategia codiciosa los vendería en el orden 1 -> 2 -> 5 -> 4 -> 3 para un beneficio total de:

Pero podemos hacerlo mejor si vendemos los vinos en el orden 1 -> 5 -> 4 -> 2 -> 3 para un beneficio total de:

Este ejemplo debería convencerlo de que el problema no es tan fácil como parece a primera vista. Pero se puede resolver utilizando la Programación Dinámica.

Retroceso:
Crear una solución de memoria para un problema es útil para encontrar una solución de retroceso. La solución Backtrack evalúa todas las respuestas válidas para el problema y elige la mejor. Para la mayoría de los problemas, es más fácil encontrar tal solución. Puede haber tres estrategias a seguir para acercarse a una solución de retroceso:

1. debe ser una función que calcula la respuesta usando la recursión.
2. debe devolver la respuesta con declaración de retorno .
3. todas las variables no locales deben usarse como de solo lectura, es decir, la función puede modificar solo las variables locales y sus argumentos.

Para nuestro problema de ejemplo, trataremos de vender el vino más a la izquierda o más a la derecha y calcularemos recursivamente la respuesta y devolveremos la mejor. La solución de retroceso se vería así:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Si llamamos al procedimiento utilizando la determinación de profitDetermination(1, 0, n-1) , donde n es el número total de vinos, devolverá la respuesta.

Esta solución simplemente prueba todas las posibles combinaciones válidas de venta de vinos. Si al principio hay n vinos, comprobará posibilidades Aunque ahora obtenemos la respuesta correcta, la complejidad del tiempo del algoritmo crece exponencialmente.

La función de retroceso correctamente escrita siempre debe representar una respuesta a una pregunta bien formulada. En nuestro ejemplo, el procedimiento profitDetermination representa una respuesta a la pregunta: ¿Cuál es el mejor beneficio que podemos obtener al vender los vinos con precios almacenados en la matriz p, cuando el año actual es el año y el intervalo de los vinos no vendidos se extiende hasta [comenzar , fin], inclusive? Siempre debe intentar crear una pregunta de este tipo para su función de marcha atrás para ver si lo entendió bien y entender exactamente lo que hace.

Estado determinante:
Estado es el número de parámetros utilizados en la solución de DP. En este paso, debemos pensar en cuáles de los argumentos que pasa a la función son redundantes, es decir, podemos construirlos a partir de los otros argumentos o no los necesitamos en absoluto. Si existen tales argumentos, no necesitamos pasarlos a la función, los calcularemos dentro de la función.

En la función de ejemplo profitDetermination muestra arriba, el year del argumento es redundante. Es equivalente a la cantidad de vinos que ya hemos vendido más uno. Se puede determinar utilizando el número total de vinos desde el principio menos el número de vinos que no hemos vendido más uno. Si almacenamos el número total de vinos n como una variable global, podemos reescribir la función como:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

También debemos pensar en el rango de valores posibles de los parámetros que se pueden obtener de una entrada válida. En nuestro ejemplo, cada uno de los parámetros begin y end puede contener valores de 0 a n-1 . En una entrada válida, también esperaremos begin <= end + 1 . Puede haber O(n²) diferentes argumentos con los que se puede llamar a nuestra función.

Memorización
Ya casi hemos terminado. Transformar la solución de retroceso con complejidad de tiempo. en solución de memoria con complejidad de tiempo , usaremos un pequeño truco que no requiere mucho esfuerzo.

Como se señaló anteriormente, sólo hay Diferentes parámetros nuestra función puede ser llamada con. En otras palabras, sólo hay Diferentes cosas que realmente podemos calcular. Entonces donde hace El tiempo viene de la complejidad y ¿qué se computa?

La respuesta es: la complejidad del tiempo exponencial proviene de la repetición recursiva y debido a eso, calcula los mismos valores una y otra vez. Si ejecuta el código mencionado anteriormente para un conjunto arbitrario de n = 20 vinos y calcula cuántas veces se llamó la función para los argumentos begin = 10 y end = 10 , obtendrá un número 92378 . Es una enorme pérdida de tiempo calcular la misma respuesta muchas veces. Lo que podríamos hacer para mejorar esto es almacenar los valores una vez que los hayamos computado y cada vez que la función solicite un valor ya calculado, no necesitamos ejecutar la recursión completa nuevamente. Tendremos una matriz dp [N] [N] , la inicializaremos con -1 (o cualquier valor que no aparezca en nuestro cálculo), donde -1 denota que el valor aún no se ha calculado. El tamaño de la matriz está determinado por el valor máximo posible de inicio y finalización, ya que almacenaremos los valores correspondientes de ciertos valores de inicio y finalización en nuestra matriz. Nuestro procedimiento se vería como:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Esta es nuestra solución de DP requerida. Con nuestro truco muy simple, la solución se ejecuta. tiempo, porque hay diferentes parámetros con los que se puede llamar a nuestra función y para cada uno de ellos, la función se ejecuta solo una vez con complejidad.

Veraniego:
Si puede identificar un problema que se puede resolver utilizando DP, siga los siguientes pasos para construir una solución DP:

• Cree una función de retroceso para proporcionar la respuesta correcta.
• Eliminar los argumentos redundantes.
• Estimar y minimizar el rango máximo de valores posibles de parámetros de función.
• Intente optimizar la complejidad del tiempo de una llamada de función.
• Almacena los valores para que no tengas que calcularlos dos veces.

La complejidad de una solución de DP es: rango de valores posibles a los que se puede llamar la función con * complejidad de tiempo de cada llamada .