Algoritmia/Programación dinámica

La programación dinámica puede verse como una optimización de otros métodos algorítmicos (Divide y vencerás, Vuelta atrás, ...) en los que una solución a un problema puede implicar la repetición continua de subproblemas. En concreto, la programación dinámica suele implicar la utilización de una tabla auxiliar donde almacenar las soluciones a los subproblemas ya calculados, de tal forma que cada subsolución se calcule una única vez, reduciendo así el coste en tiempo a cambio de coste en espacio (almacenamiento en memoria de la tabla).

El término dinámico proviene de que la tabla auxiliar se rellena en tiempo de ejecución. No debe confundirse la programación dinámica en el ámbito algorítmico con los lenguajes de programación dinámicos, como Scheme o Lisp.

Ejemplo: la sucesión de Fibonacci

La primera implementación de una función para encontrar el n-ésimo término de la sucesión de Fibonacci que surge de forma natural, es la basada en la definición matemática de la misma:

fun fib(n)
    si n = 0 || n = 1
        devolver n
    si no
        devolver fib(n - 1) + fib(n - 2)
    fsi
ffun

No es difícil comprobar la cantidad de cálculo redundante a que conduce este primer acercamiento al problema. Si llamamos, por ejemplo, a fib (5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:

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

Si se considera ahora la utilización de un simple array para almacenar la solución a los distintos subproblemas, la función resultante será de complejidad lineal, en lugar de exponencial, pues cada fib(n) se calcula una única vez:

var tabla : array [0..n] de ent
fun fib(n)
   si tabla[n] = -1 entonces               // El array inicializado a -1
       tabla[n] := fib(n - 1) + fib(n - 2)
   fsi
   devolver tabla[n]
ffun

Esta implementación está hecha desde arriba (top-down en inglés), solicitando primero la solución del problema y calculando recursivamente las soluciones a los subproblemas. Una implementación desde abajo (bottom-up en inglés) consiste en realizar el proceso inverso: calcular primero la solución a los subproblemas y a partir de las mismas, definir la solución al problema.

Problemas resueltos

Ejemplo: la sucesión de Fibonacci

Problemas resueltos

Ejecución de n tareas en tiempo mínimo

Problema de los sellos

Problema de la mochila

Problema del producto de una secuencia de matrices

Problema de las monedas

Problema del coste mínimo entre dos nodos de un grafo dirigido

Problema de la división de peso

Problema de las vacas