¿De qué trata la programación dinámica?

33

Lo siento de antemano si esta pregunta suena tonta ...

Hasta donde sé, construir un algoritmo usando programación dinámica funciona de esta manera:

  1. expresa el problema como una relación de recurrencia;
  2. implementar la relación de recurrencia ya sea mediante la memorización o mediante un enfoque ascendente.

Hasta donde sé, he dicho todo sobre programación dinámica. Quiero decir: la programación dinámica no proporciona herramientas / reglas / métodos / teoremas para expresar relaciones de recurrencia, ni para convertirlas en código.

Entonces, ¿qué tiene de especial la programación dinámica? ¿Qué le ofrece, aparte de un método vago para abordar un cierto tipo de problemas?

oye oye
fuente
11
Factoid histórico (este comentario no lo ayudará, pero Bellman es realmente una buena pista si desea obtener una teoría sólida sobre la programación dinámica): cuando Bellman se le ocurrió lo que ahora se conoce como programación dinámica, llamó a la idea "programación dinámica "debido a que el trabajo puramente teórico no volaría con su empleador en ese momento, por lo que necesitaba algo más popular que no se pudiera usar de manera peyorativa .
G. Bach
3
Que yo sepa, son exactamente estos dos puntos los que mencionas. Se vuelve especial cuando evita la explosión exponencial debido a la superposición de subproblemas. Eso es todo. Ah, por cierto, mi profesor prefiere el "paradigma algorítmico" sobre el "método vago".
Hendrik Jan
La "programación dinámica" parece ser principalmente una palabra de moda (que desde entonces perdió su voz). Eso no significa que no sea útil, por supuesto.
user253751
3
No merece una respuesta, pero para mí la programación dinámica es definitivamente "lo que usas cuando intentas resolver un problema de forma recursiva, pero terminas perdiendo el tiempo revisando los mismos subproblemas una y otra vez".
hobbs
@hobbs: Exactamente, pero la habilidad está en encontrar esa forma inicial de perder el tiempo;)
j_random_hacker

Respuestas:

27

La programación dinámica le brinda una forma de pensar sobre el diseño de algoritmos. Esto a menudo es muy útil.

Los métodos de memorización y ascendentes le brindan una regla / método para convertir las relaciones de recurrencia en código. La memorización es una idea relativamente simple, ¡pero las mejores ideas a menudo lo son!

La programación dinámica le brinda una forma estructurada de pensar sobre el tiempo de ejecución de su algoritmo. El tiempo de ejecución está determinado básicamente por dos números: el número de subproblemas que tiene que resolver y el tiempo que lleva resolver cada subproblema. Esto proporciona una manera conveniente y fácil de pensar sobre el problema de diseño del algoritmo. Cuando tiene una relación de recurrencia candidata, puede verla y tener una idea muy rápida de cuál podría ser el tiempo de ejecución (por ejemplo, a menudo puede decir muy rápidamente cuántos subproblemas habrá, que es un límite inferior en el tiempo de ejecución; si hay exponencialmente muchos subproblemas que tiene que resolver, entonces la recurrencia probablemente no será un buen enfoque). Esto también le ayuda a descartar descomposiciones de subproblemas candidatos. Por ejemplo, si tenemos una cadenaS [ 1 .. i ] S [ j . . n ] S [ i . . j ] n S nS[1..n], definir un subproblema con un prefijo o sufijo o una subcadena puede ser razonable (el número de subproblemas es polinomial en ), pero definir un subproblema por una subsecuencia de no es probable que sea un buen enfoque (el número de subproblemas es exponencial en ). Esto le permite podar el "espacio de búsqueda" de posibles recurrencias.S[1..i]S[j..n]S[i..j]nSn

La programación dinámica le brinda un enfoque estructurado para buscar relaciones de recurrencia de candidatos. Empíricamente, este enfoque suele ser eficaz. En particular, hay algunos patrones heurísticos / comunes que puede reconocer para formas comunes de definir subproblemas, dependiendo del tipo de entrada. Por ejemplo:

  • Si la entrada es un número entero positivo , una forma candidata de definir un subproblema es reemplazando por un número entero más pequeño (st ).n n 0 n nnnn0nn

  • Si la entrada es una cadena , algunas formas posibles de definir un subproblema incluyen: reemplazar con un prefijo ; reemplazar con un sufijo ; reemplace con una subcadena . (Aquí el subproblema está determinado por la elección de .)S[1..n]S[1..n]S[1..i]S[1..n]S[j..n]S[1..n]S[i..j]i,j

  • Si la entrada es una lista , haga lo mismo que haría para una cadena.

  • Si la entrada es un árbol , una forma candidata de definir un subproblema es reemplazar con cualquier subárbol de (es decir, elegir un nodo y reemplazar con el subárbol enraizado en ; el subproblema se determina por la elección de )TTTxTxx

  • Si la entrada es un par , mire recursivamente el tipo de el tipo de para identificar una forma de elegir un subproblema para cada uno. En otras palabras, una forma candidata para definir un subproblema es reemplazar por donde es un subproblema para e es un subproblema para . (También puede considerar subproblemas de la forma o .)x y ( x , y ) ( x , y ) x x y y ( x , y ) ( x , y )(x,y)xy(x,y)(x,y)xxyy(x,y)(x,y)

Y así. Esto le proporciona una heurística muy útil: con solo mirar la firma de tipo del método, puede encontrar una lista de formas candidatas para definir subproblemas. En otras palabras, solo observando el enunciado del problema, observando solo los tipos de entradas, puede encontrar un puñado de formas candidatas para definir un subproblema.

Esto a menudo es muy útil. No le dice cuál es la relación de recurrencia, pero cuando tiene una opción particular sobre cómo definir el subproblema, a menudo no es demasiado difícil determinar una relación de recurrencia correspondiente. Por lo tanto, a menudo convierte el diseño de un algoritmo de programación dinámico en una experiencia estructurada. Anote en papel de desecho una lista de formas candidatas para definir subproblemas (usando la heurística anterior). Luego, para cada candidato, intente escribir una relación de recurrencia y evaluar su tiempo de ejecución contando el número de subproblemas y el tiempo empleado por subproblema. Después de probar a cada candidato, conserva el mejor que pudo encontrar. Proporcionar cierta estructura al proceso de diseño del algoritmo es una gran ayuda, ya que de lo contrario el diseño del algoritmo puede ser intimidante (hay '

DW
fuente
Entonces confirma que la programación dinámica no proporciona "procedimientos" concretos a seguir. Es solo "una forma de pensar", como dijiste. Tenga en cuenta que no estoy argumentando que DP es inútil (¡por el contrario!), Solo estoy tratando de entender si hay algo que me falta o si debería practicar más.
hey hey
@heyhey, bueno, sí ... y no. Vea mi respuesta revisada para más detalles. No es una bala de plata, pero proporciona algunos procedimientos semi-concretos que a menudo son útiles (no se garantiza que funcionen, pero a menudo son útiles).
DW
¡Muchas gracias! Al practicar me estoy familiarizando cada vez más con algunos de esos "procedimientos semi-concretos" que está describiendo.
hey hey
"Si hay exponencialmente muchos subproblemas que tienes que resolver, entonces la recurrencia probablemente no será un buen enfoque". Para muchos problemas no se conoce un algoritmo de tiempo polinómico. ¿Por qué debería ser este un criterio para usar DP?
Chiel ten Brinke
@Chiel, no es un criterio para usar DP. Si tiene un problema en el que estaría contento con los algoritmos de tiempo exponencial, puede ignorar ese comentario en paréntesis en particular. Es solo un ejemplo para tratar de ilustrar el punto general que estaba haciendo, no es algo que deba tomarse demasiado en serio o interpretar como una regla estricta.
DW
9

Su comprensión de la programación dinámica es correcta ( afaik ), y su pregunta está justificada.

Creo que el espacio de diseño adicional que obtenemos del tipo de recurrencias que llamamos "programación dinámica" se puede ver mejor en comparación con otros esquemas de enfoques recursivos.

Supongamos que nuestras entradas son matrices en aras de resaltar los conceptos.A[1..n]

  1. Enfoque inductivo

    Aquí la idea es hacer que su problema sea más pequeño, resolver la versión más pequeña y derivar una solución para la original. Esquemáticamente

    f(A)=g(f(A[1..nc]),A)

    con la función / algoritmo que traduce la solución.g

    Ejemplo: encontrar superestrellas en tiempo lineal

  2. Divide y vencerás

    Particione la entrada en varias partes más pequeñas, resuelva el problema para cada una y combine. Esquemáticamente (para dos partes),

    .f(A)=g(f(A[1..c]),f(A[c+1..n]),A)

    Ejemplos: Fusionar / Clasificación rápida, distancia por pares más corta en el plano

  3. Programación dinámica

    Considere todas las formas de dividir el problema en problemas más pequeños y elija el mejor. Esquemáticamente (para dos partes),

    .f(A)=best{g(f(A[1..c]),f(A[c+1..n]))|1cn1}

    Ejemplos: editar distancia, cambiar el problema

    Nota al margen importante: ¡ la programación dinámica no es fuerza bruta ! La aplicación de lo en cada paso reduce considerablemente el espacio de búsqueda.best

En cierto sentido, usted sabe cada vez menos estáticamente yendo de arriba a abajo, y tiene que tomar más y más decisiones dinámicamente.

La lección de aprender acerca de la programación dinámica es que está bien probar todas las particiones posibles (bueno, es necesario para la corrección) porque aún puede ser eficiente usando la memorización.

Rafael
fuente
La "programación dinámica podada" (cuando corresponde) demuestra que NO se requiere probar todas las posibilidades para ser correcto.
Ben Voigt
@BenVoigt Por supuesto. Permanecí deliberadamente vago sobre lo que significa "todas las formas de partición"; ¡Desea descartar tantos como sea posible, por supuesto! (Sin embargo, incluso si intenta todas las formas de particionamiento, no obtiene fuerza bruta, ya que solo investiga combinaciones de soluciones óptimas para subproblemas, mientras que la fuerza bruta investigaría todas las combinaciones de todas las soluciones).
Raphael
Continuemos esta discusión en el chat .
Apass.Jack
5

La programación dinámica le permite intercambiar memoria por tiempo de cálculo. Considere el ejemplo clásico, Fibonacci.

Fibonacci se define por la recurrencia . Si resuelve el uso de esta recursividad, termina haciendo llamadas O ( 2 n ) a F i b ( ) , ya que el árbol de recursión es un árbol binario con altura n .Fib(n)=Fib(n1)+Fib(n2)O(2n)Fib()n

En cambio, desea calcular , luego use esto para encontrar F i b ( 3 ) , use eso para encontrar F i b ( 4 ) , etc. Esto solo toma tiempo O ( n ) .Fib(2)Fib(3)Fib(4)O(n)

DP también nos proporciona técnicas básicas para traducir una relación de recurrencia en una solución de abajo hacia arriba, pero estas son relativamente sencillas (y generalmente implican el uso de una matriz dimensional , o una frontera de dicha matriz, donde m es el número de parámetros en La relación de recurrencia). Estos se explican bien en cualquier texto sobre DP.mm

Kittsil
fuente
1
Solo se habla de la parte de la memorización, que pierde el punto de la pregunta.
Raphael
1
"La programación dinámica le permite cambiar la memoria por tiempo de cálculo" no es algo que escuché cuando estaba en la universidad, y es una excelente manera de ver este tema. Esta es una respuesta intuitiva con un ejemplo sucinto.
Trueshot
@trueshot: Excepto que a veces la programación dinámica (y en particular, "Programación dinámica podada") puede reducir los requisitos de tiempo y espacio.
Ben Voigt
@Ben No dije que era un intercambio uno a uno. También puede podar un árbol de recurrencia. Creo que sí respondí la pregunta, que era: "¿Qué nos consigue DP?" Nos consigue algoritmos más rápidos intercambiando espacio por tiempo. Estoy de acuerdo en que la respuesta aceptada es más exhaustiva, pero esto también es válido.
Kittsil
2

Aquí hay otra forma ligeramente diferente de redactar lo que la programación dinámica le brinda. La programación dinámica colapsa un número exponencial de soluciones candidatas en un número polinómico de clases de equivalencia, de modo que las soluciones candidatas en cada clase son indistinguibles en algún sentido.

kAn2nO(n2)f(i,)i

f(i,)=j<i such thatA[j]<A[i]f(j,1)
f(i,1)=1 for all i=1n

O(n2k)

jnalanko
fuente