¿Qué es la programación dinámica? [cerrado]

¿Qué es la programación dinámica ?

¿En qué se diferencia de recursividad, memorización, etc.?

He leído el artículo de Wikipedia en él, pero todavía no lo entiendo.

La programación dinámica es cuando utiliza el conocimiento pasado para facilitar la resolución de un problema futuro.

Un buen ejemplo es resolver la secuencia de Fibonacci para n = 1,000,002.

Este será un proceso muy largo, pero ¿qué pasa si le doy los resultados para n = 1,000,000 yn = 1,000,001? De repente, el problema se volvió más manejable.

La programación dinámica se usa mucho en problemas de cadenas, como el problema de edición de cadenas. Usted resuelve un subconjunto (s) del problema y luego usa esa información para resolver el problema original más difícil.

Con la programación dinámica, generalmente almacena sus resultados en algún tipo de tabla. Cuando necesite la respuesta a un problema, haga referencia a la tabla y vea si ya sabe cuál es. Si no, usa los datos en su tabla para darse un paso hacia la respuesta.

El libro de Algoritmos de Cormen tiene un gran capítulo sobre programación dinámica. ¡Y es gratis en Google Books! Compruébalo aquí.

La programación dinámica es una técnica utilizada para evitar calcular varias veces el mismo subproblema en un algoritmo recursivo.

Tomemos el ejemplo simple de los números de Fibonacci: encontrar el n ^º número de Fibonacci definida por

F _n = F _n-1 + F _n-2 y F ₀ = 0, F ₁ = 1

Recursividad

La forma obvia de hacer esto es recursiva:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Programación dinámica

• De arriba hacia abajo - Memoization

La recursión hace muchos cálculos innecesarios porque un número de Fibonacci determinado se calculará varias veces. Una manera fácil de mejorar esto es almacenar en caché los resultados:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

• De abajo hacia arriba

Una mejor manera de hacer esto es deshacerse de la recursión al evaluar los resultados en el orden correcto:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

Incluso podemos usar espacio constante y almacenar solo los resultados parciales necesarios en el camino:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

• ¿Cómo aplicar la programación dinámica?

  1. Encuentra la recursividad en el problema.
  2. De arriba hacia abajo: guarde la respuesta para cada subproblema en una tabla para evitar tener que volver a calcularlos.
  3. De abajo hacia arriba: encuentre el orden correcto para evaluar los resultados para que los resultados parciales estén disponibles cuando sea necesario.

La programación dinámica generalmente funciona para problemas que tienen un orden inherente de izquierda a derecha, como cadenas, árboles o secuencias de enteros. Si el ingenuo algoritmo recursivo no calcula el mismo subproblema varias veces, la programación dinámica no ayudará.

Hice una colección de problemas para ayudar a entender la lógica: https://github.com/tristanguigue/dynamic-programing

La memorización es cuando almacena resultados previos de una llamada a función (una función real siempre devuelve lo mismo, dadas las mismas entradas). No hace una diferencia para la complejidad algorítmica antes de que se almacenen los resultados.

La recursión es el método de una función que se llama a sí misma, generalmente con un conjunto de datos más pequeño. Dado que la mayoría de las funciones recursivas se pueden convertir en funciones iterativas similares, esto tampoco hace una diferencia para la complejidad algorítmica.

La programación dinámica es el proceso de resolver subproblemas más fáciles de resolver y construir la respuesta a partir de eso. La mayoría de los algoritmos DP estarán en el tiempo de ejecución entre un algoritmo Greedy (si existe) y un algoritmo exponencial (enumere todas las posibilidades y encuentre el mejor).

• Los algoritmos DP podrían implementarse con recursividad, pero no tienen que serlo.
• Los algoritmos DP no se pueden acelerar mediante la memorización, ya que cada subproblema solo se resuelve (o se llama a la función "resolver") una vez.

Es una optimización de su algoritmo que reduce el tiempo de ejecución.

Si bien un algoritmo codicioso generalmente se llama ingenuo , ya que puede ejecutarse varias veces sobre el mismo conjunto de datos, la programación dinámica evita esta trampa a través de una comprensión más profunda de los resultados parciales que deben almacenarse para ayudar a construir la solución final.

Un ejemplo simple es atravesar un árbol o un gráfico solo a través de los nodos que contribuirían con la solución, o poner en una tabla las soluciones que has encontrado hasta ahora para que puedas evitar atravesar los mismos nodos una y otra vez.

Aquí hay un ejemplo de un problema adecuado para la programación dinámica, del juez en línea de UVA: Edit Steps Ladder.

Voy a hacer un breve resumen de la parte importante del análisis de este problema, tomado del libro Desafíos de programación, le sugiero que lo revise.

Mire bien ese problema, si definimos una función de costo que nos dice cuán lejos están dos cadenas, tenemos dos considerar los tres tipos naturales de cambios:

Sustitución: cambie un solo carácter del patrón "s" a un carácter diferente en el texto "t", como cambiar "disparo" a "spot".

Inserción: inserte un solo carácter en el patrón "s" para que coincida con el texto "t", como cambiar "ago" por "agog".

Eliminación: elimine un solo carácter del patrón "s" para que coincida con el texto "t", como cambiar "hora" a "nuestro".

Cuando establecemos que cada una de estas operaciones cuesta un paso, definimos la distancia de edición entre dos cadenas. Entonces, ¿cómo lo calculamos?

Podemos definir un algoritmo recursivo utilizando la observación de que el último carácter de la cadena debe coincidir, sustituirse, insertarse o eliminarse. Cortar los caracteres en la última operación de edición deja un par de operaciones deja un par de cadenas más pequeñas. Sea i y j el último carácter del prefijo relevante de y t, respectivamente. Hay tres pares de cadenas más cortas después de la última operación, correspondientes a la cadena después de una coincidencia / sustitución, inserción o eliminación. Si supiéramos el costo de editar los tres pares de cadenas más pequeñas, podríamos decidir qué opción conduce a la mejor solución y elegir esa opción en consecuencia. Podemos aprender este costo, a través de lo increíble que es la recursividad:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Este algoritmo es correcto, pero también es increíblemente lento.

Ejecutando en nuestra computadora, lleva varios segundos comparar dos cadenas de 11 caracteres, y el cálculo desaparece en nunca más nunca aterriza en nada.

¿Por qué el algoritmo es tan lento? Lleva tiempo exponencial porque vuelve a calcular los valores una y otra y otra vez. En cada posición de la cadena, la recursión se ramifica de tres maneras, lo que significa que crece a un ritmo de al menos 3 ^ n, de hecho, incluso más rápido ya que la mayoría de las llamadas reducen solo uno de los dos índices, no ambos.

Entonces, ¿cómo podemos hacer que el algoritmo sea práctico? La observación importante es que la mayoría de estas llamadas recursivas están calculando cosas que ya se han calculado antes. ¿Como sabemos? Bueno, solo puede haber | s | · | T | posibles llamadas recursivas únicas, ya que solo hay muchos pares distintos (i, j) que sirven como parámetros de llamadas recursivas.

Al almacenar los valores para cada uno de estos pares (i, j) en una tabla, podemos evitar volver a calcularlos y simplemente buscarlos según sea necesario.

La tabla es una matriz bidimensional m donde cada una de las | s | · | t | Las celdas contienen el costo de la solución óptima de este subproblema, así como un puntero principal que explica cómo llegamos a esta ubicación:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

La versión de programación dinámica tiene tres diferencias con respecto a la versión recursiva.

Primero, obtiene sus valores intermedios usando la búsqueda de tabla en lugar de llamadas recursivas.

** Segundo, ** actualiza el campo padre de cada celda, lo que nos permitirá reconstruir la secuencia de edición más adelante.

** Tercero, ** Tercero, se instrumenta usando una cell()función de objetivo más general en lugar de simplemente devolver m [| s |] [| t |] .cost. Esto nos permitirá aplicar esta rutina a una clase más amplia de problemas.

Aquí, un análisis muy particular de lo que se necesita para obtener los resultados parciales más óptimos es lo que hace que la solución sea "dinámica".

Aquí hay una solución alternativa completa para el mismo problema. También es "dinámico" a pesar de que su ejecución es diferente. Le sugiero que compruebe cuán eficiente es la solución enviándola al juez en línea de UVA. Me parece sorprendente cómo se abordó un problema tan pesado de manera tan eficiente.

Los bits clave de la programación dinámica son "subproblemas superpuestos" y "subestructura óptima". Estas propiedades de un problema significan que una solución óptima se compone de las soluciones óptimas para sus subproblemas. Por ejemplo, los problemas de la ruta más corta exhiben una subestructura óptima. La ruta más corta de A a C es la ruta más corta de A a algún nodo B seguido de la ruta más corta de ese nodo B a C.

En mayor detalle, para resolver un problema de ruta más corta:

• encuentre las distancias desde el nodo inicial hasta cada nodo que lo toca (digamos de A a B y C)
• encuentre las distancias desde esos nodos hasta los nodos que los tocan (de B a D y E, y de C a E y F)
• ahora conocemos la ruta más corta de A a E: es la suma más corta de Ax y xE para algún nodo x que hemos visitado (B o C)
• repita este proceso hasta llegar al nodo de destino final

Debido a que estamos trabajando de abajo hacia arriba, ya tenemos soluciones a los subproblemas a la hora de usarlos, memorizándolos.

Recuerde, los problemas de programación dinámica deben tener subproblemas superpuestos y una subestructura óptima. Generar la secuencia de Fibonacci no es un problema de programación dinámica; utiliza la memorización porque tiene subproblemas superpuestos, pero no tiene una subestructura óptima (porque no hay ningún problema de optimización involucrado).

Programación dinámica

Definición

La programación dinámica (DP) es una técnica general de diseño de algoritmos para resolver problemas con subproblemas superpuestos. Esta técnica fue inventada por el matemático estadounidense "Richard Bellman" en la década de 1950.

Idea clave

La idea clave es guardar las respuestas de subproblemas superpuestos más pequeños para evitar el recálculo.

Propiedades de programación dinámica

• Una instancia se resuelve utilizando las soluciones para instancias más pequeñas.
• Las soluciones para una instancia más pequeña pueden ser necesarias varias veces, por lo tanto, almacene sus resultados en una tabla.
• Por lo tanto, cada instancia más pequeña se resuelve solo una vez.
• Se utiliza espacio adicional para ahorrar tiempo.

También soy muy nuevo en la programación dinámica (un algoritmo poderoso para un tipo particular de problemas)

En palabras más simples, solo piense en la programación dinámica como un enfoque recursivo con el uso del conocimiento previo

El conocimiento previo es lo que más importa aquí. Haga un seguimiento de la solución de los subproblemas que ya tiene.

Considere esto, el ejemplo más básico para dp de Wikipedia

Encontrar la secuencia de fibonacci

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

Analicemos la llamada a la función con say n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((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 lleva a un algoritmo de tiempo exponencial.

Ahora, intentemos almacenando el valor que ya descubrimos en una estructura de datos, digamos un Mapa

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]

Aquí estamos guardando la solución de subproblemas en el mapa, si aún no la tenemos. Esta técnica de guardar valores que ya habíamos calculado se denomina Memoization.

Por último, para un problema, primero intente encontrar los estados (posibles subproblemas e intente pensar en el mejor enfoque de recursión para que pueda usar la solución del subproblema anterior en otros).

La programación dinámica es una técnica para resolver problemas con problemas secundarios superpuestos. Un algoritmo de programación dinámica resuelve cada subproblema solo una vez y luego guarda su respuesta en una tabla (matriz). Evitar el trabajo de volver a calcular la respuesta cada vez que se encuentra el subproblema. La idea subyacente de la programación dinámica es: Evite calcular las mismas cosas dos veces, generalmente manteniendo una tabla de resultados conocidos de subproblemas.

Los siete pasos en el desarrollo de un algoritmo de programación dinámica son los siguientes:

1. Establezca una propiedad recursiva que brinde la solución a una instancia del problema.
2. Desarrollar un algoritmo recursivo según la propiedad recursiva
3. Vea si la misma instancia del problema se está resolviendo nuevamente y nuevamente en llamadas recursivas
4. Desarrollar un algoritmo recursivo memorable.
5. Vea el patrón al almacenar los datos en la memoria
6. Convierta el algoritmo recursivo memorizado en algoritmo iterativo
7. Optimice el algoritmo iterativo utilizando el almacenamiento según sea necesario (optimización del almacenamiento)

en resumen, la diferencia entre la memoria de recursión y la programación dinámica

La programación dinámica como sugiere su nombre es utilizar el valor calculado anterior para construir dinámicamente la próxima solución nueva

Dónde aplicar la programación dinámica: si su solución se basa en una subestructura óptima y un subproceso superpuesto, en ese caso será útil usar el valor calculado anterior para que no tenga que volver a calcularlo. Es un enfoque de abajo hacia arriba. Suponga que necesita calcular fib (n) en ese caso, todo lo que necesita hacer es agregar el valor calculado anterior de fib (n-1) y fib (n-2)

Recursión: Básicamente subdividiendo su problema en una parte más pequeña para resolverlo con facilidad, pero tenga en cuenta que no evita el recálculo si tenemos el mismo valor calculado previamente en otra llamada de recursión.

Memorización: Básicamente, el almacenamiento del antiguo valor de recursión calculado en la tabla se conoce como memorización, lo que evitará el recálculo si ya ha sido calculado por alguna llamada anterior, por lo que cualquier valor se calculará una vez. Entonces, antes de calcular, verificamos si este valor ya se calculó o no, si ya se calculó, luego devolvemos lo mismo de la tabla en lugar de volver a calcular. También es un enfoque de arriba hacia abajo

Aquí está un ejemplo sencillo de código Python Recursive, Top-down, Bottom-upenfoque para la serie de Fibonacci:

Recursivo: O (2 ⁿ )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

De arriba hacia abajo: O (n) Eficiente para entradas más grandes

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

De abajo hacia arriba: O (n) Para simplicidad y pequeños tamaños de entrada

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))