PDF de programación - Capítulo 5 - PROGRAMACIÓN DINÁMICA

Capítulo 5

PROGRAMACIÓN DINÁMICA

5.1 INTRODUCCIÓN
Existe una serie de problemas cuyas soluciones pueden ser expresadas
recursivamente en términos matemáticos, y posiblemente la manera más natural de
resolverlos es mediante un algoritmo recursivo. Sin embargo, el tiempo de
ejecución de la solución recursiva, normalmente de orden exponencial y por tanto
impracticable, puede mejorarse substancialmente mediante la Programación
Dinámica.
En el diseño Divide y Vencerás del capítulo 3 veíamos cómo para resolver un
problema lo dividíamos en subproblemas independientes, los cuales se resolvían de
manera recursiva para combinar finalmente las soluciones y así resolver el
problema original. El inconveniente se presenta cuando los subproblemas
obtenidos no son independientes sino que existe solapamiento entre ellos; entonces
es cuando una solución recursiva no resulta eficiente por la repetición de cálculos
que conlleva. En estos casos es cuando la Programación Dinámica nos puede
ofrecer una solución aceptable. La eficiencia de esta técnica consiste en resolver
los subproblemas una sola vez, guardando sus soluciones en una tabla para su
futura utilización.
La Programación Dinámica no sólo tiene sentido aplicarla por razones de
eficiencia, sino porque además presenta un método capaz de resolver de manera
eficiente problemas cuya solución ha sido abordada por otras técnicas y ha
fracasado.
Donde tiene mayor aplicación la Programación Dinámica es en la resolución de
problemas de optimización. En este tipo de problemas se pueden presentar distintas
soluciones, cada una con un valor, y lo que se desea es encontrar la solución de
valor óptimo (máximo o mínimo).
La solución de problemas mediante esta técnica se basa en el llamado principio
de óptimo enunciado por Bellman en 1957 y que dice:
“En una secuencia de decisiones óptima toda subsecuencia ha de ser también
óptima”.
Hemos de observar que aunque este principio parece evidente no siempre es
aplicable y por tanto es necesario verificar que se cumple para el problema en
cuestión. Un ejemplo claro para el que no se verifica este principio aparece al tratar
de encontrar el camino de coste máximo entre dos vértices de un grafo ponderado.

178

TÉCNICAS DE DISEÑO DE ALGORITMOS

Para que un problema pueda ser abordado por esta técnica ha de cumplir dos
condiciones:
• La solución al problema ha de ser alcanzada a través de una secuencia de

decisiones, una en cada etapa.

• Dicha secuencia de decisiones ha de cumplir el principio de óptimo.



En grandes líneas, el diseño de un algoritmo de Programación Dinámica consta
de los siguientes pasos:
1. Planteamiento de la solución como una sucesión de decisiones y verificación de

que ésta cumple el principio de óptimo.

2. Definición recursiva de la solución.
3. Cálculo del valor de la solución óptima mediante una tabla en donde se

almacenan soluciones a problemas parciales para reutilizar los cálculos.

4. Construcción de la solución óptima haciendo uso de la información contenida

en la tabla anterior.



5.2 CÁLCULO DE LOS NÚMEROS DE FIBONACCI
Antes de abordar problemas más complejos veamos un primer ejemplo en el cual
va a quedar reflejada toda esta problemática. Se trata del cálculo de los términos de
la sucesión de números de Fibonacci. Dicha sucesión podemos expresarla
recursivamente en términos matemáticos de la siguiente manera:
si n = 0,1
si n >1


Fib(n) = 1

Fib(n−1)+ Fib(n− 2)




Por tanto, la forma más natural de calcular los términos de esa sucesión es
mediante un programa recursivo:


PROCEDURE FibRec(n:CARDINAL):CARDINAL;
BEGIN
IF n<=1 THEN RETURN 1
ELSE
RETURN FibRec(n-1) + FibRec(n-2)
END
END FibRec;


El inconveniente es que el algoritmo resultante es poco eficiente ya que su
tiempo de ejecución es de orden exponencial, como se vió en el primer capítulo.
Como podemos observar, la falta de eficiencia del algoritmo se debe a que se
producen llamadas recursivas repetidas para calcular valores de la sucesión, que
habiéndose calculado previamente, no se conserva el resultado y por tanto es
necesario volver a calcular cada vez (véase el apartado 3.11 del capítulo 3, en
donde se determina el número exacto de veces que se repite cada cálculo).

PROGRAMACIÓN DINÁMICA



179

Para este problema es posible diseñar un algoritmo que en tiempo lineal lo
resuelva mediante la construcción de una tabla que permita ir almacenando los
cálculos realizados hasta el momento para poder reutilizarlos:


Fib(0)

Fib(1)

Fib(2)

...

Fib(n)


El algoritmo iterativo que calcula la sucesión de Fibonacci utilizando tal tabla es:


TYPE TABLA = ARRAY [0..n] OF CARDINAL
PROCEDURE FibIter(VAR T:TABLA;n:CARDINAL):CARDINAL;
VAR i:CARDINAL;
BEGIN
IF n<=1 THEN RETURN 1
ELSE
T[0]:=1;
T[1]:=1:
FOR i:=2 TO n DO
T[i]:=T[i-1]+T[i-2]
END;
RETURN T[n]
END
END FibIter;


Existe aún otra mejora a este algoritmo, que aparece al fijarnos que únicamente
son necesarios los dos últimos valores calculados para determinar cada término, lo
que permite eliminar la tabla entera y quedarnos solamente con dos variables para
almacenar los dos últimos términos:


PROCEDURE FibIter2(n: CARDINAL):CARDINAL;
VAR i,suma,x,y:CARDINAL; (* x e y son los 2 ultimos terminos *)
BEGIN
IF n<=1 THEN RETURN 1
ELSE
x:=1; y:=1;
FOR i:=2 TO n DO
suma:=x+y; y:=x; x:=suma;
END;
RETURN suma
END
END FibIter2;


Aunque esta función sea de la misma complejidad temporal que la anterior
(lineal), consigue una complejidad espacial menor, pues de ser de orden O(n) pasa
a ser O(1) ya que hemos eliminado la tabla.
El uso de estructuras (vectores o tablas) para eliminar la repetición de los
cálculos, pieza clave de los algoritmos de Programación Dinámica, hace que en

180

TÉCNICAS DE DISEÑO DE ALGORITMOS

este capítulo nos fijemos no sólo en la complejidad temporal de los algoritmos
estudiados, sino también en su complejidad espacial.
En general, los algoritmos obtenidos mediante la aplicación de esta técnica
consiguen tener complejidades (espacio y tiempo) bastante razonables, pero
debemos evitar que el tratar de obtener una complejidad temporal de orden
polinómico conduzca a una complejidad espacial demasiado elevada, como
veremos en alguno de los ejemplos de este capítulo.


5.3 CÁLCULO DE LOS COEFICIENTES BINOMIALES
En la resolución de un problema, una vez encontrada la expresión recursiva que
define su solución, muchas veces la dificultad estriba en la creación del vector o la
tabla que ha de conservar los resultados parciales. Así en este segundo ejemplo,
aunque
tabla
bidimensional algo más compleja. Se trata del cálculo de los coeficientes
binomiales, definidos como:

también sencillo, observamos que vamos a necesitar una

n
k






=


n
k





1

−
−

1
1


+


 −
n

k


0 si






<<

k

n

,

n
0





=





n
n


=


1

.

El algoritmo recursivo que los calcula resulta ser de complejidad exponencial
por la repetición de los cálculos que realiza. No obstante, es posible diseñar un
algoritmo con un tiempo de ejecución de orden O(nk) basado en la idea del
Triángulo de Pascal. Para ello es necesario la creación de una tabla bidimensional
en la que ir almacenando los valores intermedios que se utilizan posteriormente:



0
1
2
3
...
...
n-1

n

0
1
1
1
1
...
...



1

1
2
3
...
...



2


1
3
...
...



3



1
...
...



...



...
...



k-1



...
C(n-1,k-1) + C(n-1,k)

k



C(n,k)



derecha mediante el siguiente algoritmo de complejidad polinómica:

Iremos construyendo esta tabla por filas de arriba hacia abajo y de izquierda a


PROCEDURE CoefIter(n,k: CARDINAL):CARDINAL;
VAR i,j: CARDINAL;
C: TABLA;
BEGIN

PROGRAMACIÓN DINÁMICA



181

FOR i:=0 TO n DO C[i,0]:=1 END;
FOR i:=1 TO n DO C[i,1]:=i END;
FOR i:=2 TO k DO C[i,i]:=1 END;
FOR i:=3 TO n DO
FOR j:=2 TO i-1 DO
IF j<=k THEN
C[i,j]:=C[i-1,j-1]+C[i-1,j]
END
END
END;
RETURN C[n,k]
END CoefIter.



5.4 LA SUBSECUENCIA COMÚN MÁXIMA
Hay muchos problemas para los cuales no sólo deseamos encontrar el valor de la
solución óptima sino que además deseamos conocer cuál es la composición de esta
solución, es decir, los elementos que forman parte de ella. En estos casos es
necesario ir conservando no sólo los valores de las soluciones parciales, sino
también cómo se llega a ellas. Esta información adicional puede ser almacenada en
la misma tabla que las soluciones parciales, o bien en otra tabla al efecto.
Veamos un ejemplo en el que se crea una tabla y a partir de ella se reconstruye
la solución. Se trata del cálculo de la subsecuencia común máxima. Vamos en
primer lugar a definir el problema.
Dada una secuencia X={x1 x2 ... xm}, decimos que Z={z1 z2 ... zk} es una
subsecuencia de X (siendo k ≤ m) si existe una secuencia creciente {i1 i2 ... ik} de
índices de X tales que para todo j = 1, 2, ..., k tenemos xij = zj.
Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y
si es subsecuencia de X y subsecuencia de Y. Deseamos determinar la subsecuencia
de longitud máxima común a dos secuencias.

()
Solución
Llamaremos L(i,j) a la longitud de la s