Progtwigción dinámica y memorización: enfoques ascendentes frente a descendentes

No estoy seguro de entender el enfoque de arriba hacia abajo con la memorización y el método ascendente correctamente.

De abajo hacia arriba: es donde primero ves los subproblemas “más pequeños” y luego resuelves los subproblemas más grandes usando la solución al problema más pequeño.

De arriba hacia abajo: resuelva el problema de forma natural y compruebe si ha calculado la solución al subproblema anteriormente.

Estoy un poco confundido. ¿Alguien puede explicarlo? ¿Y cual es la diferencia?

rev4: un comentario muy eloquent del usuario Sammaron ha notado que, tal vez, esta respuesta confundía previamente de arriba hacia abajo y de abajo hacia arriba. Si bien originalmente esta respuesta (rev3) y otras respuestas decían que “de abajo hacia arriba es la memorización” (“asumir los subproblemas”), puede ser la inversa (es decir, “de arriba hacia abajo” puede ser “asumir los subproblemas” y ” de abajo hacia arriba “puede ser” componen los subproblemas “). Previamente, he leído que la memorización es un tipo diferente de progtwigción dinámica en oposición a un subtipo de progtwigción dinámica. Estaba citando ese punto de vista a pesar de no suscribirme a él. He reescrito esta respuesta para ser agnóstico de la terminología hasta que se encuentren referencias adecuadas en la literatura. También he convertido esta respuesta a una wiki de la comunidad. Por favor, prefiere fonts académicas. Lista de referencias: {Web: 1 , 2 } {Literatura: 5 }

Resumen

La progtwigción dinámica se trata de ordenar sus cálculos de una manera que evite volver a calcular el trabajo duplicado. Usted tiene un problema principal (la raíz de su árbol de subproblemas) y subproblemas (subárboles). Los subproblemas generalmente se repiten y se superponen .

Por ejemplo, considere su ejemplo favorito de Fibonnaci. Este es el árbol completo de subproblemas, si hiciéramos una llamada ingenua recursiva:

TOP of the tree fib(4) fib(3)...................... + fib(2) fib(2)......... + fib(1) fib(1)........... + fib(0) fib(1) + fib(0) fib(1) fib(1) fib(0) fib(1) fib(0) BOTTOM of the tree 

(En algunos otros problemas raros, este árbol podría ser infinito en algunas twigs, representando la no terminación, y por lo tanto, la parte inferior del árbol puede ser infinitamente grande. Además, en algunos problemas es posible que no sepas cómo es el árbol completo antes de Por lo tanto, es posible que necesite una estrategia / algoritmo para decidir qué subproblemas revelar.


Memoización, Tabulación

Existen al menos dos técnicas principales de progtwigción dinámica que no son mutuamente excluyentes:

  • Memoización: este es un enfoque de laissez-fair: supone que ya ha calculado todos los subproblemas y que no tiene idea de cuál es el orden de evaluación óptimo. Normalmente, realizaría una llamada recursiva (o algún equivalente iterativo) desde la raíz, y o bien esperaría que se acerque a la orden de evaluación óptima, u obtener una prueba de que lo ayudará a llegar a la orden de evaluación óptima. Se aseguraría de que la llamada recursiva nunca recalcule un subproblema porque almacena en caché los resultados, y por lo tanto, los subárboles duplicados no se vuelven a calcular.

    • ejemplo: si está calculando la secuencia Fibonacci fib(100) , simplemente llamaría esto, y llamaría a fib(100)=fib(99)+fib(98) , lo que llamaría fib(99)=fib(98)+fib(97) , … etc …, lo que llamaría fib(2)=fib(1)+fib(0)=1+0=1 . Entonces finalmente resolvería fib(3)=fib(2)+fib(1) , pero no necesita recalcular fib(2) , porque lo almacenamos en caché.
    • Esto comienza en la parte superior del árbol y evalúa los subproblemas de las hojas / subárboles hacia la raíz.
  • Tabulación: también puede pensar en la progtwigción dinámica como un algoritmo de “llenado de tablas” (aunque generalmente es multidimensional, esta “tabla” puede tener geometrías no euclidianas en casos muy raros *). Esto es como la memorización, pero más activo, e implica un paso adicional: debe elegir, con anticipación, el orden exacto en el que realizará sus cálculos. Esto no debería implicar que la orden debe ser estática, pero que tiene mucha más flexibilidad que la memorización.

    • ejemplo: si está realizando fibonacci, puede optar por calcular los números en este orden: fib(2) , fib(3) , fib(4) … almacenando en caché cada valor para que pueda calcular los siguientes más fácilmente. También puede pensar que se trata de llenar una tabla (otra forma de almacenamiento en caché).
    • Personalmente, no escucho mucho la palabra ‘tabulación’, pero es un término muy decente. Algunas personas consideran esta “progtwigción dinámica”.
    • Antes de ejecutar el algoritmo, el progtwigdor considera todo el árbol, luego escribe un algoritmo para evaluar los subproblemas en un orden particular hacia la raíz, generalmente rellenando una tabla.
    • * nota al pie: Algunas veces, la ‘tabla’ no es una tabla rectangular con conectividad cuadriculada, per se. Por el contrario, puede tener una estructura más complicada, como un árbol o una estructura específica para el dominio del problema (por ejemplo, ciudades dentro de la distancia de vuelo en un mapa), o incluso un diagtwig enrejado que, aunque no parezca una cuadrícula, no tiene una estructura de conectividad arriba-abajo-izquierda-derecha, etc. Por ejemplo, user3290797 enlazó un ejemplo de progtwigción dinámica para encontrar el conjunto independiente máximo en un árbol , que corresponde al llenado de los espacios en blanco en un árbol.

(En general, en un paradigma de “progtwigción dinámica”, diría que el progtwigdor considera todo el árbol, luego escribe un algoritmo que implementa una estrategia para evaluar subproblemas que puede optimizar las propiedades que desee (generalmente una combinación de tiempo-complejidad) y la complejidad del espacio). Su estrategia debe comenzar en alguna parte, con algún subproblema particular, y tal vez se pueda adaptar en función de los resultados de esas evaluaciones. En el sentido general de “progtwigción dinámica”, puede tratar de almacenar en caché estos subproblemas, y más En general, trate de evitar revisar los subproblemas con una distinción sutil, tal vez sea el caso de los gráficos en varias estructuras de datos. Muy a menudo, estas estructuras de datos están en su núcleo como matrices o tablas. Las soluciones a subproblemas pueden descartarse si no las necesitamos nunca más.)

[Anteriormente, esta respuesta hacía una statement sobre la terminología de arriba hacia abajo o de abajo hacia arriba; Claramente hay dos enfoques principales llamados Memoización y Tabulación que pueden estar en biyección con esos términos (aunque no del todo). El término general que la mayoría de las personas usa sigue siendo “Progtwigción dinámica” y algunas personas dicen “Memoización” para referirse a ese subtipo particular de “Progtwigción dinámica”. Esta respuesta se reduce a decir cuál es de arriba hacia abajo y de abajo hacia arriba hasta que la comunidad pueda encontrar las referencias adecuadas en los documentos académicos. En última instancia, es importante entender la distinción en lugar de la terminología.]


Pros y contras

Facilidad de encoding

La memorización es muy fácil de codificar (generalmente puede * escribir una anotación “memoizer” o función de envoltura que automáticamente lo hace por usted), y debe ser su primera línea de enfoque. La desventaja de la tabulación es que tienes que inventar un pedido.

* (esto es realmente sencillo si está escribiendo la función usted mismo, y / o está codificando en un lenguaje de progtwigción impuro / no funcional … por ejemplo, si alguien ya escribió una función fib precomstackda, necesariamente hace llamadas recursivas a sí misma, y no puede memorizar mágicamente la función sin asegurarse de que esas llamadas recursivas llamen a su nueva función memorada (y no a la función original no conmemorada))

Recursividad

Tenga en cuenta que tanto desde arriba como desde abajo se pueden implementar con recurrencia o llenado iterativo de tablas, aunque puede no ser natural.

Preocupaciones prácticas

Con la memorización, si el árbol es muy profundo (p. Ej. fib(10^6) ), se quedará sin espacio en la stack, porque cada cómputo demorado debe colocarse en la stack, y tendrá 10 ^ 6 de ellos.

Optimalidad

Cualquiera de los enfoques puede no ser óptimo en el tiempo si el orden en que ocurre (o intenta) visitar subproblemas no es óptimo, específicamente si hay más de una forma de calcular un subproblema (normalmente el caché resolvería esto, pero teóricamente es posible que el almacenamiento en caché pueda no en algunos casos exóticos). La memorización generalmente agregará su complejidad de tiempo a su complejidad de espacio (por ejemplo, con tabulación tiene más libertad para descartar cálculos, como usar tabulación con Fib le permite usar O (1) espacio, pero la memoria con Fib usa O (N) stack de espacio).

Optimizaciones avanzadas

Si también está haciendo un problema extremadamente complicado, puede que no tenga más remedio que hacer la tabulación (o al menos asumir un papel más activo al dirigir la memorización hacia donde quiere que vaya). Además, si se encuentra en una situación en la que la optimización es absolutamente crítica y debe optimizarla, la tabulación le permitirá realizar optimizaciones que, de otro modo, la memorización no le permitiría hacer de manera sensata. En mi humilde opinión, en la ingeniería de software normal, ninguno de estos dos casos aparece, así que simplemente usaría memoria (“una función que almacena sus respuestas”) a menos que algo (como espacio de stack) haga que la tabulación sea necesaria … aunque técnicamente para evitar un estallido de stack, puedes 1) boost el límite de tamaño de stack en idiomas que lo permiten, o 2) comer un factor constante de trabajo extra para virtualizar tu stack (ick), o 3) progtwigr en estilo de continuación de paso, que en efecto también virtualiza tu stack (no estoy seguro de la complejidad de esto, pero básicamente tomarás la cadena de llamadas diferida de la stack de tamaño N y la pegarás de facto en N funciones de procesador anidadas sucesivamente … aunque en algunos idiomas) sin la optimización de la llamada de la cola, es posible que tenga que trampolín para evitar una explosión de la stack).


Ejemplos más complicados

Aquí enumeramos ejemplos de particular interés, que no son solo problemas generales de DP, sino que distinguen de forma interesante la memorización y la tabulación. Por ejemplo, una formulación puede ser mucho más fácil que la otra, o puede haber una optimización que básicamente requiere tabulación:

  • el algoritmo para calcular la distancia de edición [ 4 ], interesante como un ejemplo no trivial de un algoritmo bidimensional de llenado de tablas

Los DP de arriba hacia abajo son dos formas diferentes de resolver los mismos problemas. Considere una solución de progtwigción memorable (de arriba hacia abajo) vs dinámica (de abajo hacia arriba) para calcular los números de Fibonacci.

 fib_cache = {} def memo_fib(n): global fib_cache if n == 0 or n == 1: return 1 if n in fib_cache: return fib_cache[n] ret = memo_fib(n - 1) + memo_fib(n - 2) fib_cache[n] = ret return ret def dp_fib(n): partial_answers = [1, 1] while len(partial_answers) <= n: partial_answers.append(partial_answers[-1] + partial_answers[-2]) return partial_answers[n] print memo_fib(5), dp_fib(5) 

Personalmente encuentro la memorización mucho más natural. Puede tomar una función recursiva y memorizarla mediante un proceso mecánico (primera respuesta de búsqueda en caché y devolverla si es posible; de ​​lo contrario, calcúlela recursivamente y luego antes de regresar, guarde el cálculo en el caché para uso futuro), mientras que hace abajo La progtwigción dinámica requiere que codifique un orden en el que se calculan las soluciones, de modo que no se compute un "gran problema" antes del problema menor del que depende.

Una característica clave de la progtwigción dinámica es la presencia de subproblemas superpuestos . Es decir, el problema que está tratando de resolver se puede dividir en subproblemas, y muchos de esos subproblemas comparten subproblemas. Es como “Divide y vencerás”, pero terminas haciendo lo mismo muchas, muchas veces. Un ejemplo que utilicé desde 2003 al enseñar o explicar estos asuntos: puede calcular los números de Fibonacci recursivamente.

 def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) 

Use su idioma favorito e intente ejecutarlo para fib(50) . Tomará mucho, mucho tiempo. ¡Aproximadamente tanto tiempo como fib(50) sí mismo! Sin embargo, se está haciendo mucho trabajo innecesario. fib(50) llamará a fib(49) y fib(48) , pero luego ambos terminarán llamando fib(47) , aunque el valor sea el mismo. De hecho, fib(47) se computará tres veces: por una llamada directa de fib(49) , por una llamada directa de fib(48) , y también por una llamada directa de otra fib(48) , la que fue engendrado por el cálculo de fib(49) ... Así que ya ves, tenemos subproblemas superpuestos .

Una gran noticia: no es necesario calcular el mismo valor muchas veces. Una vez que lo calcule una vez, guarde en caché el resultado, y la próxima vez use el valor en caché. Esta es la esencia de la progtwigción dinámica. Puede llamarlo "de arriba hacia abajo", "memoria" o cualquier otra cosa que desee. Este enfoque es muy intuitivo y muy fácil de implementar. Simplemente, primero escriba una solución recursiva, pruébela en pruebas pequeñas, agregue memorización (almacenamiento en memoria caché de valores ya computados), y --- ¡bingo! --- estás listo.

Por lo general, también puede escribir un progtwig iterativo equivalente que funcione de abajo hacia arriba, sin recurrencia. En este caso, este sería el enfoque más natural: pasar del 1 al 50 computando todos los números de Fibonacci sobre la marcha.

 fib[0] = 0 fib[1] = 1 for i in range(48): fib[i+2] = fib[i] + fib[i+1] 

En cualquier escenario interesante, la solución de abajo hacia arriba suele ser más difícil de entender. Sin embargo, una vez que lo entiendes, generalmente obtendrías una imagen más clara de cómo funciona el algoritmo. En la práctica, al resolver problemas no triviales, recomiendo primero escribir el enfoque descendente y probarlo en pequeños ejemplos. Luego, escriba la solución de abajo hacia arriba y compare los dos para asegurarse de obtener lo mismo. Idealmente, compare las dos soluciones automáticamente. Escriba una pequeña rutina que generaría muchas pruebas, idealmente, todas las pruebas pequeñas hasta cierto tamaño, y valide que ambas soluciones den el mismo resultado. Después de eso, use la solución bottom-up en producción, pero mantenga el código superior-inferior, comentado. Esto hará que sea más fácil para otros desarrolladores entender qué es lo que estás haciendo: el código de abajo hacia arriba puede ser bastante incomprensible, incluso si lo escribes e incluso si sabes exactamente lo que estás haciendo.

En muchas aplicaciones, el enfoque ascendente es un poco más rápido debido a la sobrecarga de llamadas recursivas. El desbordamiento de la stack también puede ser un problema en ciertos problemas, y tenga en cuenta que esto puede depender mucho de los datos de entrada. En algunos casos, es posible que no pueda escribir una prueba que cause un desbordamiento de la stack si no entiende la progtwigción dinámica lo suficientemente bien, pero puede que algún día esto suceda.

Ahora bien, hay problemas en los que el enfoque descendente es la única solución factible porque el espacio problemático es tan grande que no es posible resolver todos los subproblemas. Sin embargo, el "almacenamiento en caché" aún funciona en un tiempo razonable porque su entrada solo necesita una fracción de los subproblemas que se resolverán, pero es demasiado complicado definir explícitamente, qué subproblemas debe resolver y, por lo tanto, escribir un hasta la solución. Por otro lado, hay situaciones en las que sabes que necesitarás resolver todos los subproblemas. En este caso, continúa y usa de abajo hacia arriba.

Yo personalmente usaría top-bottom para optimización de párrafos, también conocido como el problema de optimización de Word wrap (busque los algoritmos Knuth-Plass para romper líneas, al menos TeX lo usa, y algunos progtwigs de Adobe Systems usan un enfoque similar). Usaría de abajo arriba para la Transformada Rápida de Fourier .

Tomemos la serie de Fibonacci como ejemplo

 1,1,2,3,5,8,13,21.... first number: 1 Second number: 1 Third Number: 2 

Otra forma de decirlo,

 Bottom(first) number: 1 Top (Eighth) number on the given sequence: 21 

En caso de los primeros cinco números de Fibonacci

 Bottom(first) number :1 Top (fifth) number: 5 

Ahora echemos un vistazo al algoritmo recursivo de la serie Fibonacci como ejemplo

 public int rcursive(int n) { if ((n == 1) || (n == 2)) { return 1; } else { return rcursive(n - 1) + rcursive(n - 2); } } 

Ahora si ejecutamos este progtwig con los siguientes comandos

 rcursive(5); 

si observamos de cerca el algoritmo, para generar un quinto número, se requieren números 3 y 4. Así que mi recursión en realidad comienza desde la parte superior (5) y luego va hasta los números inferiores / inferiores. Este enfoque es en realidad un enfoque de arriba hacia abajo.

Para evitar hacer el mismo cálculo varias veces, utilizamos técnicas de progtwigción dinámica. Almacenamos valores previamente calculados y los reutilizamos. Esta técnica se llama memorización. Hay más en la progtwigción dinámica aparte de la memorización que no es necesaria para discutir el problema actual.

De arriba hacia abajo

Permite reescribir nuestro algoritmo original y agregar técnicas memoradas.

 public int memoized(int n, int[] memo) { if (n <= 2) { return 1; } else if (memo[n] != -1) { return memo[n]; } else { memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo); } return memo[n]; } 

Y ejecutamos este método como sigue

  int n = 5; int[] memo = new int[n + 1]; Arrays.fill(memo, -1); memoized(n, memo); 

Esta solución sigue siendo de arriba hacia abajo a medida que el algoritmo comienza desde el valor superior e irá al final de cada paso para obtener nuestro máximo valor.

De abajo hacia arriba

Pero, la pregunta es, ¿podemos comenzar desde abajo, como desde el primer número de Fibonacci, luego caminar hacia arriba y hacia arriba. Vamos a reescribirlo usando estas técnicas,

 public int dp(int n) { int[] output = new int[n + 1]; output[1] = 1; output[2] = 1; for (int i = 3; i <= n; i++) { output[i] = output[i - 1] + output[i - 2]; } return output[n]; } 

Ahora bien, si observamos este algoritmo, en realidad comienza desde valores más bajos y luego ve hacia arriba. Si necesito el quinto número de Fibonacci, estoy calculando primero, luego segundo y tercero hasta llegar al quinto número. Estas técnicas en realidad se llaman técnicas ascendentes.

Los dos últimos, los algoritmos completan los requisitos de progtwigción dinámica. Pero uno es de arriba hacia abajo y otro de abajo hacia arriba. Ambos algoritmos tienen una complejidad de espacio y tiempo similar.

¡La progtwigción dinámica a menudo se llama Memoización!

1. La memorización es la técnica de arriba hacia abajo (comienza a resolver el problema dado descomponiéndolo) y la progtwigción dinámica es una técnica de abajo arriba (empieza a resolver desde el sub-problema trivial, hacia el problema dado)

2.DP encuentra la solución comenzando desde el (los) caso (s) base y avanza hacia arriba. DP resuelve todos los sub-problemas, porque lo hace de abajo hacia arriba

A diferencia de Memoization, que resuelve solo los sub-problemas necesarios

  1. DP tiene el potencial de transformar soluciones de fuerza bruta en tiempo exponencial en algoritmos de tiempo polinomial.

  2. DP puede ser mucho más eficiente porque su iterativo

Por el contrario, la Memoization debe pagar los gastos generales (a menudo significativos) debido a la recursión.

Para ser más simple, Memoization usa el enfoque descendente para resolver el problema, es decir, comienza con el problema central (principal) y luego lo divide en subproblemas y resuelve estos subproblemas de manera similar. En este enfoque, el mismo sub-problema puede ocurrir varias veces y consumir más ciclo de CPU, por lo tanto, boost la complejidad del tiempo. Mientras que en la progtwigción dinámica, el mismo sub-problema no se resolverá varias veces, pero el resultado anterior se usará para optimizar la solución.

Simplemente decir el enfoque de arriba hacia abajo usa la recursividad para llamar a los problemas de Sub una y otra vez
donde como enfoque de abajo hacia arriba usa el single sin llamar a nadie y por lo tanto es más eficiente.

A continuación se encuentra la solución basada en DP para el problema de Editar Distancia, que es de arriba hacia abajo. Espero que también ayude a comprender el mundo de la progtwigción dinámica:

 public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle. int m = word2.length(); int n = word1.length(); if(m == 0) // Cannot miss the corner cases ! return n; if(n == 0) return m; int[][] DP = new int[n + 1][m + 1]; for(int j =1 ; j <= m; j++) { DP[0][j] = j; } for(int i =1 ; i <= n; i++) { DP[i][0] = i; } for(int i =1 ; i <= n; i++) { for(int j =1 ; j <= m; j++) { if(word1.charAt(i - 1) == word2.charAt(j - 1)) DP[i][j] = DP[i-1][j-1]; else DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this. } } return DP[n][m]; } 

Puede pensar en su implementación recursiva en su hogar. Es bastante bueno y desafiante si no has resuelto algo como esto antes.