.

Probablemente este miércoles podamos empezar a trabajar en clase con los problemas de la hoja de programación dinámica. Pero únicamente lo haremos si los habéis trabajado antes vosotros…

Para plantear una solución de programación dinámica, normalmente, deben seguirse los pasos siguientes:

1. Definir de manera precisa una función parametrizada tal que, para algunos valores de sus parámetros, nos aporte la solución del problema originalmente propuesto.
2. Escribir una ecuación recurrente (o relación de recurrencia) para esa función parametrizada, detallando para qué valores de sus parámetros es válida la ecuación, y escribir los casos base de la función (casos particulares de sus parámetros para los que se puede expresar el valor de la función sin necesidad de recurrencias).
3. Detallar qué tabla es necesaria para almacenar los valores de la función parametrizada, y qué orden puede seguirse para calcularla. Detallar si se precisa alguna otra tabla auxiliar para reconstruir la solución para la que la función alcanza el óptimo.
4. Escribir en pseudocódigo el algoritmo para rellenar la tabla de los valores óptimos de la función parametrizada y, si se solicita, escribir el algoritmo para construir la solución para la que se alcanza el óptimo del problema original.

Ejemplo de aplicación de estos pasos para el problema de “Multiplicación de una secuencia de matrices” (transparencias 31 a 40 de clase):

1. Función m(i,j) = número mínimo de multiplicaciones de escalares necesarias para multiplicar la subsecuencia de matrices M_i, …, M_j.
   El problema originalmente propuesto es calcular m(1,n).
2. m(i,i) = 0, para i = 1..n (casos base).
   m(i,j) = min_1≤k<j {m(i,k)+m(k+1,j)+d_i-1d_kd_j}, para todos los i, j tales que 1≤i<j≤n.
3. Matriz triangular superior para almacenar los m(i,j), con 1≤i≤j≤n. Puede calcularse por diagonales, empezando por la diagonal principal y, desde ahí, hacia arriba.
   Matriz auxiliar de iguales dimensiones para almacenar los índices k para los que se consigue el mínimo de la ecuación recurrente para cada uno de los m(i,j). Es la matriz km[i,j] en el algoritmo de la transparencia nº 38.
4. Algoritmos de la página 38 y de la página 40 de las transparencias.

¿Tenéis alguna idea para la función parametrizada (punto (1) de los anteriores) de alguno de los problemas de la hoja? El foro de Moodle es un buen sitio para compartir ideas…