algorithm - qué - Programación dinámica y memorización: enfoques ascendentes frente a descendentes

metodo de estimacion descendente

Question

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?

Answer 1

rev4: un comentario muy elocuente del usuario Sammaron ha notado que tal vez esta respuesta anteriormente se confundía 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 "). Anteriormente, he leído que la memorización es un tipo diferente de programación dinámica, en oposición a un subtipo de programación dinámica, por lo que fue citar eso a pesar de no suscribirse a ese punto de vista. He reescrito esta respuesta para ser un agnóstico de la terminología hasta que se encuentren las referencias adecuadas en la literatura, y convertí esta respuesta a una wiki comunitaria. Por favor, prefiere fuentes académicas. Lista de referencias: {Web: 1 , 2 } {Literatura: -}

Resumen

La programació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 ramas, 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 tiempo, y por lo tanto puede necesitar una estrategia / algoritmo para decidir qué subproblemas revelar).

Memoización, Tabulación

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

• Memoización: este es un enfoque de laissez-faire: supone que ya ha calculado todos los subproblemas. No tienes idea del orden de evaluación óptimo. Por lo general, realiza una llamada recursiva (o algún equivalente iterativo) desde la raíz, y o bien espera acercarse al orden de evaluación óptimo, o tiene una prueba de que obtendrá el orden de evaluación óptimo. Se asegura 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 programació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, exactamente en qué orden hará sus cálculos (esto no implica que el orden debe ser estático, pero que tiene mucha más flexibilidad que la memorización).

  • ejemplo: si haces fibonacci, eliges calcular los números en este orden: fib(2) , fib(3) , fib(4) ... almacenando en caché cada valor para que puedas 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 "programación dinámica".
  • Antes de ejecutar el algoritmo, el programador 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: a veces la ''tabla'' no es una tabla rectangular con conectividad en forma de grillas per se, sino que puede tener una estructura más complicada, como: un árbol o una estructura específica del dominio problemático (p. ej. en un mapa), o un diagrama enrejado (que a la vez que la estructura de conectividad no es arriba-abajo-izquierda-derecha), etc. Por ejemplo, user3290797 enlazó un ejemplo de programación dinámica para encontrar el conjunto independiente máximo en un árbol , que corresponde a llenar los espacios en blanco en un árbol.

(En su aspecto más general, en "programación dinámica" diría que el programador considera todo el árbol, luego escribe un algoritmo que implementa una estrategia para evaluar los subproblemas (que optimiza las propiedades que desee, generalmente una combinación de tiempo-complejidad y espacio- complejidad). La estrategia debe comenzar en alguna parte, un subproblema particular, y tal vez se adapte a sí misma en función de los resultados de esas evaluaciones. En "programación dinámica" en el sentido más general, generalmente intenta almacenar estos subproblemas (y más generalmente, también evitar revisión de subproblemas ... una distinción sutil quizás en 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 desecharse si ya no las necesitamos. )

[Anteriormente, esta respuesta hacía una declaración 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 "Programación dinámica" y algunas personas dicen "Memoización" para referirse a ese subtipo particular de programació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 codificación

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 programación impuro / no funcional ... por ejemplo, si alguien ya escribió una función fib precompilada, 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 pila, porque cada cómputo demorado debe colocarse en la pila, 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) pila 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 pila) haga que la tabulación sea necesaria ... aunque técnicamente para evitar un estallido de pila, puedes 1) aumentar el límite de tamaño de pila en idiomas que lo permiten, o 2) comer un factor constante de trabajo extra para virtualizar tu stack (ick), o 3) programar en estilo de continuación de paso, que en efecto también virtualiza tu pila (no estoy seguro de la complejidad de esto, pero básicamente tomarás la cadena de llamadas diferida de la pila 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 pila).

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

Answer 2

¡La programació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 programació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, aumentar la complejidad del tiempo. Mientras que en la programación dinámica, el mismo sub-problema no se resolverá varias veces, pero el resultado anterior se usará para optimizar la solución.

Answer 3

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 programació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.

Answer 4

Los DP de arriba hacia abajo son dos formas diferentes de resolver los mismos problemas. Considere una solución de programació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 programació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.

Answer 5

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.

Answer 6

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 programa 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 programación dinámica. Almacenamos valores previamente calculados y los reutilizamos. Esta técnica se llama memorización. Hay más en la programació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 programació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.

Answer 7

Una característica clave de la programació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 programació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 programa 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 pila 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 pila si no entiende la programació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 programas de Adobe Systems usan un enfoque similar). Usaría de abajo arriba para la Transformada Rápida de Fourier .