¿Qué es la programación dinámica? [cerrado]

277

¿Qué es la programación dinámica ?

¿En qué se diferencia de recursividad, memorización, etc.?

He leído el artículo de Wikipedia en él, pero todavía no lo entiendo.

smac89
fuente
1
Aquí hay un tutorial de Michael A. Trick de CMU que encontré particularmente útil: mat.gsia.cmu.edu/classes/dynamic/dynamic.html Sin duda, es además de todos los recursos que otros han recomendado (todos los demás recursos, especialmente CLR y Kleinberg, ¡Tardos son muy buenos!). La razón por la que me gusta este tutorial es porque introduce conceptos avanzados de forma bastante gradual. Es un material poco antiguo, pero es una buena adición a la lista de recursos presentada aquí. Consulte también la página y las conferencias de Steven Skiena sobre Programación dinámica: cs.sunysb.edu/~algorith/video-lectures http:
Edmon
11
Siempre he encontrado "Programación dinámica" un término confuso: "Dinámico" sugiere no estático, pero ¿qué es "Programación estática"? Y "... Programación" trae a la mente "Programación Orientada a Objetos" y "Programación Funcional", sugiriendo que DP es un paradigma de programación. Realmente no tengo un nombre mejor (¿quizás "Algoritmos dinámicos"?) Pero es una pena que estemos atrapados con este.
dimo414
3
@ dimo414 La "programación" aquí está más relacionada con la "programación lineal" que se incluye en una clase de métodos de optimización matemática. Consulte el artículo Optimización matemática para obtener una lista de otros métodos de programación matemática.
syockit
1
@ dimo414 "Programación" en este contexto se refiere a un método tabular, no a escribir código de computadora. - Coreman
usuario2618142
El problema de minimización del costo del boleto de autobús descrito en cs.stackexchange.com/questions/59797/… se resuelve mejor en la programación dinámica.
truthadjustr

Respuestas:

211

La programación dinámica es cuando utiliza el conocimiento pasado para facilitar la resolución de un problema futuro.

Un buen ejemplo es resolver la secuencia de Fibonacci para n = 1,000,002.

Este será un proceso muy largo, pero ¿qué pasa si le doy los resultados para n = 1,000,000 yn = 1,000,001? De repente, el problema se volvió más manejable.

La programación dinámica se usa mucho en problemas de cadenas, como el problema de edición de cadenas. Usted resuelve un subconjunto (s) del problema y luego usa esa información para resolver el problema original más difícil.

Con la programación dinámica, generalmente almacena sus resultados en algún tipo de tabla. Cuando necesite la respuesta a un problema, haga referencia a la tabla y vea si ya sabe cuál es. Si no, usa los datos en su tabla para darse un paso hacia la respuesta.

El libro de Algoritmos de Cormen tiene un gran capítulo sobre programación dinámica. ¡Y es gratis en Google Books! Compruébalo aquí.

Samoz
fuente
50
¿No acabas de describir la memorización?
dreadwail
31
Yo diría que la memorización es una forma de programación dinámica, cuando la función / método memorizado es recursivo.
Daniel Huckstep
66
Buena respuesta, solo agregaría una mención sobre la subestructura óptima (por ejemplo, cada subconjunto de cualquier ruta a lo largo de la ruta más corta de A a B es en sí la ruta más corta entre los 2 puntos finales, suponiendo una métrica de distancia que observe la desigualdad del triángulo).
Shea
55
Yo no diría "más fácil", pero más rápido. Un malentendido común es que dp resuelve problemas que los algoritmos ingenuos no pueden y ese no es el caso. No es una cuestión de funcionalidad sino de rendimiento.
andandandand
66
Usando la memorización, los problemas de programación dinámica se pueden resolver de arriba hacia abajo. es decir, llamar a la función para calcular el valor final, y esa función a su vez la llama de forma recursiva para resolver los subproblemas. Sin él, los problemas de programación dinámica solo pueden resolverse de forma ascendente.
Pranav el
176

La programación dinámica es una técnica utilizada para evitar calcular varias veces el mismo subproblema en un algoritmo recursivo.

Tomemos el ejemplo simple de los números de Fibonacci: encontrar el n º número de Fibonacci definida por

F n = F n-1 + F n-2 y F 0 = 0, F 1 = 1

Recursividad

La forma obvia de hacer esto es recursiva:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Programación dinámica

  • De arriba hacia abajo - Memoization

La recursión hace muchos cálculos innecesarios porque un número de Fibonacci determinado se calculará varias veces. Una manera fácil de mejorar esto es almacenar en caché los resultados:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]
  • De abajo hacia arriba

Una mejor manera de hacer esto es deshacerse de la recursión al evaluar los resultados en el orden correcto:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

Incluso podemos usar espacio constante y almacenar solo los resultados parciales necesarios en el camino:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi
  • ¿Cómo aplicar la programación dinámica?

    1. Encuentra la recursividad en el problema.
    2. De arriba hacia abajo: guarde la respuesta para cada subproblema en una tabla para evitar tener que volver a calcularlos.
    3. De abajo hacia arriba: encuentre el orden correcto para evaluar los resultados para que los resultados parciales estén disponibles cuando sea necesario.

La programación dinámica generalmente funciona para problemas que tienen un orden inherente de izquierda a derecha, como cadenas, árboles o secuencias de enteros. Si el ingenuo algoritmo recursivo no calcula el mismo subproblema varias veces, la programación dinámica no ayudará.

Hice una colección de problemas para ayudar a entender la lógica: https://github.com/tristanguigue/dynamic-programing

Tristan
fuente
3
Esta es una gran respuesta y la colección de problemas en Github también es muy útil. ¡Gracias!
p4sh4
Solo por curiosidad por aclarar las cosas: en su opinión, ¿una implementación recursiva que utiliza una relación recurrente y una memorización es una programación dinámica?
Codor
Gracias por la explicación. ¿Hay una condición que falta de abajo hacia arriba: if n in cachecomo con el ejemplo de arriba hacia abajo o me falta algo?
DavidC
¿Entiendo correctamente entonces que cualquier bucle donde los valores calculados en cada iteración se usan en iteraciones posteriores es un ejemplo de programación dinámica?
Alexey
¿Podría dar alguna referencia para la interpretación que dio, incluidos los casos especiales de arriba hacia abajo y de abajo hacia arriba?
Alexey
38

La memorización es cuando almacena resultados previos de una llamada a función (una función real siempre devuelve lo mismo, dadas las mismas entradas). No hace una diferencia para la complejidad algorítmica antes de que se almacenen los resultados.

La recursión es el método de una función que se llama a sí misma, generalmente con un conjunto de datos más pequeño. Dado que la mayoría de las funciones recursivas se pueden convertir en funciones iterativas similares, esto tampoco hace una diferencia para la complejidad algorítmica.

La programación dinámica es el proceso de resolver subproblemas más fáciles de resolver y construir la respuesta a partir de eso. La mayoría de los algoritmos DP estarán en el tiempo de ejecución entre un algoritmo Greedy (si existe) y un algoritmo exponencial (enumere todas las posibilidades y encuentre el mejor).

  • Los algoritmos DP podrían implementarse con recursividad, pero no tienen que serlo.
  • Los algoritmos DP no se pueden acelerar mediante la memorización, ya que cada subproblema solo se resuelve (o se llama a la función "resolver") una vez.
filomathohollic
fuente
Muy claramente puesto. Desearía que los instructores de algoritmos pudieran explicar esto bien.
Kelly S. French
22

Es una optimización de su algoritmo que reduce el tiempo de ejecución.

Si bien un algoritmo codicioso generalmente se llama ingenuo , ya que puede ejecutarse varias veces sobre el mismo conjunto de datos, la programación dinámica evita esta trampa a través de una comprensión más profunda de los resultados parciales que deben almacenarse para ayudar a construir la solución final.

Un ejemplo simple es atravesar un árbol o un gráfico solo a través de los nodos que contribuirían con la solución, o poner en una tabla las soluciones que has encontrado hasta ahora para que puedas evitar atravesar los mismos nodos una y otra vez.

Aquí hay un ejemplo de un problema adecuado para la programación dinámica, del juez en línea de UVA: Edit Steps Ladder.

Voy a hacer un breve resumen de la parte importante del análisis de este problema, tomado del libro Desafíos de programación, le sugiero que lo revise.

Mire bien ese problema, si definimos una función de costo que nos dice cuán lejos están dos cadenas, tenemos dos considerar los tres tipos naturales de cambios:

Sustitución: cambie un solo carácter del patrón "s" a un carácter diferente en el texto "t", como cambiar "disparo" a "spot".

Inserción: inserte un solo carácter en el patrón "s" para que coincida con el texto "t", como cambiar "ago" por "agog".

Eliminación: elimine un solo carácter del patrón "s" para que coincida con el texto "t", como cambiar "hora" a "nuestro".

Cuando establecemos que cada una de estas operaciones cuesta un paso, definimos la distancia de edición entre dos cadenas. Entonces, ¿cómo lo calculamos?

Podemos definir un algoritmo recursivo utilizando la observación de que el último carácter de la cadena debe coincidir, sustituirse, insertarse o eliminarse. Cortar los caracteres en la última operación de edición deja un par de operaciones deja un par de cadenas más pequeñas. Sea i y j el último carácter del prefijo relevante de y t, respectivamente. Hay tres pares de cadenas más cortas después de la última operación, correspondientes a la cadena después de una coincidencia / sustitución, inserción o eliminación. Si supiéramos el costo de editar los tres pares de cadenas más pequeñas, podríamos decidir qué opción conduce a la mejor solución y elegir esa opción en consecuencia. Podemos aprender este costo, a través de lo increíble que es la recursividad:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Este algoritmo es correcto, pero también es increíblemente lento.

Ejecutando en nuestra computadora, lleva varios segundos comparar dos cadenas de 11 caracteres, y el cálculo desaparece en nunca más nunca aterriza en nada.

¿Por qué el algoritmo es tan lento? Lleva tiempo exponencial porque vuelve a calcular los valores una y otra y otra vez. En cada posición de la cadena, la recursión se ramifica de tres maneras, lo que significa que crece a un ritmo de al menos 3 ^ n, de hecho, incluso más rápido ya que la mayoría de las llamadas reducen solo uno de los dos índices, no ambos.

Entonces, ¿cómo podemos hacer que el algoritmo sea práctico? La observación importante es que la mayoría de estas llamadas recursivas están calculando cosas que ya se han calculado antes. ¿Como sabemos? Bueno, solo puede haber | s | · | T | posibles llamadas recursivas únicas, ya que solo hay muchos pares distintos (i, j) que sirven como parámetros de llamadas recursivas.

Al almacenar los valores para cada uno de estos pares (i, j) en una tabla, podemos evitar volver a calcularlos y simplemente buscarlos según sea necesario.

La tabla es una matriz bidimensional m donde cada una de las | s | · | t | Las celdas contienen el costo de la solución óptima de este subproblema, así como un puntero principal que explica cómo llegamos a esta ubicación:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

La versión de programación dinámica tiene tres diferencias con respecto a la versión recursiva.

Primero, obtiene sus valores intermedios usando la búsqueda de tabla en lugar de llamadas recursivas.

** Segundo, ** actualiza el campo padre de cada celda, lo que nos permitirá reconstruir la secuencia de edición más adelante.

** Tercero, ** Tercero, se instrumenta usando una cell()función de objetivo más general en lugar de simplemente devolver m [| s |] [| t |] .cost. Esto nos permitirá aplicar esta rutina a una clase más amplia de problemas.

Aquí, un análisis muy particular de lo que se necesita para obtener los resultados parciales más óptimos es lo que hace que la solución sea "dinámica".

Aquí hay una solución alternativa completa para el mismo problema. También es "dinámico" a pesar de que su ejecución es diferente. Le sugiero que compruebe cuán eficiente es la solución enviándola al juez en línea de UVA. Me parece sorprendente cómo se abordó un problema tan pesado de manera tan eficiente.

andandandand
fuente
¿Realmente se requiere almacenamiento para ser una programación dinámica? ¿No se saltaría ninguna cantidad de trabajo que calificaría un algoritmo como dinámico?
Nthalk
Usted tiene que reunir óptima paso a paso los resultados para hacer una "dinámica" algoritmo. La programación dinámica se deriva del trabajo de Bellman en quirófano, si dice "que omitir cualquier cantidad de palabras es programación dinámica", está devaluando el término, ya que cualquier búsqueda heurística sería programación dinámica. en.wikipedia.org/wiki/Dynamic_programming
andandandand
13

Los bits clave de la programación dinámica son "subproblemas superpuestos" y "subestructura óptima". Estas propiedades de un problema significan que una solución óptima se compone de las soluciones óptimas para sus subproblemas. Por ejemplo, los problemas de la ruta más corta exhiben una subestructura óptima. La ruta más corta de A a C es la ruta más corta de A a algún nodo B seguido de la ruta más corta de ese nodo B a C.

En mayor detalle, para resolver un problema de ruta más corta:

  • encuentre las distancias desde el nodo inicial hasta cada nodo que lo toca (digamos de A a B y C)
  • encuentre las distancias desde esos nodos hasta los nodos que los tocan (de B a D y E, y de C a E y F)
  • ahora conocemos la ruta más corta de A a E: es la suma más corta de Ax y xE para algún nodo x que hemos visitado (B o C)
  • repita este proceso hasta llegar al nodo de destino final

Debido a que estamos trabajando de abajo hacia arriba, ya tenemos soluciones a los subproblemas a la hora de usarlos, memorizándolos.

Recuerde, los problemas de programación dinámica deben tener subproblemas superpuestos y una subestructura óptima. Generar la secuencia de Fibonacci no es un problema de programación dinámica; utiliza la memorización porque tiene subproblemas superpuestos, pero no tiene una subestructura óptima (porque no hay ningún problema de optimización involucrado).

Nick Lewis
fuente
1
En mi humilde opinión, esta es la única respuesta que tiene sentido en términos de programación dinámica. Tengo curiosidad desde cuando la gente comenzó a explicar DP usando números de Fibonacci (apenas relevante).
Terry Li
@TerryLi, puede tener sentido, pero no es fácil de entender. El problema del número de Fibonacci es conocido y fácil de entender.
Ajay
6

Programación dinámica

Definición

La programación dinámica (DP) es una técnica general de diseño de algoritmos para resolver problemas con subproblemas superpuestos. Esta técnica fue inventada por el matemático estadounidense "Richard Bellman" en la década de 1950.

Idea clave

La idea clave es guardar las respuestas de subproblemas superpuestos más pequeños para evitar el recálculo.

Propiedades de programación dinámica

  • Una instancia se resuelve utilizando las soluciones para instancias más pequeñas.
  • Las soluciones para una instancia más pequeña pueden ser necesarias varias veces, por lo tanto, almacene sus resultados en una tabla.
  • Por lo tanto, cada instancia más pequeña se resuelve solo una vez.
  • Se utiliza espacio adicional para ahorrar tiempo.
Sabir Al Fateh
fuente
5

También soy muy nuevo en la programación dinámica (un algoritmo poderoso para un tipo particular de problemas)

En palabras más simples, solo piense en la programación dinámica como un enfoque recursivo con el uso del conocimiento previo

El conocimiento previo es lo que más importa aquí. Haga un seguimiento de la solución de los subproblemas que ya tiene.

Considere esto, el ejemplo más básico para dp de Wikipedia

Encontrar la secuencia de fibonacci

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Analicemos la llamada a la función con say n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib (2) se calculó tres veces desde cero. En ejemplos más grandes, se recalculan muchos más valores de fib o subproblemas, lo que lleva a un algoritmo de tiempo exponencial.

Ahora, intentemos almacenando el valor que ya descubrimos en una estructura de datos, digamos un Mapa

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Aquí estamos guardando la solución de subproblemas en el mapa, si aún no la tenemos. Esta técnica de guardar valores que ya habíamos calculado se denomina Memoization.

Por último, para un problema, primero intente encontrar los estados (posibles subproblemas e intente pensar en el mejor enfoque de recursión para que pueda usar la solución del subproblema anterior en otros).

Aman Singh
fuente
Estafa directa de Wikipedia. ¡Votado abajo!
solidak
4

La programación dinámica es una técnica para resolver problemas con problemas secundarios superpuestos. Un algoritmo de programación dinámica resuelve cada subproblema solo una vez y luego guarda su respuesta en una tabla (matriz). Evitar el trabajo de volver a calcular la respuesta cada vez que se encuentra el subproblema. La idea subyacente de la programación dinámica es: Evite calcular las mismas cosas dos veces, generalmente manteniendo una tabla de resultados conocidos de subproblemas.

Los siete pasos en el desarrollo de un algoritmo de programación dinámica son los siguientes:

  1. Establezca una propiedad recursiva que brinde la solución a una instancia del problema.
  2. Desarrollar un algoritmo recursivo según la propiedad recursiva
  3. Vea si la misma instancia del problema se está resolviendo nuevamente y nuevamente en llamadas recursivas
  4. Desarrollar un algoritmo recursivo memorable.
  5. Vea el patrón al almacenar los datos en la memoria
  6. Convierta el algoritmo recursivo memorizado en algoritmo iterativo
  7. Optimice el algoritmo iterativo utilizando el almacenamiento según sea necesario (optimización del almacenamiento)
Adnan Qureshi
fuente
¿Es 6. Convert the memoized recursive algorithm into iterative algorithmun paso obligatorio? ¿Esto significaría que su forma final no es recursiva?
truthadjustr
no es obligatorio, es opcional
Adnan Qureshi
El objetivo es reemplazar el algoritmo recursivo utilizado para almacenar los datos en la memoria con una iteración sobre los valores almacenados porque una solución iterativa guarda la creación de una pila de funciones para cada llamada recursiva realizada.
David C. Rankin
2

en resumen, la diferencia entre la memoria de recursión y la programación dinámica

La programación dinámica como sugiere su nombre es utilizar el valor calculado anterior para construir dinámicamente la próxima solución nueva

Dónde aplicar la programación dinámica: si su solución se basa en una subestructura óptima y un subproceso superpuesto, en ese caso será útil usar el valor calculado anterior para que no tenga que volver a calcularlo. Es un enfoque de abajo hacia arriba. Suponga que necesita calcular fib (n) en ese caso, todo lo que necesita hacer es agregar el valor calculado anterior de fib (n-1) y fib (n-2)

Recursión: Básicamente subdividiendo su problema en una parte más pequeña para resolverlo con facilidad, pero tenga en cuenta que no evita el recálculo si tenemos el mismo valor calculado previamente en otra llamada de recursión.

Memorización: Básicamente, el almacenamiento del antiguo valor de recursión calculado en la tabla se conoce como memorización, lo que evitará el recálculo si ya ha sido calculado por alguna llamada anterior, por lo que cualquier valor se calculará una vez. Entonces, antes de calcular, verificamos si este valor ya se calculó o no, si ya se calculó, luego devolvemos lo mismo de la tabla en lugar de volver a calcular. También es un enfoque de arriba hacia abajo

Esfuerzo
fuente
-1

Aquí está un ejemplo sencillo de código Python Recursive, Top-down, Bottom-upenfoque para la serie de Fibonacci:

Recursivo: O (2 n )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

De arriba hacia abajo: O (n) Eficiente para entradas más grandes

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

De abajo hacia arriba: O (n) Para simplicidad y pequeños tamaños de entrada

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))
0xAliHn
fuente
El primer caso NO tiene un tiempo de ejecución de n ^ 2, su complejidad de tiempo es O (2 ^ n): stackoverflow.com/questions/360748/…
Sam
actualizado gracias. @Sam
0xAliHn