Programación dinámica

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto.

Un problema tiene subproblemas superpuestos si se usa un mismo subproblema para resolver diferentes problemas mayores.

Los algoritmos divide y vencerás están dentro de los métodos descendentes
        Empezar con el problema original y descomponerlo en pasos sucesivos en problemas de menor          tamaño.

La programación dinámica por el contrario, es un método ascendente:
        Resolver primero los problemas pequeños (guardando las soluciones) y después combinarlas              para resolver problemas más grandes.

La programación dinámica hace uso de:

1. Subproblemas superpuestos
2. Subestructuras óptimas
3. Memoización

En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1. Dividir el problema en subproblemas más pequeños
2.  Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Ejemplo. Fibonacci

Si se llama a fib(5), se produce un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:

Cuando se llega en el árbol a los casos base (señalados en la imagen) evidentemente las llamadas a la función se detienen. Pero también podemos notar que existen varios casos en donde se llama recursivamente a números que ya fueron calculados, por ejemplo el 3.

Entonces para subsecuentes llamadas la cantidad de operaciones a calcular se volverían exponenciales y la complejidad aproximada sería 𝑂(𝑐 𝑛 ) lo cuál para un n=20 ya es mucho que calcular (𝑂( 1+ 5^1/2 )/2 ) ^𝑛≈ 15,127 llamadas a la función).

Originalmente, el término de programación dinámica se refería a la resolución de ciertos problemas y operaciones fuera del ámbito de la Ingeniería Informática, al igual que hacía la programación lineal. Aquel contexto no tiene relación con la programación en absoluto; el nombre es una coincidencia. El término también lo usó en los años 40 Richard Bellman, un matemático norteamericano, para describir el proceso de resolución de problemas donde hace falta calcular la mejor solución consecutivamente.

Algunos lenguajes de programación funcionales, sobre todo Haskell, pueden usar la memorización automáticamente sobre funciones con un conjunto concreto de argumentos, para acelerar su proceso de evaluación. Esto sólo es posible en funciones que no tengan efectos secundarios.

Memoizacion

Los subproblemas superpuestos provocan resolver varias veces el mismo problema, ya que la solución de un subproblema requiere calcular soluciones que otro subproblema también tenga que calcular.

Perder tiempo calculando varias veces la solución al mismo subproblema se puede evitar guardando las soluciones que ya hemos calculado. Entonces, si necesitamos resolver el mismo problema más tarde, podemos obtener la solución de la lista de soluciones calculadas y reutilizarla. Este acercamiento al problema se llama memoización (Memoization en inglés) o memorización se diferencia de 'memorización' puesto que el término ya era usado en matemáticas).

Se puede resolver el problema, utilizando el enfoque de memorización (guardar los valores que ya han sido calculados para utilizarlos posteriormente).

       Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos           cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla                             unidimensional con los resultados desde 0 hasta n.

En programación dinámica comúnmente se utilizan tablas de resultados conocidos que se va generando a medida que se resuelven los subcasos.

Subestructuras óptimas

Donde tiene mayor aplicación la Programación Dinámica es en la resolución de problemas de optimización. En este tipo de problemas se pueden presentar distintas soluciones, cada una con un valor, y lo que se desea es encontrar la solución de valor óptimo (máximo o mínimo). 

La solución de problemas mediante esta técnica se basa en el llamado principio de óptimo enunciado por Bellman en 1957 y que dice:

“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima”.

Enfoques de la programación dinámica

Top-down: El problema se divide en subproblemas, y estos se resuelven recordando las soluciones por si fueran necesarias nuevamente. Es una combinación de memoización y recursión.

Bottom-up: Todos los problemas que puedan ser necesarios se resuelven de antemano y después se usan para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado

Fibonacci utilizando programación dinámica (Top-Down)

Fibonacci utilizando programación dinámica (Buttom-Up)

Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones (solución optima) de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución optima.

En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

“En una secuencia de decisiones óptima toda subsecuencia ha de ser también óptima” 

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en problemas más pequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:

1. Una enorme cantidad de problemas
2. Problemas cuyas soluciones parciales se solapan
3. Grupos de problemas de muy distinta complejidad

Diseño de un algoritmo con programación dinámica

Para que un problema pueda ser abordado por esta técnica ha de cumplir dos condiciones:

    1. La solución al problema ha de ser alcanzada a través de una secuencia de decisiones, una en                cada etapa.

    2.Dicha secuencia de decisiones ha de cumplir el principio de optimalizad.

El diseño de un algoritmo de Programación Dinámica consta de los siguientes pasos:

1. Planteamiento de la solución como una sucesión de decisiones y verificación de que ésta cumple el principio de óptimo.
2. Definición recursiva* o iterativa de la solución
3. Cálculo del valor de la solución óptima mediante una estructura de datos en donde se almacenan soluciones a problemas parciales para reutilizar los cálculos.
4. Construcción de la solución óptima haciendo uso de la información contenida en la estructura de datos.