Primeros pasos con la programación dinámica

Introducción a la programación dinámica

Programación dinámica resuelve problemas combinando las soluciones de los subproblemas. Puede ser análogo al método divide y vencerás, 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. Por el contrario, la programación dinámica se aplica cuando los subproblemas se superponen, es decir, cuando los subproblemas comparten subproblemas. En este contexto, un algoritmo divide y vencerás hace más trabajo del necesario, resolviendo repetidamente los subsubproblemas comunes. Un algoritmo de programación dinámica resuelve cada subsubproblema 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 subsubproblema.

Veamos un ejemplo. El matemático italiano Leonardo Pisano Bigollo, a quien comúnmente conocemos como Fibonacci, descubrió una serie de números considerando el [crecimiento idealizado de la población de conejos](https://en .wikipedia.org/wiki/Fibonacci_number#Origins). 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 devolverá el n-ésimo número de Fibonacci, es decir,

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 generalizar 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. Entonces 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 algunas más. Representemos esto gráficamente:

Árbol recursivo para F(6)

En la imagen, podemos ver que F(6) llamará F(5) y F(4). Ahora F(5) llamará 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 han sido calculadas. Eso significa que ya hemos calculado F(4). Pero de nuevo estamos calculando F(4) como indica el hijo derecho de F(6). ¿Realmente necesitamos recalcular? Lo que podemos hacer es, una vez que hayamos calculado el valor de F(4), lo almacenaremos en una matriz llamada dp y lo 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 nuestra F(n) modificada se verá así:

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 la matriz dp serán -1. Cuando se llama a F(4), comprobamos si está vacío o no. Si almacena -1, calcularemos su valor y lo almacenaremos en dp4. Si almacena cualquier cosa menos -1, eso significa que ya hemos calculado su valor. Así que simplemente devolveremos el valor.

Esta optimización simple usando memorización se llama Programación Dinámica.

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

  • Subproblemas:
    Un problema de PD 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 alguna parte común para la cual se llama a la misma función más de una vez. Por ejemplo: F(5) y F(6) tienen F(3) y F(4) en común. Esta es la razón por la que almacenamos los valores en nuestra matriz.

Gráfico de subproblemas superpuestos

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

Comprender el estado en la programación dinámica

Vamos a discutir con un ejemplo. De n artículos, ¿de cuántas formas puedes elegir r artículos? Sabes que se denota por nCr. Ahora piensa en un solo artículo.

  • Si no selecciona el elemento, después de eso, debe tomar r elementos de los n-1 elementos restantes, que se obtiene mediante (n-1)Cr .
  • Si selecciona el elemento, después de eso, debe tomar r-1 elementos de los restantes n-1 elementos, que se obtiene mediante (n-1)C(r-1) .

La suma de estos dos nos da el número total de formas. Eso es:
nCr = (n-1)Cr + (n-1)C(r-1)

Si pensamos en nCr(n,r) como una función que toma n y r como parámetro y determina nCr, 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. Sabemos que, nC1 = n y nCn = 1. Usando estos dos como casos base, nuestro algoritmo para determinar nCr será:

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:

Árbol de recurrencia que muestra un subproblema superpuesto

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 indica 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 nCr, 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 dimensiones de la matriz dp. El tamaño de la matriz cambiará según 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 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.

Construcción de una solución de DP

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

Iterativo VS Recursivo:
Hay dos técnicas para construir una solución DP. Están:

  • Iterativo (utilizando ciclos for)
  • Recursivo (usando recursividad)

Por ejemplo, algoritmo para calcular la longitud de la [Subsecuencia común más larga](https://www.wikiod.com/es/dynamic-programming/algoritmos-relacionados-con-subsecuencias#Subsecuencia común más larga t=201611230422107601679) 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 recursividad.
  • Determinar la complejidad temporal y espacial es más fácil.
  • El código fuente es corto y limpio.

Mirando el código fuente, puede entender fácilmente cómo y por qué funciona, pero es difícil entender cómo llegar a esta solución. Sin embargo, los dos enfoques mencionados anteriormente se traducen en dos pseudocódigos diferentes. Uno usa la iteración (de abajo hacia arriba) y otro usa el enfoque de recursividad (de arriba hacia abajo). Esta última también se conoce como técnica de memorizació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 llegar a 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 este es el año 1, en el año y el precio del iésimo vino 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, puede 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 en que estaban al principio.

Por ejemplo: supongamos que tiene 4 vinos en el estante 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á una ganancia total de: [! 11+32+23+44=29]1

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. Así que 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 parece 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 por una ganancia total de: [! 21+32+43+14+5*5=49]2

Pero podemos hacerlo mejor si vendemos los vinos en el orden 1 -> 5 -> 4 -> 2 -> 3 para una ganancia total de: 2<em>1+4</em>2+1<em>3+3</em>4+5*5=50

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

Retroceso:
Para encontrar la solución de memorización para un problema, es útil encontrar una solución de retroceso. Backtrack solution 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 llegar a esa solución. Puede haber tres estrategias a seguir para abordar una solución de retroceso:

  1. debe ser una función que calcule la respuesta usando recursividad.
  2. debe devolver la respuesta con la instrucción return.
  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, intentaremos 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 usando 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 los vinos. Si hay n vinos al principio, comprobará 2^n posibilidades. Aunque ahora obtenemos la respuesta correcta, la complejidad temporal 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 gananciaDeterminación representa una respuesta a la pregunta: ¿Cuál es la mejor ganancia que podemos obtener vendiendo los vinos con precios almacenados en la matriz p, cuando el año actual es año y el intervalo de vinos no vendidos abarca hasta [begin, end], inclusive? Siempre debe intentar crear una pregunta de este tipo para su función de retroceso para ver si lo hizo bien y comprender exactamente lo que hace.

Estado determinante:
Estado es el número de parámetros utilizados en la solución 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 ‘gananciaDeterminación’ que se muestra arriba, el argumento ‘año’ es redundante. Es equivalente al número 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 desde 0 hasta 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.

Memoización:
Ya casi hemos terminado. Para transformar la solución de retroceso con complejidad temporal O(2^n) en una solución de memorización con complejidad temporal O(n^2), utilizará un pequeño truco que no requiere mucho esfuerzo.

Como se señaló anteriormente, solo hay O(n^2) parámetros diferentes con los que se puede llamar a nuestra función. En otras palabras, solo hay O(n^2) cosas diferentes que podemos calcular. Entonces, ¿de dónde viene la complejidad del tiempo O(2^n) y qué calcula?

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

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 DP requerida. Con nuestro truco muy simple, la solución se ejecuta O(n^2) tiempo, porque hay O(n^2) parámetros diferentes nuestra función se puede llamar con y para cada uno de ellos, la función se ejecuta solo una vez con una complejidad de O(1).

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

  • Crear 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 los parámetros de una función.
  • Intente optimizar la complejidad del tiempo de una llamada de función.
  • Almacene los valores para que no tenga que calcularlos dos veces.

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