algorithm - software - programacion dinamica vs divide y venceras

Buenos ejemplos, artículos, libros para comprender la programación dinámica (14)

No puedo descifrar los principios de la programación dinámica y realmente lo quiero. DP es muy poderoso, puede resolver problemas como este:

Obtener la suma más baja posible de la diferencia de números

Entonces, ¿pueden sugerirme buenos libros o artículos (preferiblemente con ejemplos con código real) que me expliquen qué es la programación dinámica? Realmente quiero ejemplos simples antes que nada, luego seguiré adelante.

Solo algunos problemas se pueden resolver con la programación dinámica

Dado que nadie lo ha mencionado aún, las propiedades necesarias para que una solución de programación dinámica sea aplicable son:

Subproblemas superpuestos. Debe ser posible dividir el problema original en subproblemas de tal manera que algunos subproblemas ocurran más de una vez. La ventaja de la DP sobre la recursión simple es que cada uno de estos subproblemas se resolverá solo una vez , y los resultados se guardarán y reutilizarán si es necesario. En otras palabras, los algoritmos DP intercambian memoria por tiempo.
Subestructura óptima Debe ser posible calcular la solución óptima para un subproblema utilizando solo las soluciones óptimas para los subproblemas. Verificar que esta propiedad se mantenga puede requerir un pensamiento cuidadoso.

Ejemplo: rutas más cortas para todos los pares

Como ejemplo típico de un algoritmo de DP, considere el problema de encontrar las longitudes de las rutas más cortas entre todos los pares de vértices en un gráfico usando el algoritmo de Floyd-Warshall .

Supongamos que hay n vértices numerados del 1 al n . Aunque estamos interesados en calcular una función d(a, b) , la longitud de la ruta más corta entre los vértices a y b , es difícil encontrar una manera de calcular esto de manera eficiente a partir de otros valores de la función d() .

Introduzcamos un tercer parámetro c , y definamos d(a, b, c) como la longitud de la ruta más corta entre b que solo visita vértices en el rango de 1 a c en el medio. (No es necesario que visite todos esos vértices.) Aunque esto parece una restricción inútil para agregar, observe que ahora tenemos la siguiente relación:

d(a, b, c) = min(d(a, b, c-1), d(a, c, c-1) + d(c, b, c-1))

Los 2 argumentos a min() arriba muestran los 2 casos posibles. La forma más rápida de ir de a a b usando solo los vértices 1 a c :

Evita c (en cuyo caso es igual a la ruta más corta usando solo los primeros vértices c-1 ), o
Va por c . En este caso, esta ruta debe ser la más corta desde a hasta c seguida de la ruta más corta desde c hasta b , con ambas rutas restringidas para visitar solo vértices en el rango de 1 a c-1 en el medio. Sabemos que si este caso (yendo por c ) es más corto, entonces estos 2 caminos no pueden visitar ninguno de los mismos vértices, porque si lo hicieran, sería aún más corto omitir todos los vértices (incluyendo c ) entre ellos, entonces caso 1 han sido recogidos en su lugar.

Esta formulación satisface la propiedad óptima de la subestructura : solo es necesario conocer las soluciones óptimas para los subproblemas para encontrar la solución óptima a un problema mayor. ( No todos los problemas tienen esta propiedad importante; por ejemplo, si quisiéramos encontrar las rutas más largas entre todos los pares de vértices, este enfoque se rompe porque la ruta más larga de aa c puede visitar vértices que también son visitados por la ruta más larga desde c a b )

Conociendo la relación funcional anterior, y la condición de frontera que d(a, b, 0) es igual a la longitud del borde entre a y b (o infinito si no existe tal borde), es posible calcular cada valor de d(a, b, c) , comenzando desde c=1 y trabajando hasta c=n . d(a, b, n) es la distancia más corta entre a y b que puede visitar cualquier vértice en el medio - la respuesta que estamos buscando.

Algoritmos de planificación, por Steven LaValle tiene una sección sobre programación dinámica:

http://planning.cs.uiuc.edu/

Ver por ejemplo la sección 2.3.1.

Casi todos los libros de algoritmos introductorios tienen algunos capítulos para la programación dinámica. Yo lo recomiendo:

Introducción a los algoritmos por Cormen et al
Introducción a los algoritmos: un enfoque creativo de Udi Manber

Como parte de una maestría de Matemáticas de correspondencia, hice un curso basado en el libro http://www.amazon.co.uk/Introduction-Programming-International-mathematics-computer/dp/0080250645/ref=sr_1_4?ie=UTF8&qid=1290713580&sr=8-4 Realmente es más un ángulo matemático que un ángulo de programación, pero si puede dedicar el tiempo y el esfuerzo, es una introducción muy completa, que me pareció un trabajo como un curso que se ejecutó prácticamente fuera del libro.

También tengo una versión anterior del libro "Algorithms" (Algoritmos) de Sedgewick, y hay un breve capítulo muy ameno sobre programación dinámica allí. Ahora parece vender una desconcertante variedad de libros caros. Mirando en Amazon, parece que hay un capítulo del mismo nombre en http://www.amazon.co.uk/gp/product/toc/0201361205/ref=dp_toc?ie=UTF8&n=266239

Creo que la programación dinámica algebraica vale la pena mencionar. Es una presentación bastante inspiradora de la técnica de DP y se usa ampliamente en la comunidad de la bioinformática. Además, el principio de optimalidad de Bellman se establece de una manera muy comprensible.

Tradicionalmente, DP se enseña con el ejemplo: los algoritmos se expresan en términos de recurrencias entre entradas de tabla que almacenan soluciones a problemas intermedios, a partir de esta tabla, la solución global se construye a través de un análisis de caso.

ADP organiza el algoritmo DP de forma que la descomposición del problema en subproblemas y el análisis de casos estén completamente separados del objetivo de optimización previsto. Esto permite reutilizar y combinar diferentes partes de algoritmos DP para problemas similares.

Hay tres partes débilmente acopladas en el algoritmo ADP:

creación de espacio de búsqueda (que se expresa en términos de gramáticas arbóreas);
puntuación de cada elemento del espacio de búsqueda;
función objetivo seleccionando aquellos elementos del espacio de búsqueda, en los que estamos interesados.

Todas estas partes luego se fusionaron automáticamente, produciendo un algoritmo efectivo.

Empezar con

Artículo de wikipedia sobre programación dinámica luego
Te sugiero que leas este artículo en Topcoder
ch6 sobre programación dinámica en algoritmos (Vazirani)
Capítulo de programación dinámica en Algorithms Design Manual
Capítulo de programación dinámica en algoritmos libro clásico ( Introducción a algoritmos )

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

y por supuesto

mira la categoría de programación dinámica del algoritmo

También puedes ver buenos algoritmos de universidades cursos

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

En resumen, la Programación Dinámica es un método para resolver problemas complejos dividiéndolos en pasos más simples, es decir, resolviendo un problema paso a paso.

Espero que estos enlaces ayuden al menos un poco.

MIT Open CourseWare 6.00 Introducción a la informática y la programación

Si intentas una programación dinámica para resolver un problema, creo que llegarás a apreciar el concepto detrás de esto. En Google codejam, una vez que los participantes recibieron un programa llamado " Bienvenido a CodeJam ", reveló el uso de la programación dinámica de una manera excelente.

Si quiere aprender sobre algoritmos, he encontrado que MIT tiene algunos videos excelentes de conferencias disponibles.

Por ejemplo, 6.046J / 18.410J Introducción a los algoritmos (SMA 5503) parece ser una buena apuesta.

El curso cubre la programación dinámica, entre muchas otras técnicas algorítmicas útiles. El libro utilizado es también, en mi opinión personal, bastante excelente, y muy digno de una compra para cualquier persona seria en el aprendizaje de algoritmos.

Además, el curso viene con una lista de tareas y demás, por lo que tendrás la posibilidad de ejercitar la teoría en la práctica también.

Preguntas relacionadas:

Vea abajo

http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

y hay demasiadas muestras y referencias de artículos en el artículo anterior.

Después de aprender programación dinámica puede mejorar su habilidad resolviendo problemas de UVA . Hay listas de algunos problemas de programación dinámica de UVA en el tablero de discusión de UVA.

También Wiki tiene buenas muestras simples para ello.

Editar: para algoritmo de libro al respecto, puede usar:

Algoritmos de Python: Dominio de algoritmos básicos en el lenguaje Python : en este libro puede ver el trabajo práctico con DP.
Introducción a los algoritmos : la forma más simple posible de describir los algoritmos hechos en este libro.

También debería echar un vistazo a memoization en la programación dinámica.

La programación dinámica es un tipo de algoritmo útil que se puede utilizar para optimizar problemas difíciles dividiéndolos en subproblemas más pequeños. Al almacenar y reutilizar soluciones parciales, logra evitar las trampas de usar un algoritmo codicioso. Hay dos tipos de programación dinámica, de abajo hacia arriba y de arriba hacia abajo.

Para que un problema se pueda resolver usando programación dinámica, el problema debe poseer la propiedad de lo que se llama una subestructura óptima . Esto significa que, si el problema se dividió en una serie de subproblemas y se encontró la solución óptima para cada subproblema, la solución resultante se realizará a través de la solución a estos subproblemas. Un problema que no tiene esta estructura no puede resolverse con programación dinámica.

De arriba hacia abajo

De arriba hacia abajo es mejor conocido como memoization . Es la idea de almacenar cálculos pasados para evitar volver a calcularlos cada vez.

Dada una función recursiva, diga:

fib(n) = 0 if n = 0 1 if n = 1 fib(n - 1) + fib(n - 2) if n >= 2

Podemos escribir esto recursivamente desde su forma matemática fácilmente como:

function fib(n) if(n == 0 || n == 1) n else fib(n-1) + fib(n-2)

Ahora, cualquiera que haya estado programando por un tiempo o conozca una o dos cosas sobre la eficiencia algorítmica le dirá que esta es una idea terrible. La razón es que, en cada paso, debe volver a calcular el valor de fib (i), donde i es 2..n-2.

Un ejemplo más eficiente de esto es almacenar estos valores, creando un algoritmo de programación dinámica de arriba hacia abajo.

m = map(int, int) m[0] = 0 m[1] = 1 function fib(n) if(m[n] does not exist) m[n] = fib(n-1) + fib(n-2)

Al hacer esto, calculamos fib (i) como máximo una vez.

De abajo hacia arriba

De abajo hacia arriba utiliza la misma técnica de memorización que se utiliza en la parte superior hacia abajo. La diferencia, sin embargo, es que bottom-up utiliza sub-problemas comparativos conocidos como recurrencias para optimizar su resultado final.

En la mayoría de los problemas de programación dinámica ascendente, a menudo intenta minimizar o maximizar una decisión. Le dan dos (o más) opciones en cualquier punto dado y tiene que decidir cuál es la más óptima para el problema que está tratando de resolver. Estas decisiones, sin embargo, se basan en elecciones anteriores que hizo.

Al tomar la decisión más óptima en cada punto (cada subproblema), se asegura de que su resultado general sea el más óptimo.

La parte más difícil de estos problemas es encontrar las relaciones de recurrencia para resolver su problema.

Para pagar un montón de libros de texto de algoritmo, planeas robar una tienda que tenga n artículos. El problema es que su pequeña mochila solo puede contener como máximo W kg. Conociendo el peso (w [i]) y el valor (v [i]) de cada artículo, desea maximizar el valor de sus bienes robados que, en conjunto, pesan como máximo W. Para cada artículo, debe hacer una elección binaria: Tómelo o déjelo.

Ahora, necesita encontrar cuál es el subproblema. Siendo un ladrón muy brillante, te das cuenta de que el valor máximo de un elemento dado, i, con un peso máximo, w, se puede representar m [i, w]. Además, m [0, w] (0 elementos como máximo peso w) ym [i, 0] (i elementos con 0 peso máximo) siempre será igual a 0 valor.

asi que,

m[i, w] = 0 if i = 0 or w = 0

Con su máscara de pensamiento en la cara completa, observa que si ha llenado su bolso con tanto peso como pueda, no se puede considerar un nuevo artículo a menos que su peso sea menor o igual a la diferencia entre su peso máximo y el peso actual de la bolsa. Otro caso en el que podría considerar un artículo es si tiene un peso menor o igual al de un artículo en la bolsa, pero tiene más valor.

m[i, w] = 0 if i = 0 or w = 0 m[i - 1, w] if w[i] > w max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w

Estas son las relaciones de recurrencia descritas anteriormente. Una vez que tienes estas relaciones, escribir el algoritmo es muy fácil (¡y corto!).

v = values from item1..itemn w = weights from item1..itemn n = number of items W = maximum weight of knapsack m[n, n] = array(int, int) function knapsack for w=0..W m[0, w] = 0 for i=1 to n m[i, 0] = 0 for w=1..W if w[i] <= w if v[i] + m[i-1, w - w[i]] > m[i-1, w] m[i, w] = v[i] + m[i-1, w - w[i]] else m[i, w] = m[i-1, w] else m[i, w] = c[i-1, w] return m[n, n]

Recursos adicionales

Problemas de ejemplo

Afortunadamente, la programación dinámica se ha convertido realmente en una cuestión de programación competitiva. Consulte la Programación dinámica en UVAJudge para ver algunos problemas de práctica que pondrán a prueba su capacidad para implementar y encontrar recurrencias para problemas de programación dinámica.

Este artículo de USACO es un buen punto de partida para comprender los conceptos básicos de DP y cómo puede dar tremendas aceleraciones. Luego mire este artículo de TopCoder que también cubre los conceptos básicos, pero no está escrito tan bien. Este tutorial de CMU también es bastante bueno. Una vez que comprenda eso, tendrá que dar el salto a 2D DP para resolver el problema al que se refiere. Lea este artículo de Topcoder hasta e incluyendo la pregunta de manzanas (etiquetada como intermedia).

También puede resultar útil ver esta conferencia de video de MIT , dependiendo de qué tan bien recoja las cosas de los videos.

También tenga en cuenta que deberá tener una sólida comprensión de la recursión antes de poder recoger DP con éxito. ¡DP es difícil ! Pero la parte realmente difícil es ver la solución. Una vez que comprenda el concepto de DP (al cual debe llegar) le está dando el boceto de una solución (por ejemplo, mi respuesta a su pregunta, entonces realmente no es tan difícil de aplicar, ya que las soluciones de DP suelen ser muy conciso y no muy lejos de las versiones iterativas de una solución recursiva más fácil de entender.

También debe echar un vistazo a la memoization , que algunas personas encuentran más fácil de entender, pero a menudo es tan eficiente como DP. Para explicarlo brevemente, la memorización toma una función recursiva y guarda sus resultados en la caché para ahorrar el volver a computar los resultados para los mismos argumentos en el futuro.

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