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

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

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

He leído el artículo de wikipedia , pero todavía no lo entiendo.

La progtwigción dinámica es cuando utiliza el conocimiento pasado para facilitar la solució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 ¿y si le doy los resultados para n = 1,000,000 yn = 1,000,001? De repente, el problema se volvió más manejable.

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

Con la progtwigción dinámica, usted almacena sus resultados en algún tipo de tabla en general. Cuando necesite la respuesta a un problema, haga referencia a la tabla y vea si ya sabe de qué se trata. Si no, utiliza los datos en su tabla para dar un paso hacia la respuesta.

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

La progtwigció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 definido por

F n = F n-1 + F n-2 y F 0 = 0, F 1 = 1

Recursión

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) 

Progtwigción dinámica

  • Top Down – 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 forma de hacerlo es deshacerse de la recursividad mediante la evaluación de 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 progtwigción dinámica?

    1. Encuentra la recursión en el problema.
    2. De arriba hacia abajo: almacene la respuesta para cada subproblema en una tabla para evitar tener que recalcularlos.
    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 progtwigción dinámica generalmente funciona para problemas que tienen un orden inherente de izquierda a derecha, como cadenas, árboles o secuencias enteras. Si el ingenuo algoritmo recursivo no calcula el mismo subproblema varias veces, la progtwigción dinámica no ayudará.

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

Aquí está mi respuesta en un tema similar

Empezar con

  • Artículo de wikipedia sobre progtwigción dinámica luego
  • Te sugiero que leas este artículo en Topcoder
  • ch6 sobre progtwigción dinámica en algoritmos (Vazirani)
  • Capítulo de progtwigción dinámica en Algorithms Design Manual
  • Capítulo de progtwigción dinámica en algoritmos libro clásico ( Introducción a algoritmos )

Si quieres ponerte a prueba, mis elecciones sobre los jueces en línea son

  • Problemas de progtwigción dinámica Uva
  • Problemas de progtwigción dinámica de Timus
  • Spoj Problemas de progtwigción dinámica
  • Problemas de progtwigción dinámica de TopCoder

y por supuesto

  • mira la categoría de progtwigción dinámica del algoritmo

También puedes ver buenos algoritmos de universidades cursos

  • Aduni (Algoritmos)
  • MIT (Introducción a los algoritmos (capítulo 15))

Después de todo, si no puede resolver los problemas, pregunte ASÍ que muchos algoritmos adictos existen aquí

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

La recursividad 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 a funciones iterativas similares, tampoco cambia la complejidad algorítmica.

La progtwigción dinámica es el proceso de resolver sub-problemas fáciles de resolver y construir la respuesta a partir de eso. La mayoría de los algoritmos de DP estarán en los tiempos de ejecución entre un algoritmo codicioso (si existe) y un algoritmo exponencial (enumerar todas las posibilidades y encontrar el mejor).

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

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

Mientras que un algoritmo codicioso generalmente se llama ingenuo , porque puede ejecutarse varias veces sobre el mismo conjunto de datos, la progtwigción dinámica evita este escollo 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 ha encontrado hasta el momento para que pueda evitar atravesar los mismos nodos una y otra vez.

Aquí hay un ejemplo de un problema que es adecuado para la progtwigción dinámica, desde el 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 progtwigción, sugiero que lo revisen.

Eche un buen vistazo a ese problema, si definimos una función de costo que nos diga cuán lejos están dos cadenas, tenemos dos que consideren los tres tipos naturales de cambios:

Sustitución: cambie un solo carácter del patrón “s” por un carácter diferente en el texto “t”, como cambiar “disparo” por “detectar”.

Inserción: inserte un único 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” por “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 ser emparejado, sustituido, insertado o eliminado. Cortar los caracteres en la última operación de edición deja una operación de par que deja un par de cadenas más pequeñas. Deje que i y j sean el último carácter del prefijo correspondiente de y t, respectivamente. hay tres pares de cadenas más cortas después de la última operación, que corresponden 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 recursión:

  #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.

Al correr en nuestra computadora, toma varios segundos comparar dos cadenas de 11 caracteres, y la computación desaparece en un estado de nunca jamás en algo más largo.

¿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 recursividad se bifurca 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 computando cosas que ya han sido calculadas anteriormente. ¿Como sabemos? Bueno, solo puede haber | s | · | T | posibles llamadas recursivas únicas, ya que solo existen 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 m bidimensional donde cada uno de los | s | · | t | cells contiene 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 progtwigción dinámica tiene tres diferencias con respecto a la versión recursiva.

En primer lugar, obtiene sus valores intermedios mediante la búsqueda de tabla en lugar de llamadas recursivas.

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

** Tercero, ** En tercer lugar, está instrumentado utilizando una función cell () de objective 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 uno “dynamic” a pesar de que su ejecución es diferente. Le sugiero que compruebe qué tan eficiente es la solución enviándola al juez en línea de UVA. Me parece sorprendente cómo un problema tan grave fue abordado tan eficientemente.

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

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

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

Debido a que estamos trabajando de abajo hacia arriba, ya tenemos soluciones para los sub-problemas cuando llega el momento de usarlos, al memorizarlos.

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

Progtwigción dinámica

Definición

La progtwigción dinámica (DP) es una técnica de diseño de algoritmo general para resolver problemas con sub-problemas superpuestos. Esta técnica fue inventada por el matemático estadounidense “Richard Bellman” en 1950.

Idea clave

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

Propiedades de progtwigció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, así que almacene sus resultados en una tabla.
  • Por lo tanto, cada instancia más pequeña se resuelve solo una vez.
  • Espacio adicional se usa para ahorrar tiempo.

Aquí hay un tutorial de Michael A. Trick de CMU que encontré particularmente útil:

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

Sin duda, se sum a todos los recursos que otros recomendaron (todos los demás recursos, especialmente CLR y Kleinberg, ¡los Tardos son muy buenos!).

La razón por la que me gusta este tutorial es porque introduce conceptos avanzados bastante gradualmente. Es un material algo anticuado, pero es una buena adición a la lista de recursos presentada aquí.

Consulte también la página de Steven Skiena y las conferencias sobre progtwigción dinámica: http://www.cs.sunysb.edu/~algorith/video-lectures/

http://www.cs.sunysb.edu/~algorith/video-lectures/1997/lecture12.pdf

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

En la mayoría de las palabras simples, solo piense en la progtwigció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 sub-problemas 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) 

Vamos a desglosar la llamada de función con decir 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 mm[n] := fib(n − 1) + fib(n − 2) return m[n] 

Aquí guardamos la solución de sub-problemas en el mapa, si es que aún no la tenemos. Esta técnica de guardar valores que ya habíamos calculado se denomina Memoización.

Por último, para un problema, primero intente encontrar los estados (posibles subproblemas y trate de pensar en el mejor enfoque de recursión para que pueda usar la solución del sub-problema anterior en más).

en resumen, la diferencia entre la memoria de recursividad y la progtwigción dinámica

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

Dónde aplicar la progtwigción dinámica: si su solución se basa en una subestructura óptima y en un subproblema superpuesto, entonces, en ese caso, será útil utilizar el valor calculado anteriormente para que no tenga que recalcularlo. Es un enfoque de abajo arriba. Supongamos 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)

Recursividad: básicamente subdividiendo tu problema en una parte más pequeña para resolverlo con facilidad, pero tenlo en cuenta, no evita el cálculo si tenemos el mismo valor calculado anteriormente en otra llamada de recursión.

Memoizació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 ha calculado 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í hay un ejemplo simple de código python de aproximación Recursive , Top-down , Bottom-up para series de Fibonacci:

Recursivo: O (2 ^ n)

 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 una entrada más grande

 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 simplificar 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))