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

• Un artículo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquí).
• Un par de capítulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por fusión (acceso con clave aquí y aquí).
• La demostración de que el coste promedio del quicksort está en n log n (acceso con clave aquí).
• Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet.

  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 

El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(n^{log 3})  ( ≈ O(n^1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de la extinta Unión Soviética (Doklady Akademii Nauk SSSR) en 1962.

Curiosamente, el mencionado artículo no fue escrito por Anatoli Alekséyevich Karatsuba (Grozny, URSS, 31 de enero de 1937 — Moscú, Rusia, 28 de septiembre de 2008) sino que, tal y como relata él mismo en su artículo “The complexity of computations” (publicado en Proceedings of the Steklov Mathematical Institute, vol. 211, pp. 169-183, 1995, copia local con clave aquí), fue escrito por Kolmogorov, probablemente ayudado por Ofman, y sin el conocimiento de Karatsuba, quien era realmente el autor del algoritmo:

[...] Later in 1962 Kolmogorov wrote a short article (probably in collaboration with Ofman) and published it in Doklady Akad. Nauk SSSR. The article was entitled: A. Karatsuba and Y. Ofman, “Multiplication of Multiplace Numbers on Automata” (Doklady Akad. Nauk SSSR, vol. 145, No. 2, pp. 293-294). I learned about the article only when I was given its reprints.

En el mismo artículo de 1995, Karatsuba reivindica su autoría:

In this section I present my algorithm for multiplying numbers. Now it is called the KML algorithm or, briefly, KML (Karatsuba Multiplication).

Anatoli Alekséyevich Karatsuba

Con posterioridad, se han desarrollado algoritmos asintóticamente más rápidos que el de Karatsuba, como el de Schönhage–Strassen (1971), de coste Θ(n log(n) log(log(n))), o el de Martin Fürer (2007), de coste n log(n) 2^Θ(log*(n)).

• Un artículo que describe un par de métodos de ordenación por fusión (o mezcla) “in situ” y analiza su coste (acceso con clave aquí).
• Un par de capítulos de libros sobre métodos de ordenación en memoria externa basados en la idea de la ordenación por fusión (acceso con clave aquí y aquí).
• La demostración de que el coste promedio del quicksort está en n log n (acceso con clave aquí).
• Comparación práctica de velocidades de métodos de ordenación: un applet, otro applet.

Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009

Aquí y aquí.