Programación dinámica (computación)

De Wikipedia, la enciclopedia libre

En Ingeniería Informática, 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, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953.

[editar] Introducción

Una subestructura óptima significa que soluciones óptimas de subproblemas pueden ser usadas para encontrar las soluciones óptimas del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. 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 ellos mismos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Decir que un problema tiene subproblemas superpuestos es decir que un mismo subproblema es usado para resolver diferentes problemas mayores. Por ejemplo, en la sucesión de Fibonacci, F₃ = F₁ + F₂ y F₄ = F₂ + F₃ — calcular cada término supone calcular F₂. Como ambos F₃ y F₄ hacen falta para calcular F₅, una mala implementación para calcular F₅ acabará calculando F₂ dos o más veces. Esto ocurre siempre que haya subproblemas superpuestos: una mala implementación puede acabar desperdiciando tiempo recalculando las soluciones óptimas a subproblemas que ya han sido resueltos anteriormente.

Esto 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 memorización. Si estamos seguros de que no volveremos a necesitar una solución en concreto, la podemos descartar para ahorrar espacio. En algunos casos, podemos calcular las soluciones a problemas que sabemos que vamos a necesitar de antemano.

En resumen, la programación dinámica hace uso de:

• Subproblemas superpuestos
• Subestructuras óptimas
• Memorización

La programación dinámica toma normalmente uno de los dos siguientes enfoques:

• Top-down: El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente. Es una combinación de memorización y recursión.
• Bottom-up: Todos los subproblemas que puedan ser necesarios se resuelven de antemano y después son usados 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.

Originalmente, el término de programación dinámica designaba únicamente a la resolución de ciertos problemas operaciones fuera del ámbito de la Ingeniería Informática, al igual que lo hacía programación lineal. En este contexto no tiene ninguna relación con la programación en absoluto; el nombre es una coincidencia. El término también se usaba en los años 40 por Richard Bellman, un matemático americano, para describir el proceso de resolver 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, algo que ocurre en Haskell pero no tanto en otros lenguajes.

[editar] Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar la mejor solución de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cual es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.

A menudo, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima». 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.

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

• Una enorme cantidad de subproblemas.
• Subproblemas cuyas soluciones parciales se solapan.
• Grupos de subproblemas de muy distinta complejidad.

[editar] Ejemplo

[editar] Sucesión de Fibonacci

Una implementación de una función que encuentre el n-ésimo término de la sucesión de Fibonacci basada directamente en la definición matemática de la sucesión realiza mucho trabajo redundante:

   function fib(n)
       if n = 0 or n = 1
           return n
       else
           return fib(n − 1) + fib(n − 2)

Si llamamos, por ejemplo, a fib (5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib(2) ha sido calculado dos veces desde cero. En ejemplos mayores, muchos otros valores de fib, o subproblemas, son recalculados, llevando a un algoritmo de complejidad exponencial.

Ahora suponemos que tenemos un simple objeto mapa, m, que guarda cada valor de fib que ya ha sido calculado y modificamos la función para que lo use y actualice. La función resultante tiene complejidad O(n), en lugar de exponencial:

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if n not in keys(m)
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

Esta técnica de guardar los valores que ya han sido calculados se llama memoización; esto es una implementación top-down, puesto que primero dividimos el problema en otros más pequeños y después calculamos y almacenamos los valores. En este caso, también podemos evitar que la función use una cantidad de espacio lineal (O(n)) y use una cantidad constante en su lugar cambiando la definición de nuestra función y usando una implementación bottom-up que calculará valores pequeños de fib primero para calcular otros mayores a partir de éstos:

   function fib(n)
       var previousFib := 1, currentFib := 1
       repeat n − 1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

En ambos ejemplos, fib(2) sólo se ha calculado una vez, y a continuación se ha usado para calcular tanto fib(4) como fib(3), en lugar de calcularlo cada vez que era evaluado.

[editar] Ejercicios resueltos con Programación Dinámica

• Ejecución de n tareas en tiempo mínimo en un sistema de dos procesadores A y B
• Programas en disco
• Problema de los sellos con programación dinámica
• Problema de la mochila con programación dinámica
• Problema del producto de una secuencia de matrices con programación dinámica
• Problema de las monedas con programación dinámica
• Camino de coste mínimo entre dos nodos de un grafo dirigido
• Problema de la división de peso
• Problema de las vacas con programación dinámica