¿Cuándo puedo usar la programación dinámica para reducir la complejidad temporal de mi algoritmo recursivo?

13

La programación dinámica puede reducir el tiempo necesario para realizar un algoritmo recursivo. Sé que la programación dinámica puede ayudar a reducir la complejidad temporal de los algoritmos. ¿Las condiciones generales son tales que si un algoritmo recursivo lo satisface implicaría que el uso de la programación dinámica reducirá la complejidad temporal del algoritmo? ¿Cuándo debo usar la programación dinámica?

Anónimo
fuente

Respuestas:

9

La programación dinámica es útil si su algoritmo recursivo se encuentra llegando a las mismas situaciones (parámetros de entrada) muchas veces. Hay una transformación general de algoritmos recursivos a programación dinámica conocida como memorización , en la que hay una tabla que almacena todos los resultados calculados por su procedimiento recursivo. Cuando se llama al procedimiento recursivo en un conjunto de entradas que ya se utilizaron, los resultados se obtienen de la tabla. Esto reduce el Fibonacci recursivo a Fibonacci iterativo.

La programación dinámica puede ser aún más inteligente, aplicando optimizaciones más específicas. Por ejemplo, a veces no es necesario almacenar toda la tabla en la memoria en un momento dado.

Yuval Filmus
fuente
El contador sería entonces que cada vez que la complejidad espacial de la memorización sea mayor que los datos de entrada (quizás solo> O (N)), es probable que la programación dinámica no ayude. Es decir, cuando con poca frecuencia te encuentras con la misma situación.
edA-qa mort-ora-y
1
Memoisation! = Programación dinámica!
Raphael
1
No creo que estemos diciendo eso, pero la pregunta indica la reducción de la complejidad del tiempo. La programación dinámica por sí sola simplemente divide el problema. La programación dinámica + la memorización es una forma genérica de mejorar la complejidad del tiempo siempre que sea posible .
edA-qa mort-ora-y
@ edA-qamort-ora-y: Correcto. Creo que es importante señalarlo claramente, ya que aparentemente el OP confunde / mezcla los conceptos.
Raphael
8

Si solo busca acelerar su algoritmo recursivo, la memorización podría ser suficiente. Esta es la técnica de almacenar resultados de llamadas a funciones para que las llamadas futuras con los mismos parámetros puedan reutilizar el resultado. Esto es aplicable si (y solo si) su función

  • no tiene efectos secundarios y
  • solo depende de sus parámetros (es decir, no de algún estado).

Le ahorrará tiempo si (y solo si) se llama a la función con los mismos parámetros una y otra vez. Los ejemplos populares incluyen la definición recursiva de los números de Fibonacci, es decir

f(0)=0f(1)=1f(n+2)=f(n+1)+f(n), n0

Cuando se evalúa ingenuamente, se llama exponencialmente a menudo. Con la memorización, siempre ha sido calculada por , por lo que solo queda un número lineal de llamadas.f ( n ) f ( n + 1 )ff(n)f(n+1)

Tenga en cuenta que, por el contrario, la memorización es casi inútil para algoritmos como el tipo de fusión: por lo general, pocas (si las hay) listas parciales son idénticas, y las comprobaciones de igualdad son caras (¡la clasificación es solo un poco más costosa!).

En implementaciones prácticas, la forma en que almacena los resultados es de gran importancia para el rendimiento. El uso de tablas hash puede ser la opción obvia, pero puede romper la localidad. Si sus parámetros son enteros no negativos, las matrices son una opción natural, pero pueden causar una sobrecarga de memoria enorme si usa solo algunas entradas. Por lo tanto, la memorización es una compensación entre efecto y costo; si vale la pena depende de su escenario específico.


La programación dinámica es una bestia completamente diferente. Es aplicable a problemas con la propiedad que

  • se puede dividir en subproblemas (probablemente en más de una forma),
  • esos subproblemas se pueden resolver de forma independiente,
  • Las soluciones (óptimas) de esos subproblemas se pueden combinar con las soluciones (óptimas) del problema original y
  • Los subproblemas tienen la misma propiedad (o son triviales).

Esto suele estar implícito (implícitamente) cuando las personas invocan el Principio de Optimidad de Bellman .

Ahora, esto solo describe una clase de problemas que pueden expresarse mediante un cierto tipo de recursión. La evaluación de estos es (a menudo) eficiente porque la memorización se puede aplicar con gran efecto (ver arriba); por lo general, los subproblemas más pequeños ocurren como parte de muchos problemas más grandes. Los ejemplos populares incluyen la distancia de edición y el algoritmo Bellman-Ford .

Rafael
fuente
¿Está diciendo que hay casos en que la programación dinámica conducirá a una mejor complejidad del tiempo, pero la memorización no ayudaría (o al menos no tanto)? ¿Tienes algún ejemplo? ¿O simplemente está diciendo que la programación dinámica es útil solo para un subconjunto de problemas donde está la memorización?
svick
@svick: La programación dinámica no acelera nada per se, solo si la recursividad DP se evalúa con la memorización (que suele ser (!) el caso). Nuevamente: DP es una forma de modelar problemas en términos de recursividad, la memorización es una técnica para acelerar algoritmos recursivos adecuados (sin importar si es DP). No tiene sentido comparar ambos directamente. Por supuesto, intenta modelar un problema como DP porque espera aplicar la memorización y, por lo tanto, resolverla más rápidamente de lo que podrían hacerlo los enfoques ingenuos (r). Pero un punto de vista de DP tampoco siempre conduce al algoritmo más eficiente.
Raphael
Si tiene varios procesadores disponibles, la programación dinámica mejora en gran medida el rendimiento del mundo real, ya que puede paralelizar las partes. Sin embargo, en realidad no cambia la complejidad del tiempo.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Eso es cierto para cualquier recursión. Sin embargo, no está claro que esto cree una buena aceleración, porque la memorización es menos eficiente sobre los límites del procesador.
Raphael
Corrección: la evaluación de las recurrencias DP de forma ingenua puede ser (mucho) más rápida que la fuerza bruta; cf. Aquí .
Raphael