¿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 versus memorización versus tabulación
¿Cuál es la diferencia entre memorización y programación dinámica?
Memorización es un término que describe una técnica de optimización en la que se almacenan en caché los resultados calculados previamente y se 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 memorización. Como puede ver, ninguno es un "subconjunto" del otro.
Una pregunta de seguimiento razonable es: ¿ Cuál es la diferencia entre tabulación (la técnica típica de programación dinámica) y memorización?
Cuando resuelves un problema de programación dinámica usando tabulación, resuelves el problema " de abajo hacia arriba ", es decir, resolviendo primero todos los subproblemas relacionados, generalmente llenando una tabla de n dimensiones. Con base en los resultados de la tabla, se calcula la solución al problema "superior"/original.
Si utiliza la memorización para resolver el problema, lo hace manteniendo un mapa de subproblemas ya resueltos. Lo hace " de arriba hacia abajo " en el sentido de que resuelve primero el problema "superior" (que normalmente se repite hacia abajo para resolver los subproblemas).
Una buena diapositiva desde aquí (el enlace ya no está disponible, 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 descendente por un factor constante.
- Sin gastos generales por recursividad y menos gastos generales por mantener la tabla
- Hay 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 memorizada tiene la ventaja de resolver solo aquellos subproblemas que definitivamente se requieren.
Recursos adicionales:
- Wikipedia: memorización , programación dinámica
- Preguntas y respuestas relacionadas con SO: Enfoque de memorización o tabulación para programación dinámica
La programación dinámica es un paradigma algorítmico que resuelve un problema complejo determinado dividiéndolo en subproblemas y almacena los resultados de los 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 realizar un seguimiento de soluciones resueltas previamente (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 vuelvan a encontrar. Se puede utilizar tanto en métodos ascendentes como descendentes.
Vea esta discusión sobre memorización versus tabulación.
Entonces, la programación dinámica es un método para resolver ciertas clases de problemas resolviendo relaciones de recurrencia/recursividad y almacenando 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 previamente resueltos y se puede utilizar con cualquier función que tenga soluciones deterministas únicas para un conjunto determinado de entradas.
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 dirección opuesta resolviendo el problema de abajo hacia arriba.
A continuación se muestra una analogía interesante:
De arriba hacia abajo : primero dices que me apoderaré del mundo. ¿Cómo lo harás? Dices que primero me haré cargo de Asia. ¿Cómo lo harás? Primero me haré cargo de la India. Me convertiré en el Ministro Principal de Delhi, etc., etc.
De abajo hacia arriba : dices que me convertiré en el CM de Delhi. Luego me apoderaré de la India, luego de todos los demás países de Asia y finalmente me apoderaré del mundo.
