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

Una cosa que agregaría a las otras respuestas proporcionadas aquí es que el término “programación dinámica” se refiere comúnmente a dos conceptos diferentes, pero relacionados. Los dos conceptos provienen de la informática por un lado, y la teoría de control / investigación de operaciones por el otro. La distinción es un poco confusa porque las vistas CS y OR / controles de DP están relacionadas entre sí (CS, controles y OR se superponen bastante), y puede argumentar que una vista de DP es un caso especial de el otro.

La mayoría de las otras respuestas a esta pregunta se refieren a la vista CS de DP, que se refiere al enfoque algorítmico general para resolver problemas dividiéndolos en muchos pequeños problemas similares. Esta es una colección bastante amplia de ideas y toca temas tanto teóricos como relacionados con la implementación.

La vista OR / controles de DP está más enfocada que la vista CS amplia de DP. Cuando OR / controles las personas hablan sobre DP, se refieren a un enfoque específico para resolver una clase de problemas conocidos como problemas de “control óptimo”. Un problema de control óptimo es un tipo especial de problema de optimización matemática en el que el objetivo es encontrar la mejor regla para aplicar (“política”) para controlar algo con el tiempo. Para las personas que vienen de CS, el aprendizaje de refuerzo puede verse como una generalización del control óptimo.

La clave para reconocer con la vista OR / controles de DP es que los problemas de control óptimos tienen una forma matemática específica (bueno, dos, una forma para tiempo continuo y una forma para tiempo discreto) y DP es una forma de resolver problemas escritos ene sta forma. De hecho, algunas personas usan el término “algoritmo de programación dinámica” como sinónimo de la técnica conocida como “inducción hacia atrás” (también llamada “iteración de valor”) que a menudo se usa para resolver problemas de control óptimos. Para más información sobre la concepción de OR / controles de DP, una buena referencia es Bertsekas [1]. Por cierto, Bertsekas enseña CS, pero su libro usa el término DP en el sentido OR / controles.

Por lo que puedo decir, el término “programación dinámica” se originó en los controles OR /, y se abrió paso en CS por analogía, ya que el algoritmo OR DP es un tipo de algoritmo CS DP. Esto, tal vez, explica el nombre. En OR, “programación” se trata más de programar y asignar (por ejemplo, como en “programa de eventos” o “programación de TV”) que de instruir a una computadora sobre los cálculos a realizar. La palabra “dinámico” se refiere al hecho de que los controles se aplican secuencialmente a lo largo del tiempo: los controles aplicados en el tiempo t0 tienen consecuencias que afectan los controles que deberían aplicarse en un momento posterior t1.

Referencia

[1] Dimitri P. Bertsekas, Programación dinámica y control óptimo, Programación dinámica y control óptimo

Vamos a jugar un juego. ¿Alguna vez has oído hablar del juego de Wikipedia?

La idea es que si sigues haciendo clic en el primer enlace en cualquier página de Wikipedia (no importa cuán oscuro sea), en última instancia, volverás a la página de Filosofía. [1]

Saltará de un tema a otro y se desplazará hacia conceptos cada vez más fundamentales … Lenguaje, Matemáticas, Lógica, hasta finalmente – Filosofía.

Es un juego divertido, y es cierto para ~ 97% de los artículos de Wikipedia.

Si juegas esto varias veces, comenzarás a notar algo que vamos a usar en un minuto: verás que muchos de los mismos temas aparecen una y otra vez.

No siempre, pero a menudo lo suficiente como para notarlo.

Ahora hagamos una pregunta complicada:

¿Cuál es el número promedio de enlaces en los que debe hacer clic desde cualquier página para llegar a la página de Filosofía?

(Ignoraremos el 3% que no lo logra).

¿Cómo responderías algo así?

Tal vez su reacción instintiva sería decir “Bueno, tenemos que comenzar en cada artículo y contar la cantidad de enlaces en los que hacemos clic hasta llegar a Filosofía”.

Ese es un buen comienzo, porque define el tipo de subproblema:

• Preguntar “¿Cuántos enlaces necesito hacer clic para inglés” puede verse como un problema distinto.
• “¿Cuántos debo hacer clic para obtener el recuento de alemán” es otro problema distinto.

Pero en realidad hay una forma mucho más rápida de hacerlo, gracias a la programación dinámica.

¿Qué pasa si vemos todos los artículos como un gráfico? (O un árbol, específicamente).

De repente, esa cosa interesante que notamos al ver los mismos artículos una y otra vez tiene mucho más sentido.

Podríamos pensar en los artículos del “primer enlace” como “padres” a otros artículos.

Por lo tanto, tanto el inglés como el alemán pueden tener “idiomas germánicos” como primer enlace y tema “principal”.

Cada artículo solo tiene un primer enlace (inherente a la definición de un primer enlace), pero ese tema principal puede tener muchos hijos.

Volviendo al problema en cuestión … Presentemos una solución a un subproblema específico:

Digámoslo así:

• Para determinar la cantidad de clics necesarios para llegar a Filosofía, comenzando con el inglés , primero debemos determinar la cantidad de clics necesarios para llegar a su padre – Idiomas germánicos
• Para determinar el recuento de idiomas germánicos , primero debemos determinar el número de idioma
• Para determinar el número de idioma , primero debemos determinar el número de lógica
• Para determinar el número de Logic , primero tenemos que averiguar el número de Math
• Para determinar el número de Matemáticas , primero tenemos que averiguar el número de Philo. Oh, espera, el número de Filosofía es claramente 0.

Así que hemos pasado de niño a padre, de niño a padre, hasta llegar al último padre, Filosofía.

Ahora aquí es donde entra la programación dinámica:

¿Qué pasa si almacenamos todas esas respuestas intermedias?

Entonces, a medida que calculamos el recuento de inglés, también almacenamos los recuentos de todos sus padres.

Ahora hagamos la pregunta para el alemán.

Para determinar el recuento de alemán, primero tenemos que calcular el recuento de idiomas germánicos.

Ah … ahí está: 4. Entonces sabemos casi al instante el recuento de alemán: 4 + 1 = 5, sin tener que pasar por todos esos pasos adicionales de nuevo.

¡Bueno!

Ahora hagámoslo para Geometría: 1 más 1 es 2. (Matemáticas rápidas).

Entiendes la idea … Podemos seguir haciendo esto para cada artículo de la lista.

Debido a que este es un árbol , los padres pueden tener muchos hijos, todos los cuales pueden beneficiarse de una sola respuesta que obtienen de sus padres … reduciendo así drásticamente la cantidad de artículos que debemos verificar de manera muy eficiente.

Al hacer esto, simplemente podemos mantener un total acumulado de la cantidad de artículos únicos visitados y el total de todos los recuentos sumados.

Luego, simplemente dividimos el recuento total por la cantidad de artículos, y listo, existe la cantidad promedio de clics que queríamos.

Eso es todo lo que es la programación dinámica.

Problemas (como este) que tienen “subproblemas superpuestos”.

Al igual que cómo obtener la respuesta para Language , primero necesitamos la respuesta para Logic , que es un “Subproblema”.

Pero el hecho de que otros artículos también necesiten la respuesta al mismo Subproblema es lo que lo convierte en un subproblema superpuesto : ambos deben hacer lo mismo en algún momento de su ejecución.

Una vez que reconocemos todo esto, podemos resolver los subproblemas superpuestos y almacenar sus resultados para ser utilizados por otros problemas.

Esto elimina la duplicación y, a menudo, solo requiere una pequeña fracción de los cálculos que de otro modo tendrían que realizarse.

Hay varias maneras de realizar la programación dinámica, esta fue solo una forma, para un tipo específico de problema.

La forma en que te mostré arriba se llama Programación dinámica de arriba hacia abajo con algo llamado Memoization . [2]

Otra forma común se llama Bottom-Up DP with Tabulation .

Existen ventajas y desventajas de las diferentes técnicas según el problema, pero al final del día, todas ahorran mucho tiempo y cómputo al almacenar las respuestas a subproblemas superpuestos.

Notas al pie

[1] Wikipedia: Cómo llegar a la filosofía – Wikipedia

[2] Memorización – Wikipedia

En la programación dinámica, un problema se divide en subproblemas, y las soluciones de estos subproblemas se combinarán para lograr una solución general para el problema principal. Cuando se utilizan enfoques como Divide-and-Conquer, un subproblema puede resolverse varias veces. Por lo tanto, los métodos de divide y vencerás tendrán que realizar más trabajo en estos casos. La programación dinámica resolverá cada uno de estos subproblemas una sola vez, lo que reducirá el número de cálculos y luego lo guardará, evitando así el trabajo de volver a calcularlo en una etapa posterior, cuando se requiere la solución para ese subproblema

La programación dinámica se utiliza para resolver problemas de optimización (como el camino más corto), donde pueden existir muchas soluciones, pero estamos interesados ​​en encontrar solo una solución óptima para el mismo (pueden existir muchas soluciones que logren el valor óptimo). Estos problemas tendrán las propiedades de superproblemas superpuestos [el problema puede dividirse en subproblemas que se reutilizan varias veces o un algoritmo recursivo resuelve el mismo subproblema una y otra vez, en lugar de generar un nuevo subproblema; Por ejemplo: números de Fibonacci] y subestructura óptima [la solución óptima puede construirse a partir de soluciones óptimas de subproblemas]. En muchos casos, los algoritmos codiciosos pueden funcionar más rápido que los algoritmos de programación dinámica, pero no se garantiza que brinden una solución óptima.

Al resolver problemas complejos, la programación dinámica es una técnica de optimización que divide el problema en subproblemas más simples y aprovecha la superposición de subproblemas almacenando en caché sus resultados y combinándolos en un orden inteligente (programación dinámica) para lograr la solución general sin volver a calcular el problema. mismos subproblemas repetidamente.

Para que la técnica sea efectiva, el número de subproblemas distintos debe ser razonablemente pequeño (no debe causar un tiempo de ejecución exponencial).

Trabajar en ejemplos reales es la mejor manera de entenderlo.
Aquí hay videos útiles, MIT. Programación dinámica
Wikipedia, programación dinámica

Algoritmo codicioso simplemente significa aprovechar al máximo lo que tiene, busca la solución local óptima cada vez, lo que en algunos casos conduce a un óptimo global como en la búsqueda de caminos. A veces, si conduce, y toma un atajo cada vez, puede llegar al destino más rápido, otras veces no lo hará si hay obras viales en uno de ellos. Sin embargo, la programación dinámica divide el problema en todos sus caminos posibles, resuelve esos problemas de manera eficiente manteniendo un registro de las soluciones pasadas y luego puede determinar realmente la solución verdadera.

P.ej. En el problema de la mochila, debe considerar cuál es la mejor combinación de artículos que un ladrón debe empacar en una bolsa para maximizar el valor. Un algoritmo codicioso no funcionaría, ya que el elemento de mayor valor cada vez podría significar que solo caben dos elementos en lugar de 3, etc., si los elementos tienen pesos diferentes y la bolsa tiene un límite de peso, por lo que se requeriría una búsqueda exhaustiva .

Mi mejor ejemplo de programación dinámica sería la serie Fibonnaci, la serie Fibonacci y la programación dinámica.

Se necesita un tiempo exponencial (no es posible que espere) para calcular la serie de Fibonacci de un número, pero mediante la programación dinámica y el almacenamiento de todas las soluciones pasadas, que se repiten muchas veces, lo hace lineal (posible obtener un resultado rápidamente) .

Respuesta simple: dividir y conquistar con el almacenamiento en caché.

Respuesta más “adecuada”: combine los resultados de cálculos anteriores con los actuales para que el código no tenga que volver a calcularlos.

Queja personal: la programación dinámica es una de esas exageraciones “nuevas” en la programación que no es más que dar un nombre formal a algo que casi todo el mundo ya hizo de todos modos (si pudieran considerar el espacio de almacenamiento).

Básicamente se reduce a: No volver a hacer algo que ya estaba hecho. Y para llegar allí divide el problema en pequeños pasos para que cada uno pueda ser “recordado” entre diferentes ejecuciones. Es solo una situación de “sentido común” que se está formalizando.

La programación dinámica es una técnica muy poderosa para resolver una clase particular de problemas. Exige una formulación muy elegante del enfoque y un pensamiento simple y la parte de codificación es muy fácil. La idea es muy simple: si ha resuelto un problema con la entrada dada, guarde el resultado para referencia futura, a fin de evitar resolver el mismo problema nuevamente … en breve ‘Recordar su pasado’ 🙂. Si el problema dado se puede dividir en subproblemas más pequeños y estos subproblemas más pequeños se dividen a su vez en otros aún más pequeños, y en este proceso, si observa algunos subproblemas superpuestos, entonces es una gran pista para DP . Además, las soluciones óptimas a los subproblemas contribuyen a la solución óptima del problema dado (denominado la propiedad de subestructura óptima).

Hay dos formas de hacer esto.

1.) De arriba hacia abajo: Comience a resolver el problema dado desglosándolo. Si ve que el problema ya se ha resuelto, simplemente devuelva la respuesta guardada. Si no se ha resuelto, resuélvalo y guarde la respuesta. Esto suele ser fácil de pensar y muy intuitivo. Esto se conoce como Memoization.

2.) De abajo hacia arriba: Analice el problema y vea el orden en que se resuelven los subproblemas y comience a resolver desde el subproblema trivial, hacia el problema dado. En este proceso, se garantiza que los subproblemas se resuelven antes de resolver el problema. Esto se conoce como programación dinámica.

Tenga en cuenta que dividir y conquistar es una técnica ligeramente diferente. En eso, dividimos el problema en subproblemas no superpuestos y los resolvemos de forma independiente, como en una combinación rápida y una ordenación rápida.

En caso de que esté interesado en ver visualizaciones relacionadas con la programación dinámica, pruebe esto.

Complementario a la programación dinámica son los algoritmos codiciosos que toman una decisión de una vez por todas cada vez que necesitan hacer una elección, de tal manera que conduzca a una solución casi óptima. Una solución de programación dinámica se basa en el principio de los algoritmos codiciosos de inducción matemática que requieren otros tipos de pruebas.

La programación dinámica es un paradigma de programación en el que se resuelve un problema dividiéndolo en subproblemas de manera recursiva en múltiples niveles con la premisa de que los subproblemas rotos en un nivel pueden repetirse en algún otro lugar en otro o en el mismo nivel del árbol.

La clave para resolver un problema de programación dinámica es primero encontrar una manera de identificar un subproblema de forma única, de modo que cuando se repita pueda ser descubierto y su resultado se tabule la primera vez que se encuentre. El mismo resultado se puede volver a utilizar cuando se vuelve a encontrar el subproblema, lo que ahorra el cálculo.

Por ejemplo, digamos que estamos calculando el enésimo término de secuencia de Fibonacci dado por la fórmula:

f (n) = f (n-1) + f (n-2), si n> 2
f (2) = 1, f (1) = 0

Para calcular f (4) el problema se rompería como f (5) = f (4) + f (3). Ahora para resolver esto, debe romper f (4) = f (3) + f (2) y así sucesivamente, de modo que su f (3) se calcule en el paso de cálculo para f (4), de modo que cuando vuelva a calcule f (5), no tiene que calcular f (3) nuevamente ya que ya se habría calculado.

Editar: Nota: Esta respuesta originalmente estaba destinada a otra pregunta (fusionada por el moderador en esta), por lo que comienza a abordar la diferencia entre algoritmos codiciosos y programación dinámica según lo solicitado por el autor de la otra pregunta

Con un algoritmo codicioso (supongo que querías decir que para la programación codiciosa) buscas una solución posiblemente subóptima, y ​​los subproblemas (a menudo tan simples como las iteraciones que componen la solución del problema principal) son independientes entre sí.

Con la programación dinámica , generalmente * busca una solución óptima y los subproblemas no son independientes entre sí . Debido a esta dependencia, durante el cálculo de la solución de un subproblema dado, puede reciclar la solución de un subproblema más pequeño **: de esta manera, aprovecha todos los subproblemas ya resueltos, ahorrando muchas operaciones que se repetirían si tuviera que resolver de forma independiente cada subproblema.

¿Cómo implementar una solución de programación dinámica? Depende del problema. En términos generales, debe poder identificar una descomposición del problema principal en un conjunto de subproblemas de tamaño decreciente, generalmente * una descomposición recursiva del problema P, como

[matemáticas] P = f (P1) = f (f (P2)) = f (f (f (P3))) =…. = f (f (… .. f (Pn)) [/ matemáticas]

donde f es algún tipo de función, P1 … n son problemas de disminución de tamaño / complejidad, y Pn es un subproblema con una solución inmediata (generalmente de tiempo constante). Ahora debe calcular las soluciones de todos los subproblemas, comenzando por los que tienen la solución inmediata Pn y retrocediendo hasta obtener la solución de P.

Debe almacenar en alguna estructura de datos apropiada (podría ser una matriz, podría ser un mapa, podría ser más sofisticado si la descomposición del problema es difícil) los resultados del subproblema, para recuperar la solución precalculada siempre que sea necesario.

* Yo diría siempre, pero no estoy 100% seguro
** Esto solo es cierto si el subproblema no es un caso base, que no depende de ningún otro subproblema del problema inicial.

Es solo un nombre elegante para decir que cuando divide el problema en subproblemas, almacenará sus valores. La próxima vez, si encuentra el mismo subproblema, simplemente reutilizará el valor almacenado en lugar de volver a calcular.

Si usa la recursividad para desglosar su problema, se llama enfoque de arriba hacia abajo (memorización) y si usa un enfoque iterativo, se llama enfoque de abajo hacia arriba. En la recursividad, comienzas con todo el problema y luego comienzas a dividirlo en partes más pequeñas. Mientras que en el enfoque iterativo, comienza con el problema más pequeño (caso base), sigue almacenando valores y avanza hasta llegar al problema real en cuestión. Muchas veces, la forma iterativa es un poco más computacionalmente eficiente en términos de tiempo que el enfoque recursivo, pero el enfoque iterativo consume más espacio.

Para comprender la programación dinámica de manera eficiente, tomemos un ejemplo.

Ejemplo : suponga que tiene que ir a la universidad y tiene 3 caminos para llegar a la universidad, así que lo que hará es encontrar la distancia más corta y seguirla, lo que significa que tiene la solución de un problema. Al día siguiente, debe ir al mercado a través de su universidad y esta vez también hay 3 caminos que puede seguir, pero esta vez, en lugar de calcular la distancia más corta entre su hogar y el mercado, encontrará la distancia más corta entre la universidad y el mercado. resultado previamente calculado para el camino más corto entre su hogar y su universidad.

Técnicamente hablando, la programación dinámica es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones. La próxima vez que ocurra el mismo subproblema, en lugar de volver a calcular su solución, uno simplemente busca la solución previamente calculada, ahorrando así el tiempo de cálculo a expensas de un gasto (con suerte) modesto en espacio de almacenamiento.

Gracias por leer.

En pocas palabras, DP es recursividad sin repetición.
Los problemas de DP almacenan soluciones de subproblemas, no siempre en una matriz o tabla. A veces no es necesaria una tabla explícita.
Lea mi otra respuesta aquí: la respuesta de Aashish Barnwal a ¿Cuál es la diferencia entre programación dinámica y recursividad?

Dp se usa básicamente para una clase de problemas cuya complejidad temporal se puede reducir de tipo exponencial a polinómico.

Umm, básicamente los problemas de DP tienen dos características principales que se superponen a subproblemas y soluciones óptimas para ellos.

Básicamente almacenamos los resultados de subproblemas y luego los usamos cuando sea necesario.

Las aplicaciones de DP pueden ser como se menciona a continuación:

1. Problema de selección globalmente óptima de almacenamiento
2. Problema de corte de varilla
3. Problema de mochila… .etc

¡Excelente!

La programación dinámica (también conocida como optimización dinámica ) es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas una sola vez y almacenando sus soluciones.

La próxima vez que ocurra el mismo subproblema, en lugar de volver a calcular su solución, uno simplemente busca la solución previamente calculada, ahorrando así el tiempo de cálculo a expensas de un gasto (con suerte) modesto en espacio de almacenamiento. (Cada una de las soluciones de subproblemas está indexada de alguna manera, generalmente basada en los valores de sus parámetros de entrada, para facilitar su búsqueda).

La técnica de almacenar soluciones a subproblemas en lugar de volver a calcularlas se llama “memorización”.

La programación dinámica se trata de tener un gran problema que no sabemos cómo resolver, y dividirlo en una serie de problemas similares más pequeños que tampoco sabemos cómo resolver.

En algún momento, terminamos con subproblemas básicos muy pequeños que somos capaces de resolver.

En contraste con la recursividad, aquí comenzamos con los subproblemas más pequeños, memorizamos soluciones para ellos y luego subimos de nivel gradualmente para resolver problemas más complejos hasta que resolvamos el original. Para una mejor comprensión, puede ver el ejemplo de la computación de la serie Fibonacci utilizando dos enfoques: la programación dinámica de recursividad VS y sentir la diferencia.

La programación dinámica es un nombre elegante para almacenar resultados intermedios y reutilizar el resultado almacenado en lugar de volver a calcularlos cada vez.

Una historia te ayudará. Supongamos que una hermosa mañana vengo a ti con un rompecabezas complicado y te desafío a resolverlo. Trabajas muy duro todo el día y me cuentas la solución esa noche. Al día siguiente, vengo a ti y te pregunto exactamente el mismo acertijo . Pero como el rompecabezas fue tan complicado que te has olvidado de la mayoría de los cálculos que hiciste, los vuelves a resolver y me dices la solución. Al tercer día, vengo a ti y te pregunto exactamente el mismo acertijo . Esta vez estás realmente molesto y decides no tirar todos tus cálculos y tenerlos a mano para que, si te molesto de nuevo, puedas mostrarme tu solución. El cuarto día cuando vuelvo a ti, y te vas ¡Ja! Ahí está tu solución. Y no tuve que pensar ni por un segundo. Y a partir de ese día, nunca pude molestarte con el rompecabezas.

Lo que hiciste se llama programación dinámica. Dijiste que si voy a tener que hacer los mismos cálculos exactos 50 veces, también podría guardarlos en algún lugar .

Crédito – Blog de alguien en commonlounge 😉

La programación dinámica no tiene nada que ver con su nombre. Es solo ” Resolver problemas más grandes con la ayuda de subproblemas más pequeños a expensas de la memoria espacial ”

De esta manera, en realidad no resuelve el problema manualmente, sino que toma la ayuda del subproblema resuelto inicialmente.

Leer: la respuesta de Jonathan Paulson a ¿Cómo debo explicar la programación dinámica a un niño de 4 años?

En palabras simples, puedo decir que DP se usa para optimizar la solución recursiva (subestructura óptima) de problemas en casos en que la solución recursiva está resolviendo subproblemas más pequeños varias veces (subproblemas superpuestos).

La recursión resuelve un problema de arriba hacia abajo, DP lo optimiza resolviendo el problema de abajo hacia arriba y utilizando un caché para almacenar resultados de subproblemas más pequeños.

Para entender DP, uno debe tener un comando sobre la recursividad.

Mi libro explica Recursion y DP en gran detalle.

http://www.amazon.in/Dynamic-Pro …

No es más que recordar resultados pasados ​​para que no necesiten tomarse el tiempo para calcular nuevamente (si es necesario).

Siempre que tenga algún “problema” que requiera que calcule alguna secuencia de valores, generalmente es una buena opción mantener aquellos que ya ha calculado en algún almacenamiento. Significa que cuando se le pide un valor, puede recuperar lo que ya está hecho en lugar de volver a calcularlo.

Si esa secuencia también depende la una de la otra, especialmente si depende de los valores anteriores en esa secuencia, es extremadamente beneficioso hacer un seguimiento de ellas.

Igual que aquí: la respuesta del usuario de Quora a ¿Qué es la programación dinámica?