El enfoque "de abajo arriba" (de la programación dinámica) consiste en examinar primero los subproblemas "más pequeños" y, a continuación, resolver los subproblemas más grandes a partir de la solución de los problemas más pequeños.
El enfoque top-down consiste en resolver el problema de forma "natural" y comprobar si se ha calculado antes la solución del subproblema.
Estoy un poco confuso. ¿Cuál es la diferencia entre estos dos métodos?
rev4: Un comentario muy elocuente por el usuario Sammaron ha señalado que, tal vez, esta respuesta previamente confundido de arriba hacia abajo y de abajo hacia arriba. Aunque originalmente esta respuesta (rev3) y otras respuestas decían que "bottom-up es memoization" ("asumir los subproblemas"), puede ser a la inversa (es decir, "top-down" puede ser "asumir los subproblemas" y "bottom-up" puede ser "componer los subproblemas"). Anteriormente, he leído en memoization ser un tipo diferente de programación dinámica en contraposición a un subtipo de programación dinámica. Citaba ese punto de vista a pesar de no suscribirlo. He reescrito esta respuesta para ser agnóstico de la terminología hasta que las referencias adecuadas se pueden encontrar en la literatura. También he convertido esta respuesta a una wiki comunitaria. Por favor, prefiera fuentes académicas. Lista de referencias: {Web: 1,2} {Literatura: 5}
Recapitulación
La programación dinámica consiste en ordenar los cálculos de forma que se evite recalcular el trabajo duplicado. Tienes un problema principal (la raíz de tu árbol de subproblemas), y subproblemas (subárboles). Los subproblemas suelen repetirse y solaparse. Por ejemplo, considere su ejemplo favorito de Fibonnaci. Este es el árbol completo de subproblemas, si hiciéramos una llamada recursiva ingenua:
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
Hay al menos dos técnicas principales de programación dinámica que no son mutuamente excluyentes:
fib(100)
, simplemente llamarías a esto, y llamaría a fib(100)=fib(99)+fib(98)
, que llamaría a fib(99)=fib(98)+fib(97)
, ...etc..., que llamaría 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 hemos almacenado en caché.fib(2)
,fib(3)
,fib(4)
... almacenando en caché cada valor para que puedas calcular los siguientes más fácilmente. También puedes pensar en ello como llenar una tabla (otra forma de caché).La memoización es muy fácil de codificar (generalmente se puede escribir una anotación "memoizer" o una función envoltorio que lo haga automáticamente por usted), y debería ser su primera línea de enfoque. La desventaja de la tabulación es que usted tiene que venir para arriba con un ordenamiento.
Por ejemplo, si alguien ya escribió una función fib
precompilada, necesariamente hace llamadas recursivas a sí misma, y usted no puede mágicamente memoizar la función sin asegurarse de que esas llamadas recursivas llamen a su nueva función memoizada (y no a la función original no memoizada).
Nótese que tanto top-down como bottom-up pueden implementarse con recursividad o rellenado iterativo de tablas, aunque puede no ser natural.
Con memoización, si el árbol es muy profundo (por ejemplo fib(10^6)
), te quedarás sin espacio en la pila, porque cada cálculo retrasado debe ser puesto en la pila, y tendrás 10^6 de ellos.
Cualquiera de los dos enfoques puede no ser óptimo en tiempo si el orden en el que visitas (o intentas visitar) los subproblemas no es óptimo, específicamente si hay más de una forma de calcular un subproblema (normalmente la memorización resolvería esto, pero es teóricamente posible que la memorización no lo haga en algunos casos exóticos). Memoization por lo general se sumará a su tiempo-complejidad a su espacio-complejidad (por ejemplo, con la tabulación tiene más libertad para desechar los cálculos, como el uso de la tabulación con Fib le permite utilizar O (1) de espacio, pero memoization con Fib utiliza O (N) de espacio de pila).
Aquí enumeramos ejemplos de interés particular, que no son sólo problemas generales de AD, sino que distinguen de forma interesante entre memoización y 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 requiera tabulación:
La PD descendente y ascendente son dos formas distintas de resolver los mismos problemas. Consideremos una solución de programación memoizada (descendente) frente a una dinámica (ascendente) para calcular los números de Fibonacci.
lenguaje-todo: py -->
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 memoización mucho más natural. Puedes tomar una función recursiva y memoizarla mediante un proceso mecánico (primero buscar la respuesta en la caché y devolverla si es posible, si no, calcularla recursivamente y luego, antes de devolver, guardar el cálculo en la caché para uso futuro), mientras que hacer programación dinámica ascendente requiere que codifiques un orden en el que se calculan las soluciones, de forma que ningún "gran problema" se calcule antes que el problema más pequeño del que depende.
La Programación Dinámica suele denominarse Memoización.
1.Memoization es la técnica de arriba hacia abajo (empezar a resolver el problema dado por su descomposición) y la programación dinámica es una técnica de abajo hacia arriba (empezar a resolver desde el sub-problema trivial, hacia el problema dado)
2.La PD encuentra la solución partiendo del caso o casos base y va ascendiendo. La PD resuelve todos los subproblemas porque lo hace de abajo arriba.
A diferencia de la Memoización, que sólo resuelve los subproblemas necesarios.
DP tiene el potencial de transformar las soluciones de fuerza bruta de tiempo exponencial en algoritmos de tiempo polinómico.
DP puede ser mucho más eficiente porque sus algoritmos iterativos
Por el contrario, la Memoización debe pagar por la sobrecarga (a menudo significativa) debida a la recursividad.
Para ser más simple, Memoization utiliza el enfoque de arriba hacia abajo para resolver el problema, es decir, comienza con el núcleo (principal) del problema y luego lo divide en sub-problemas y resuelve estos sub-problemas de manera similar. En este enfoque, el mismo subproblema puede aparecer varias veces y consumir más ciclos de CPU, lo que aumenta la complejidad temporal. Mientras que en la programación dinámica, el mismo subproblema no se resolverá varias veces, sino que se utilizará el resultado anterior para optimizar la solución.