Toda solución de programación dinámica evita usar una solución top-down recursiva que directamente traduzca a un algoritmo la ecuación recurrente correspondiente al problema. Esto es así porque, normalmente, el coste en tiempo de esa solución es extremadamente alto pues resuelve muchas veces los mismos subproblemas.

Para evitar resolver muchas veces los mismos subproblemas, un algoritmo de programación dinámica utiliza siempre una tabla auxiliar, en la que se almacenan las soluciones de los subproblemas conforme se van resolviendo.

Dicho esto, hay dos formas distintas de implementar la solución de programación dinámica:

• Solución de abajo arriba (bottom-up) iterativa, en la que se van resolviendo todos los subproblemas y rellenando la tabla en un cierto orden, iterativamente, en primer lugar resolviendo los casos base de la recursión y después el resto de los casos aplicando la ecuación recurrente “ordenadamente”, de manera que cuando se necesiten las soluciones de ciertos subproblemas (en cierto sentido, “más pequeños”) para resolver otros, éstas hayan sido resueltas y almacenadas en la tabla con anterioridad en el(los) bucle(s) correspondiente(s) del algoritmo. Ejemplos de estas soluciones son las de los problemas de la mochila 0-1, el camino de coste mínimo en un grafo multietapa o la multiplicación de una secuencia de matrices, vistas ya en clase.
• Solución (recursiva) de arriba abajo (top-down) con memorialización (memoization), en la que se aplica directamente la ecuación recurrente, como en la solución top-down recursiva (mencionada antes y descartada por muy ineficiente), pero cada vez que se resuelve un subproblema, se almacena su solución en la tabla auxiliar para evitar volver a resolverlo de nuevo más adelante. De esta forma, lo primero que hace el algoritmo es averiguar si el subproblema ha sido ya resuelto consultando la tabla, y sólo si no se ha resuelto todavía, se aplica la ecuación recurrente para resolverlo (de forma recursiva). Un ejemplo de este tipo de solución es la del problema del viajante de comercio, vista ya en clase.

El coste asintótico de ambos métodos suele ser el mismo, salvo en algunos casos (poco frecuentes) en los que la solución de arriba abajo no necesita resolver todos los subproblemas de la tabla. En general, la solución de abajo arriba ofrece mejores resultados prácticos al tener constantes multiplicativas más pequeñas, pues se evita el sobrecoste provocado por las llamadas recursivas. Por eso recomendamos, siempre que sea posible, plantear una solución de abajo arriba iterativa.

Lectura adicional (acceso restringido): ejemplo del recorte óptimo de varillas y sus dos soluciones de programación dinámica (arriba abajo con memorialización versus abajo arriba iterativa), del libro [CLRS09].

Son para trabajarlos en casa antes del 31 de marzo.

No es extraño que en entrevistas de trabajo relacionadas con la Computación aparezcan problemas resolubles mediante programación dinámica.

Aquí hay algunos de ellos:

What are the top 10 most popular dynamic programming problems among interviewers?

Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática:

1. Dynamic Programming and Graph Algorithms in Computer Vision: A Survey.
2. Dynamic programming and board games: A survey (acceso restringido con usurio/clave).
3. Some dynamic programming problems useful to solve the mobile robot localization problem.
4. Systematic Dynamic Programming in Bioinformatics.

Se ha publicado en la web (sección problemas) una hoja de problemas sobre algoritmos de programación dinámica (usuario y contraseña, los dados el primer día de clase).

Se ha publicado una hoja de problemas sobre algoritmos de programación dinámica.

  si D[i,k]+D[k,j]<D[i,j] entonces
    D[i,j]:=D[i,k]+D[k,j];
    C[i,j]:=k
  fsi

La matriz se ha debido inicializar al principio del algoritmo (por ejemplo con valores nulos). El algoritmo para el cálculo del camino mínimo de i a j, usando la matriz C, queda como:

  procedimiento camino(ent i,j:vértice;
                       ent C:vector[vértice,vértice] de entero)
  variable k:vértice
  principio
    k:=C[i,j];
    si k≠0 entonces
      camino(i,k,C);
      escribir(k);
      camino(k,j,C)
    fsi
  fin

Las soluciones de programación dinámica aparecen en prácticamente todos los dominios de aplicación. Seleccionamos aquí algunos ejemplos en Visión, Juegos, Robótica y Bioinformática:

1. Dynamic Programming and Graph Algorithms in Computer Vision: A Survey.
2. Dynamic programming and board games: A survey (acceso restringido con usurio/clave).
3. Some dynamic programming problems useful to solve the mobile robot localization problem.
4. Systematic Dynamic Programming in Bioinformatics.

La definición de la sucesión o función de Fibonacci es:

Fib(n) = 1, si n = 0,1

Fib(n) = Fib(n-1) + Fib(n-2), si n > 1

La solución más natural para calcular el término n-ésimo sería, por tanto, traducir esa definición recursiva de la función a nuestro pseudocódigo:

  función FibRec(n:natural) devuelve natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      devuelve FibRec(n-1)+FibRec(n-2)
    fsi
  fin

El inconveniente de esa solución es su coste, exponencial en el valor de n. La ineficiencia de FibRec se debe a que se producen llamadas repetidas de la función para calcular valores que ya se habían calculado previamente, no se ha conservado su resultado, y por tanto hay que volver a calcularlos.

La solución de programación dinámica pasaría por utilizar una tabla auxiliar en la que almacenar las soluciones de todos los “subproblemas” (valores de Fib para valores menores que n) resueltos:

El algoritmo iterativo para devolver el n-ésimo término de Fibonacci calculando la tabla sería:

  función FibIterProto(n:natural) devuelve natural
  variables i:natural; T:vector[0..n] de natural
  principio
    si n≤1 entonces
      devuelve 1
    sino
      T[0]:=1;
      T[1]:=1;
      para i:=2 hasta n hacer
        T[i]:=T[i-1]+T[i-2]
      fpara;
      devuelve T[n]
    fsi
  fin 

El último paso en la mejora proviene de detectar que en el algoritmo anterior no es necesario todo el vector auxiliar, pues basta con almacenar los dos últimos valores calculados:

  función FibIter(n:natural) devuelve natural
  variables i,suma,x,y:natural {x e y para almacenar los dos últimos
                 términos calculados y suma para almacenar el actual}
  principio
    si n≤1 entonces
      devuelve 1
    sino
      x:=1;
      y:=1;
      para i:=2 hasta n hacer
        suma:=x+y;
        y:=x;
        x:=suma
      fpara;
      devuelve suma
    fsi
  fin