¿Cuál es la diferencia entre memorización y programación dinámica?

¿Cuál es la diferencia entre memorización y programación dinámica? Creo que la programación dinámica es un subconjunto de la memorización. ¿Es correcto?

Artículo relevante sobre programación. Guía : programación dinámica vs memorización vs tabulación

¿Cuál es la diferencia entre la memorización y la programación dinámica?

Memoization es un término que describe una técnica de optimización en la que almacena en caché los resultados calculados previamente y devuelve el resultado almacenado en caché cuando se necesita nuevamente el mismo cálculo.

La programación dinámica es una técnica para resolver problemas de naturaleza recursiva, de forma iterativa, y es aplicable cuando los cálculos de los subproblemas se superponen.

La programación dinámica generalmente se implementa mediante tabulación, pero también se puede implementar mediante la memorización. Como puede ver, ninguno de los dos es un "subconjunto" del otro.

Una pregunta de seguimiento razonable es: ¿Cuál es la diferencia entre la tabulación (la técnica de programación dinámica típica) y la memorización?

Cuando resuelve un problema de programación dinámica utilizando la tabulación, resuelve el problema "de abajo hacia arriba ", es decir, resolviendo primero todos los subproblemas relacionados, normalmente llenando una tabla n- dimensional. Según los resultados de la tabla, se calcula la solución del problema "superior" / original.

Si usa la memorización para resolver el problema, hágalo manteniendo un mapa de subproblemas ya resueltos. Lo haces "de arriba hacia abajo " en el sentido de que primero resuelves el problema de "arriba" (que generalmente recurre para resolver los subproblemas).

Una buena diapositiva desde aquí (el enlace ahora está muerto, aunque la diapositiva sigue siendo buena):

• Si todos los subproblemas deben resolverse al menos una vez, un algoritmo de programación dinámica ascendente generalmente supera a un algoritmo memorizado de arriba a abajo en un factor constante
  • Sin gastos generales para la recursividad y menos gastos generales para mantener la tabla
  • Hay algunos problemas para los cuales se puede explotar el patrón regular de acceso a la tabla en el algoritmo de programación dinámica para reducir aún más los requisitos de tiempo o espacio
• Si algunos subproblemas en el espacio de subproblemas no necesitan resolverse en absoluto, la solución memorizada tiene la ventaja de resolver solo aquellos subproblemas que definitivamente se requieren

Recursos adicionales:

• Wikipedia: Memoization , programación dinámica
• P / R SO relacionado: enfoque de memorización o tabulación para la programación dinámica

La programación dinámica es un paradigma algorítmico que resuelve un problema complejo dado dividiéndolo en subproblemas y almacena los resultados de los subproblemas para evitar calcular nuevamente los mismos resultados.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

La memorización es un método fácil para rastrear soluciones previamente resueltas (a menudo implementadas como un par de valores de clave hash, a diferencia de la tabulación que a menudo se basa en matrices) para que no se vuelvan a calcular cuando se encuentren nuevamente. Se puede usar en ambos métodos, de abajo hacia arriba o de arriba hacia abajo.

Vea esta discusión sobre memorización vs tabulación.

Por lo tanto, la programación dinámica es un método para resolver ciertas clases de problemas mediante la resolución de las relaciones de recurrencia / recursividad y el almacenamiento de soluciones encontradas previamente mediante tabulación o memorización. La memorización es un método para realizar un seguimiento de las soluciones a problemas resueltos previamente y se puede usar con cualquier función que tenga soluciones deterministas únicas para un conjunto dado de entradas.

¡La programación dinámica a menudo se llama memorización!

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

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

   A diferencia de Memoization, que resuelve solo los subproblemas necesarios

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

4. DP puede ser mucho más eficiente porque es iterativo

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

Para ser más simple, Memoization utiliza el enfoque de arriba hacia abajo para resolver el problema, es decir, comienza con el problema central (principal), luego lo divide en subproblemas y resuelve estos subproblemas de manera similar. En este enfoque, el mismo subproblema puede ocurrir varias veces y consumir más ciclos de CPU, por lo tanto, aumentar la complejidad del tiempo. Mientras que en la programación dinámica, el mismo subproblema no se resolverá varias veces, pero el resultado anterior se utilizará para optimizar la solución.

(1) Memoization y DP, conceptualmente , es realmente lo mismo. Porque: considere la definición de DP: "subproblemas superpuestos" y "subestructura óptima". Memoization posee completamente estos 2.

(2) La memorización es DP con el riesgo de desbordamiento de pila si la recursividad es profunda. DP de abajo hacia arriba no tiene este riesgo.

(3) Memoization necesita una tabla hash. Por lo tanto, espacio adicional y algo de tiempo de búsqueda.

Entonces para responder la pregunta:

- Conceptualmente , (1) significa que son lo mismo.

-Tomando en cuenta (2), si realmente quieres, la memorización es un subconjunto de DP, en el sentido de que un problema solucionable por la memorización será solucionado por DP, pero un problema solucionable por DP podría no ser solucionable por la memorización (porque podría apilarse desbordamiento).

-Tomando en cuenta (3), tienen diferencias menores en el rendimiento.

De wikipedia:

Memorización

En informática, la memorización es una técnica de optimización utilizada principalmente para acelerar los programas de computadora al hacer que las llamadas a funciones eviten repetir el cálculo de resultados para entradas procesadas previamente.

Programación dinámica

En matemáticas y ciencias de la computación, la programación dinámica es un método para resolver problemas complejos dividiéndolos en subproblemas más simples.

Al dividir un problema en subproblemas más pequeños / simples, a menudo nos encontramos con el mismo subproblema más de una vez, por lo que usamos Memoization para guardar los resultados de cálculos anteriores para que no necesitemos repetirlos.

La programación dinámica a menudo encuentra situaciones en las que tiene sentido usar la memorización, pero puede usar cualquiera de las técnicas sin necesariamente usar la otra.

Tanto la memorización como la programación dinámica resuelven subproblemas individuales solo una vez.

La memorización utiliza la recursividad y funciona de arriba hacia abajo, mientras que la programación dinámica se mueve en la dirección opuesta resolviendo el problema de abajo hacia arriba.

A continuación hay una analogía interesante:

De arriba hacia abajo : primero dices que me haré cargo del mundo. ¿Cómo lo harás? Dices que primero me haré cargo de Asia. ¿Cómo lo harás? Tomaré la India primero. Me convertiré en el Ministro Principal de Delhi, etc., etc.

De abajo hacia arriba : dices que me convertiré en el CM de Delhi. Luego tomaré el control de la India, luego todos los demás países de Asia y finalmente tomaré el control del mundo.

Me gustaría ir con un ejemplo ;

Problema:

Estás subiendo una escalera. Se necesitan n pasos para llegar a la cima.

Cada vez puedes subir 1 o 2 escalones. ¿De cuántas maneras distintas puedes subir a la cima?

Recursión con la memorización

De esta manera, estamos podando (la eliminación del exceso de material de un árbol o arbusto) el árbol de recursión con la ayuda de una matriz de notas y reduciendo el tamaño del árbol de recursión hasta ahora.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Programación dinámica

Como podemos ver, este problema se puede dividir en subproblemas, y contiene la propiedad de subestructura óptima, es decir, su solución óptima se puede construir de manera eficiente a partir de soluciones óptimas de sus subproblemas, podemos utilizar la programación dinámica para resolver este problema.

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

Ejemplos tomados de https://leetcode.com/problems/climbing-stairs/

Solo piensa en dos formas,

1. Desglosamos el problema más grande en subproblemas más pequeños: enfoque de arriba hacia abajo.
2. Comenzamos desde el subproblema más pequeño y llegamos al problema más grande: enfoque ascendente.

En Memoization vamos con (1.) donde guardamos cada llamada de función en un caché y llamamos desde allí. Es un poco caro ya que implica llamadas recursivas.

En la programación dinámica vamos con (2.) donde mantenemos una tabla, de abajo hacia arriba resolviendo subproblemas utilizando los datos guardados en la tabla, comúnmente conocida como la tabla dp.

Nota:

• Ambos son aplicables a problemas con subproblemas superpuestos.

• Memoization realiza comparativamente pobre para DP debido a los gastos generales involucrados durante las llamadas a funciones recursivas.

• La complejidad temporal asintótica sigue siendo la misma.

En programación dinámica ,

• Sin gastos generales para la recursividad, menos gastos generales para mantener la tabla.
• El patrón regular de los accesos a la tabla puede usarse para reducir los requisitos de tiempo o espacio.

En memorización ,

• Algunos subproblemas no necesitan ser resueltos.