programacion probabilistica maximizacion importancia historia estocastica ejemplos economia dinamica algorithm dynamic-programming

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



programacion dinamica maximizacion (11)

Aquí está mi respuesta en un tema similar

Empezar con

Si quieres ponerte a prueba, mis elecciones sobre los jueces en línea son

y por supuesto

También puedes consultar buenos cursos de algoritmos de universidades.

Después de todo, si no puede resolver los problemas, pregunte a SO que existen muchos algoritmos adictos aquí.

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

¿En qué se diferencia de la recursión, la memoización, etc.?

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

Aquí hay un tutorial de Michael A. Trick de CMU que encontré particularmente útil:

http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

Sin duda es un complemento 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 manera bastante gradual. Es un material poco antiguo pero es una buena adición a la lista de recursos que se presenta aquí.

También puedes ver la página de Steven Skiena y las conferencias sobre programación dinámica: http://www.cs.sunysb.edu/~algorith/video-lectures/

http://www.cs.sunysb.edu/~algorith/video-lectures/1997/lecture12.pdf

En definitiva, la diferencia entre memoización recursiva y programación dinámica.

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

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

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

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

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

Si bien un algoritmo codicioso suele llamarse ingenuo , ya que puede ejecutarse varias veces en el mismo conjunto de datos, la Programación dinámica evita este escollo 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 una gráfica solo a través de los nodos que contribuirían con la solución, o poner en una tabla las soluciones que ha encontrado hasta ahora para evitar atravesar los mismos nodos una y otra vez.

Este es 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, extraído del libro Desafíos de programación, le sugiero que lo revise.

Observe detenidamente ese problema. Si definimos una función de costo que nos dice qué tan lejos son dos cadenas, tenemos dos en cuenta 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 "punto".

Inserción: inserte un solo carácter en el patrón "s" para que coincida con el texto "t", como cambiar "ago" a "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 configuramos cada una de estas operaciones para que cuesten un paso, definimos la distancia de edición entre dos cadenas. Entonces, ¿cómo lo calculamos?

Podemos definir un algoritmo recursivo usando la observación de que el último carácter de la cadena debe estar emparejado, sustituido, insertado o eliminado. Cortar los caracteres en la última operación de edición deja una operación de par deja un par de cadenas más pequeñas. Sean 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 asombroso que es la recursión:

#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.

Al ejecutarse en nuestra computadora, se necesitan varios segundos para comparar dos cadenas de 11 caracteres, y el cálculo desaparece y nunca llega a aterrizar en nada más.

¿Por qué es tan lento el algoritmo? Toma 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 una velocidad de al menos 3 ^ n, 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 son cosas de computación que ya se han computado anteriormente. ¿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 | cell contiene el costo de la solución óptima de este subproblema, así como un indicador 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 la versión recursiva.

Primero, obtiene sus valores intermedios utilizando la búsqueda de tablas en lugar de las llamadas recursivas.

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

** Tercero, ** Tercero, está instrumentado usando una función de celda 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".

Here''s una solución alternativa y completa para el mismo problema. También es "dinámico", aunque su ejecución es diferente. Le sugiero que verifique la eficacia de la solución enviándola al juez en línea de UVA. Me parece sorprendente cómo un problema tan pesado fue abordado de manera tan eficiente.

Este es un ejemplo simple de código de Python del enfoque Recursive , Top-down , Bottom-up 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 a abajo: O (n) Eficiente para una entrada más grande

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))

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

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))

La memorización es cuando se guardan los resultados anteriores de una llamada de 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. Como 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 los tiempos de ejecución entre un algoritmo codicioso (si existe) y un algoritmo exponencial (enumerar todas las posibilidades y encontrar el mejor).

  • Los algoritmos DP podrían implementarse con recursión, pero no tienen que serlo.
  • Los algoritmos DP no pueden acelerarse mediante la memorización, ya que cada subproblema solo se resuelve (o se llama a la función "resolver" una vez).

La programación dinámica es cuando se usa 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 cadena, como el problema de edición de cadena. Resuelve un subconjunto (s) del problema y luego utiliza esa información para resolver el problema original más difícil.

Con la programación dinámica, almacena sus resultados en algún tipo de tabla en general. Cuando necesita la respuesta a un problema, hace referencia a la tabla y ve si ya sabe cuál es. Si no, utiliza los datos de tu tabla para darte un paso hacia la respuesta.

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

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

Tomemos el ejemplo simple de los números de fibonacci: encontrando el número n de fibonacci definido por

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

Recursion

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

  • Arriba abajo - memoización

La recursión realiza muchos cálculos innecesarios porque un número determinado de fibonacci se calculará varias veces. Una forma 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 hacerlo es deshacerse de la recursión en conjunto evaluando 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 a abajo: almacene 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, de modo 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 algoritmo ingenuo 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

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 del camino más corto 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, seguida de la ruta más corta de ese nodo B a C.

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

  • encuentre las distancias desde el nodo de inicio hasta cada nodo que lo toque (por ejemplo, de A a B y C)
  • encuentre las distancias desde esos nodos a 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 algunos nodos x que hemos visitado (ya sea B o C)
  • Repite este proceso hasta llegar al nodo de destino final.

Debido a que estamos trabajando de abajo hacia arriba, ya tenemos soluciones para los subproblemas cuando llega el momento de usarlos, al memorizarlos.

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 memoria porque tiene subproblemas superpuestos, pero no tiene una subestructura óptima (porque no hay problema de optimización involucrado).

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

En la mayoría de las palabras simples, solo piense en la programación dinámica como un enfoque recursivo con el uso del conocimiento previo

Lo que más importa aquí es el conocimiento previo . Mantenga un registro de la solución de los subproblemas que ya tiene.

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

Encontrando la secuencia de fibonacci

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

Vamos a desglosar la llamada de función con decir 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, la 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, intentémoslo almacenando el valor que ya encontramos en una estructura de datos, por ejemplo, un Map

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 sub-problemas en el mapa, si no lo tenemos ya. Esta técnica de guardar valores que ya habíamos calculado se denomina Memoización.

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

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 que se superponen. 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 la superposición de subproblemas más pequeños para evitar recálputos.

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.
  • Así, cada instancia más pequeña se resuelve una sola vez.
  • Se utiliza espacio adicional para ahorrar tiempo.