terminology - programacion - ¿Cuál es la diferencia entre la memorización y la programación dinámica?
programacion dinamica java (5)
Creo que la programación dinámica es un subconjunto de la memorización. ¿Es correcto?
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 subproblemas para evitar volver a calcular los mismos resultados.
http://www.geeksforgeeks.org/dynamic-programming-set-1/
La memorización es un método sencillo para rastrear soluciones resueltas previamente (a menudo implementadas como un par de valores de clave hash, en oposición a la tabulación que a menudo se basa en matrices) para que no se vuelvan a calcular cuando se vuelvan a encontrar. Se puede usar tanto en métodos de abajo arriba como de arriba hacia abajo.
Vea esta discusión sobre la tabulación de memorización vs.
Método de memoración o tabulación para la programación dinámica
Así que la programación dinámica es un método para resolver ciertas clases de problemas mediante la resolución de relaciones recurrentes / recursión y el almacenamiento de soluciones encontradas anteriormente a través de la tabulación o la 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 determinísticas únicas para un conjunto dado de entradas.
¿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 se almacenan en caché los resultados previamente calculados y se devuelve el resultado en caché cuando se necesita el mismo cálculo nuevamente.
La programación dinámica es una técnica para resolver problemas recursivamente y es aplicable cuando los cálculos de los subproblemas se superponen.
La programación dinámica se implementa típicamente usando la tabulación, pero también se puede implementar mediante la memorización. Como puede ver, ninguno 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 usando la tabulación, resuelve el problema "de abajo hacia arriba ", es decir, resolviendo todos los sub-problemas relacionados primero, típicamente llenando una tabla n- dimensional. En función de los resultados de la tabla, se calcula la solución al problema "superior" / original.
Si usa la memorización para resolver el problema, lo hace manteniendo un mapa de problemas secundarios ya resueltos. Lo haces "de arriba hacia abajo " en el sentido de que resuelves primero el problema "superior" (que generalmente se repite para resolver los sub-problemas).
Una buena diapositiva desde here (el enlace está ahora muerto, la diapositiva aún está bien):
- Si todos los subproblemas se deben resolver al menos una vez, un algoritmo de programación dinámica ascendente generalmente supera un algoritmo memorable de arriba hacia abajo por un factor constante
- Sin gastos generales para la recursividad y menos gastos generales para mantener la tabla
- Existen algunos problemas para los cuales se puede aprovechar el patrón regular de acceso a tablas 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 memorada tiene la ventaja de resolver solo aquellos subproblemas que son definitivamente necesarios
Recursos adicionales:
- Wikipedia: Memoization , programación dinámica
- Relacionado SO Q / A: enfoque de Memoization o Tabulación para programación dinámica
Esto ha sido reescrito como un artículo aquí .
¡La programación dinámica a menudo se llama Memoización!
La memorización es la técnica de arriba hacia abajo (empieza 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)
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
DP tiene el potencial de transformar soluciones de fuerza bruta en tiempo exponencial en algoritmos de tiempo polinomial.
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.
(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 recursión es profunda. DP bottom up no tiene este riesgo.
(3) La memorización necesita una tabla hash. Por lo tanto, espacio adicional y un tiempo de búsqueda.
Entonces para responder la pregunta:
- Conceptualmente , (1) significa que son la misma cosa.
- Tomando en cuenta (2), si realmente lo desea, la memorización es un subconjunto de DP, en el sentido de que un problema solucionable mediante memorando será solucionable por DP, pero un problema solucionable por DP podría no resolverse mediante la memorización (porque podría acumular desbordamiento).
-Taking (3) en cuenta, tienen pequeñas diferencias en el rendimiento.
De la wikipedia:
Memoization
En informática, la memorización es una técnica de optimización que se utiliza principalmente para acelerar los programas de computadora haciendo que las llamadas a funciones eviten repetir el cálculo de los resultados de las entradas procesadas previamente.
Programación dinámica
En matemáticas e informática, 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 / más simples, a menudo encontramos el mismo subproblema más de una vez, por lo que usamos la Memoización para guardar los resultados de los cálculos anteriores para que no tengamos que repetirlos.
La programación dinámica a menudo encuentra situaciones en las que tiene sentido utilizar la memorización, pero puede usar cualquiera de las dos técnicas sin usar necesariamente la otra.