▷¿Cuál es la diferencia entre bottom-up y top-down? ✔️ Foro Ayuda 【 2024 】

Posterior a de una larga recopilación de datos hemos podido resolver este enigma que tienen algunos usuarios. Te ofrecemos la solución y deseamos serte de gran ayuda.

Solución:

rev4: Un comentario muy elocuente del usuario Sammaron ha señalado que, tal vez, esta respuesta anteriormente 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 a la inversa (es decir, “de arriba hacia abajo” puede ser “asumir los subproblemas” y ” de abajo hacia arriba “puede ser” componer los subproblemas “). Anteriormente, leí que la memorización es un tipo diferente de programación dinámica a diferencia de un subtipo de programación dinámica. Estaba citando ese punto de vista a pesar de no suscribirme. He reescrito esta respuesta para ser independiente de la terminología hasta que se puedan encontrar referencias adecuadas en la literatura. También he convertido esta respuesta en una wiki comunitaria. Prefiera fuentes académicas. Lista de referencias: Web: 1,2 Literatura: 5

Resumen

La programación dinámica se trata de ordenar sus cálculos de una manera que evite volver a calcular el trabajo duplicado. Tiene un problema principal (la raíz de su árbol de subproblemas) y subproblemas (subárboles). Los subproblemas suelen repetirse y superponerse.

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

(En algunos otros problemas raros, este árbol podría ser infinito en algunas ramas, lo que representa 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 sepa cómo se ve el árbol completo antes de tiempo. Por lo tanto, es posible que necesite una estrategia / algoritmo para decidir qué subproblemas revelar).

Memorización, tabulación

Hay al menos dos técnicas principales de programación dinámica que no se excluyen mutuamente:

Memorización: este es un enfoque de laissez-faire: usted asume que ya ha calculado todos los subproblemas y que no tiene idea de cuál es el orden de evaluación óptimo. Por lo general, realizaría una llamada recursiva (o algún equivalente iterativo) desde la raíz, y esperaría acercarse al orden de evaluación óptimo u obtener una prueba de que lo ayudará a llegar al orden de evaluación óptimo. Debería asegurarse de que la llamada recursiva nunca vuelva a calcular un subproblema porque cache los resultados y, por lo tanto, los subárboles duplicados no se vuelven a calcular.
- ejemplo: Si está calculando la secuencia de Fibonacci fib(100), solo llamarías a esto, y llamaría fib(100)=fib(99)+fib(98), que llamaría fib(99)=fib(98)+fib(97), … etc …, que llamaría fib(2)=fib(1)+fib(0)=1+0=1. Entonces finalmente se resolvería fib(3)=fib(2)+fib(1), pero no es necesario volver a calcular fib(2), porque lo almacenamos en caché.
- Esto comienza en la parte superior del árbol y evalúa los subproblemas desde 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ía no euclidiana en casos muy raros *). Esto es como la memorización, pero más activo e implica un paso adicional: debe elegir, con anticipación, el orden exacto en el que hará sus cálculos. Esto no debería implicar que el pedido deba ser estático, sino que tiene mucha más flexibilidad que la memorización.
- ejemplo: Si está realizando fibonacci, puede optar por calcular los números en este orden: fib(2),fib(3),fib(4)… almacenando en caché cada valor para que pueda calcular los siguientes más fácilmente. También puede considerarlo como 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 el árbol completo, luego escribe un algoritmo para evaluar los subproblemas en un orden particular hacia la raíz, generalmente llenando una tabla.
- * nota al pie: A veces, la ‘mesa’ no es una mesa rectangular con conectividad en forma de cuadrícula, per se. Más bien, puede tener una estructura más complicada, como un árbol, o una estructura específica para el dominio del problema (por ejemplo, ciudades dentro de la distancia de vuelo en un mapa), o incluso un diagrama de enrejado, que, aunque tiene forma de cuadrícula, no tiene una estructura de conectividad arriba-abajo-izquierda-derecha, etc. Por ejemplo, user3290797 vinculó un ejemplo de programación dinámica para encontrar el conjunto máximo independiente en un árbol, que corresponde a completar los espacios en blanco en un árbol.

(En su forma más general, en un paradigma de “programación dinámica”, diría que el programador considera el árbol completo, luego escribe un algoritmo que implementa una estrategia para evaluar subproblemas que puede optimizar las propiedades que desee (generalmente una combinación de complejidad temporal y complejidad espacial). Su estrategia debe comenzar en algún lugar, con algún subproblema en particular, y tal vez pueda adaptarse en función de los resultados de esas evaluaciones. En el sentido general de “programación dinámica”, puede intentar almacenar en caché estos subproblemas y, de manera más general, tratar de evitar volver a visitar los subproblemas con una sutil distinción que tal vez sea el caso de gráficos en varias estructuras de datos. Muy a menudo, estas estructuras de datos se encuentran en su núcleo, como matrices o tablas. Las soluciones a los subproblemas se pueden desechar si ya no las necesitamos).

[Previously, this answer made a statement about the top-down vs bottom-up terminology; there are clearly two main approaches called Memoization and Tabulation that may be in bijection with those terms (though not entirely). The general term most people use is still “Dynamic Programming” and some people say “Memoization” to refer to that particular subtype of “Dynamic Programming.” This answer declines to say which is top-down and bottom-up until the community can find proper references in academic papers. Ultimately, it is important to understand the distinction rather than the terminology.]

Pros y contras

Facilidad de codificación

La memorización es muy fácil de codificar (generalmente puede * escribir una anotación “memorizadora” o una función de envoltura 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 tienes que hacer un pedido.

* (en realidad, esto solo es fácil si está escribiendo la función usted mismo y / o codificando en un lenguaje de programación impuro / no funcional … por ejemplo, si alguien ya escribió un precompilado fib función, necesariamente hace llamadas recursivas a sí mismo, y no puede memorizar mágicamente la función sin asegurarse de que esas llamadas recursivas llamen a su nueva función memorizada (y no a la función original no memorizada))

Recursividad

Tenga en cuenta que tanto de arriba hacia abajo como de abajo hacia arriba se pueden implementar con recursividad o relleno de tabla iterativo, aunque puede que no sea natural.

Preocupaciones practicas

Con memorización, si el árbol es muy profundo (p. Ej. fib(10^6)), se quedará sin espacio de pila, porque cada cálculo retrasado 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 el que sucede (o intenta) visitar los subproblemas no es óptimo, específicamente si hay más de una forma de calcular un subproblema (normalmente el almacenamiento en 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á complejidad de tiempo a la complejidad de su espacio (por ejemplo, con la tabulación tiene más libertad para desechar los cálculos, como usar la tabulación con Fib le permite usar el espacio O (1), pero la memorización con Fib usa O (N) espacio de pila).

Optimizaciones avanzadas

Si también está haciendo un problema extremadamente complicado, es posible que no tenga más remedio que hacer una tabulación (o al menos tomar un papel más activo en la dirección de la memorización hacia donde desea que vaya). Además, si se encuentra en una situación en la que la optimización es absolutamente crítica y debe optimizar, la tabulación le permitirá realizar optimizaciones que, de otro modo, la memorización no le permitiría hacer de una manera sensata. En mi humilde opinión, en la ingeniería de software normal, ninguno de estos dos casos aparece, por lo que solo usaría la memorización (“una función que almacena en caché sus respuestas”) a menos que algo (como el espacio de la pila) haga que la tabulación sea necesaria … aunque técnicamente, para evitar una explosión de la pila, puede 1) aumentar el límite de tamaño de la pila en los idiomas que lo permitan, o 2) consumir un factor constante de trabajo adicional para virtualizar su pila (ick), o 3) programar en estilo de paso de continuación, que en efecto, también virtualiza su pila (no estoy seguro de la complejidad de esto, pero básicamente tomará efectivamente la cadena de llamadas diferidas de la pila de tamaño N y de facto la pegará en N funciones de procesador anidadas sucesivamente … aunque en algunos idiomas sin optimización de la llamada de cola, es posible que tenga que trampolinar las cosas 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 PD, sino que distinguen de manera 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 de llenado de tablas bidimensional

El DP de arriba hacia abajo y de abajo hacia arriba son dos formas diferentes de resolver los mismos problemas. Considere una solución de programación memorizada (de arriba hacia abajo) versus 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 (primero busque la respuesta en la caché y devuélvala si es posible, de lo contrario, calcúlela de forma recursiva y luego, antes de regresar, guarde el cálculo en la caché para uso futuro), mientras que lo hace de abajo hacia arriba La programación dinámica requiere que codifique un orden en el que se calculan las soluciones, de modo que no se calcule ningún "gran problema" antes que el problema más pequeño del que depende.

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 he usado desde 2003 al enseñar o explicar estos asuntos: puede calcular números de Fibonacci de forma recursiva.

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Utilice su idioma favorito e intente ejecutarlo fib(50). Tardará muchísimo tiempo. Aproximadamente tanto tiempo como fib(50) ¡sí mismo! Sin embargo, se está haciendo mucho trabajo innecesario. fib(50) llamará fib(49) y fib(48), pero luego ambos terminarán llamando fib(47), aunque el valor sea el mismo. De hecho, fib(47) se calculará tres veces: mediante una llamada directa desde fib(49), por una llamada directa desde fib(48), y también por una llamada directa de otro fib(48), el que fue generado por el cálculo de fib(49)... así que ya ves, tenemos subproblemas superpuestos.

Buenas noticias: no es necesario calcular el mismo valor muchas veces. Una vez que lo calcule una vez, almacene en caché el resultado, y la próxima vez use el valor en caché! Ésta es la esencia de la programación dinámica. Puede llamarlo "de arriba hacia abajo", "memorización" o cualquier otra cosa que desee. Este enfoque es muy intuitivo y muy fácil de implementar. Simplemente escriba una solución recursiva primero, pruébela en pequeñas pruebas, agregue memorización (almacenamiento en caché de valores ya calculados) y --- ¡bingo! --- estás listo.

Por lo general, también puede escribir un programa iterativo equivalente que funcione de abajo hacia arriba, sin recursividad. En este caso, este sería el enfoque más natural: bucle de 1 a 50 calculando 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 ascendente suele ser más difícil de entender. Sin embargo, una vez que lo entiendas, normalmente obtendrás una imagen mucho más clara de cómo funciona el algoritmo. En la práctica, al resolver problemas no triviales, recomiendo escribir primero el enfoque de arriba hacia abajo y probarlo en pequeños ejemplos. Luego, escriba la solución de abajo hacia arriba y compare las dos para asegurarse de obtener lo mismo. Idealmente, compare las dos soluciones automáticamente. Escriba una pequeña rutina que genere muchas pruebas, idealmente: todos pequeñas pruebas hasta cierto tamaño --- y validar que ambas soluciones dan el mismo resultado. Después de eso, use la solución de abajo hacia arriba en producción, pero mantenga el código de arriba hacia abajo, comentó. 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 tú lo escribiste 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 las llamadas recursivas. El desbordamiento de pila también puede ser un problema en ciertos problemas, y tenga en cuenta que esto puede depender en gran medida 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 comprende la programación dinámica lo suficientemente bien, pero algún día esto aún puede suceder.

Ahora bien, hay problemas en los que el enfoque de arriba hacia abajo es la única solución factible porque el espacio del problema es tan grande que no es posible resolver todos los subproblemas. Sin embargo, el "almacenamiento en caché" todavía funciona en un tiempo razonable porque su entrada solo necesita una fracción de los subproblemas para ser resueltos, pero es demasiado complicado definir explícitamente qué subproblemas necesita resolver y, por lo tanto, escribir un fondo. solución. Por otro lado, hay situaciones en las que sabe que tendrá que resolver todos subproblemas. En este caso, continúe y use de abajo hacia arriba.

Personalmente, usaría de arriba a abajo para la optimización de párrafos, también conocido como el problema de optimización de ajuste de Word (busque los algoritmos de salto de línea de Knuth-Plass; al menos TeX lo usa, y algunos programas de Adobe Systems usan un enfoque similar). Usaría de abajo hacia arriba para la Transformada Rápida de Fourier.

Si sostienes algún escollo o disposición de reformar nuestro noticia eres capaz de realizar una crítica y con mucho gusto lo estudiaremos.

¡Haz clic para puntuar esta entrada!

(Votos: 0 Promedio: 0)

¿Cuál es la diferencia entre bottom-up y top-down?