PROGRAMACIN DINMICA

Pedro Romn Infante

15-0298
Luis R. Snchez
15-0589
Universidad Iberoamericana
Anlisis y Diseo de Algoritmos
Prof. Rina Familia

Resumen
Con este estudio se pretende mostrar de una manera clara el concepto y desarrollo de la programacin
dinmica que es un procedimiento diseado bsicamente, para mejorar la eficiencia de clculo de la solucin
de ciertos problemas matemticos, a travs de su segundo miembro en problema de menor tamao y, por
consiguiente, ms manejable. Sin embargo debemos destacar que el principio de optimizar ofrece una
estructura bien definidas para resolver el problema en etapas.
El principio de optimizar se considera algunas veces demasiado poderoso para ser de utilidad en la prctica;
pero aunque un problema se puede dividir adecuadamente en partes menores quizs an no se pueda obtener
una respuesta numrica, debido a la complejidad del proceso de optimizacin en cada etapa.
No obstante, debemos sealar que a pesar de esta desventaja, la solucin de muchos problemas se ha
facilitado apreciablemente a travs del uso de la programacin dinmica.

I.

INTRODUCCION

a programacin dinmica es un mtodo o

procedimiento para reducir el tiempo de
ejecucin de un algoritmo mediante una
tcnica cuantitativa de tomar decisiones. Su mayor
campo de aplicacin se encuentra en la resolucin de
problemas de optimizacin, los cuales se basan en
encontrar una solucin de valor ptimo, es decir,
mximo o mnimo, a partir de distintas soluciones
con valores diferentes. As, la programacin
dinmica se puede definir como una tcnica
matemtica til que resuelve una serie de decisiones

secuenciales, cada una de las cuales afecta las

decisiones futuras. Proporciona un procedimiento
sistemtico para determinar la combinacin de
decisiones que maximiza la efectividad total (Taha,
2004).
Este trmino fue utilizado originalmente por el
matemtico Richard Bellman en la dcada de los 40
con el objetivo de describir el proceso donde se
necesita encontrar las mejores decisiones, una tras
otra. Ms tarde, Bellman refino el significado del
trmino,
estableciendo
que
se
refiere
especficamente a anidar pequeos problemas de
decisin dentro de grandes decisiones.

Junto al profesor George Dantzig public en 1957

Dynamic Programming (Princeton University
Press. Princeton, New Jersey)(Domnguez, 2000), en
el cual realiz sus ms importantes contribuciones
sobre esta tcnica cuantitativa de toma de decisiones.
La programacin dinmica no cuenta con una
formulacin matemtica estndar, sino que se trata
de un enfoque de tipo general para la solucin de
problemas, por lo tanto, las ecuaciones especficas
que se utilizan se deben desarrollar para que
representen cada situacin individual. Regularmente,
resuelve el problema por etapas, en donde cada etapa
interviene
exactamente
una
variable
de
optimizacin.
Para resolver problemas de programacin dinmica
se necesita un grado de creatividad, al igual que un
buen conocimiento de la estructura general de los
problemas de programacin dinmica para reconocer
cuando un problema se puede resolver por medio de
estos procedimientos y cmo esto se puede llevar a
cabo.
En el siguiente trabajo de investigacin se
presentarn los fundamentos de la programacin
dinmica, sus caractersticas y casos de estudio
donde se aplica la programacin dinmica con el
propsito de optimizar los procesos.

Cada etapa tiene un cierto nmero de estados

asociados a ella. Por estados se entiende la
informacin que se necesita en cualquier
etapa para tomar una decisin ptima.
El procedimiento de solucin est diseado
para encontrar una poltica ptima para el
problema completo, es decir, una receta para
las decisiones de la poltica ptima en cada
etapa para cada uno de los estados posibles.
Dado el estado actual, una poltica ptima
para las etapas restantes es independiente de
la poltica adoptada en etapas anteriores (este
es el principio de optimalidad para la
programacin dinmica). En general, en los
problemas de P.D. el conocimiento del estado
actual del sistema expresa toda la
informacin sobre su comportamiento
anterior, y esta informacin es necesaria para
determinar la poltica ptima de ah en
adelante.
El procedimiento de solucin se inicia al
encontrar la poltica ptima para la ltima
etapa. La poltica ptima para la ltima etapa
prescribe la poltica ptima de decisin para
cada estado posible en esa etapa.
Se dispone de una relacin recursiva que
indica la poltica ptima para la etapa dada la
poltica ptima para la etapa(n+1).

CARACTERISTICAS DE LA
PROGRAMACION DINAMICA

II.

Las caractersticas de la programacin dinmica se

emplean para formular e identificar la estructura de
los problemas de este tipo. Podemos distinguir los
problemas de programacin dinmica por las
siguientes caractersticas:

El problema se puede dividir en etapas que

requieren una poltica de decisin en cada
una de ellas. En muchos problemas de
programacin dinmica, la etapa es la
cantidad de tiempo que pasa desde el inicio
del problema, en ciertos casos no se necesitan
decisiones en cada etapa.

A pesar de esta caracterstica, los problemas que

pueden ser atacados con la programacin dinmica
tienen dos propiedades adicionales:

Solo un nmero reducido de variables se debe

conocer en cualquier etapa con el fin de
describir al problema.

El resultado de una decisin en cualquier

etapa altera los valores numricos de un
nmero reducido de variables relevantes al
problema. La decisin actual ni incrementa ni
decrementa el nmero de factores sobre los
cuales depende el resultado.
III.

PRINCIPIO DE OPTIMALIDAD DE
BELLMAN

Cuando se habla de optimizar, se refiere a tomar una

buena solucin entre muchas otras soluciones
posibles. Lo interesante de este principio es que se
toma una decisin en cada paso, pero sta depende
de las soluciones a los que depende de las soluciones
a los subproblemas subproblemas que lo componen.
No obstante, el principio de optimalidad no dice que
si encontramos la solucin ptima de los
subproblemas significa que combinando dichas
soluciones obtendremos nuestra solucin para el
problema original.
Ejemplo:
Cambio en monedas
La solucin ptima para 0.07 euros es 0.05 + 0.02
euros.
La solucin solucin ptima para 0.06 euros es 0.05
+ 0.01 euros.
La solucin ptima para 0.13 euros no es (0.05 + 2)
+ (0.05 + 0.01) euros.
Es indispensable encontrar la estructura de la
solucin para saber si a esta se le puede aplicar el
Principio de Bellman. Luego se define
recursivamente la solucin ptima del problema (en
funcin de los valores de las soluciones para los
subproblemas de menor tamao). Despus, se va
calculando el valor de la solucin ptima utilizando
un enfoque ascendente. Finalmente, se van
calculando los valores de soluciones ms complejas
a partir de los valores previamente calculados y
almacenados en una tabla.

A continuacin podremos observar distintos casos de

la aplicacin de la programacin dinmica y el
principio de optimalidad de Bellman.
IV.

CALCULO DE LOS NUMEROS DE

FIBONACCI

Antes de abordar problemas ms complejos veamos

un primer ejemplo en el cual va a quedar reflejada
toda esta problemtica. Se trata del clculo de los
trminos de la sucesin de nmeros de Fibonacci.
Dicha sucesin podemos expresarla recursivamente
en trminos matemticos de la siguiente manera:
Fib(n) = 1
si n = 0,1
Fib(n-1) + Fib(n-2)
si n >1
Por tanto, la forma ms natural de calcular los trminos
de esa sucesin 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 problema ocurre en que el algoritmo resultante es poco
eficiente, ya que su tiempo de ejecucin es de orden
exponencial. La falta de eficiencia de este algoritmo se
debe a que se producen llamadas recursivas repetidas para
calcular valores de la sucesin, que habindose calculado
previamente, no se conserva el resultado y por tanto es
necesario volver a calcular cada vez.
Para este problema es posible disear un algoritmo que en
tiempo lineal lo resuelva mediante la construccin de una
tabla que permite ir almacenando los clculos realizados
hasta el momento para poder reutilizarlos:
Fib(0) Fib(1) Fib(2) ... Fib(n)
El algoritmo iterativo que calcula la sucesin de
Fibonacci utilizando tal tabla es:
TYPE
TABLA = ARRAY [0..n] OF CARDINAL

PROCEDURE
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;
V.

FibIter(VAR

EL VIAJE MS BARATO POR RO

Sobre el ro Guadalhorce hay n embarcaderos. En

cada uno de ellos se puede alquilar un bote que
permite ir a cualquier otro embarcadero ro abajo (es
imposible ir ro arriba). Existe una tabla de tarifas
que indica el coste del viaje del embarcadero i al j
para cualquier embarcadero de partida i y cualquier
embarcadero de llegada j ms abajo en el ro (i < j).
Puede suceder que un viaje de i a j sea ms caro que
una sucesin de viajes ms cortos, en cuyo caso se
tomara un primer bote hasta un embarcadero k y un
segundo bote para continuar a partir de k. No hay
coste adicional por cambiar de bote.
Nuestro problema consiste en disear un algoritmo
eficiente que determine el coste mnimo para cada
par de puntos i,j (i < j) y determinar, en funcin de n,
el tiempo empleado por el algoritmo.
Llamaremos T[i,j] a la tarifa para ir del embarcadero
i al j (directo). Estos valores se almacenarn en una
matriz triangular superior de orden n, siendo n el
nmero de embarcaderos.
El
problema
puede
resolverse
mediante
Programacin Dinmica ya que para calcular el coste
ptimo para ir del embarcadero i al j podemos
hacerlo de forma recurrente, suponiendo que la
primera parada la realizamos en un embarcadero
intermedio
k (i < k j):
C(i,j) = T(i,k) + C(k,j).

En esta ecuacin se contempla el viaje directo, que

corresponde al caso en el que k coincide con j. Esta
ecuacin verifica tambin que la solucin buscada
C(i,j) satisface el principio del ptimo, pues el coste
C(k,j), que forma parte de la solucin, ha de ser, a su
vez, ptimo. Podemos plantear entonces la siguiente
expresin de la solucin:
C(i,j) = 0
si i = j
Min( i<k<=j ) {T(i,k) + C(k,j)}
si i <j
La idea de esta segunda expresin surge al observar
que en cualquiera de los trayectos siempre existe un
primer salto inicial ptimo.
Para resolverla segn la tcnica de Programacin
Dinmica, hace falta utilizar una estructura para
almacenar resultados intermedios y evitar la
repeticin de los clculos. La estructura que
usaremos es una matriz triangular de costes C[i,j],
que iremos rellenando por diagonales mediante el
procedimiento que hemos denominado Costes. La
solucin al problema es la propia tabla, y sus valores
C[i,j] indican el coste ptimo para ir del embarcadero
i al j.
CONST MAXEMBARCADEROS = ...;
TYPE
MATRIZ=ARRAY[1..MAXEMBARCADEROS],[
1..MAXEMBARCADEROS] OF CARDINAL;
PROCEDURE
Costes(VAR
C:MATRIZ;n:CARDINAL);
VAR i, diagonal:CARDINAL;
BEGIN
FOR i:=1 TO n DO C[i,i]:=0 END; (* condiciones
iniciales *)
FOR diagonal:=1 TO n-1 DO
FOR i:=1 TO n-diagonal DO
C[i,i+diagonal]:=Min(C,i,i+diagonal)
END
END
END Costes;
Dicho procedimiento utiliza la siguiente funcin, que
permite calcular la expresin del mnimo que aparece
en la ecuacin en recurrencia:
PROCEDURE
Min(VAR
i,j:CARDINAL):CARDINAL;
VAR k,min:CARDINAL;

C:MATRIZ;

BEGIN
min:=MAX(CARDINAL);
FOR k:=i+1 TO j DO
min:=Min2(min,T[i,k] + C[k,j])
END;
RETURN min
END Min;
La funcin Min2 es la que calcula el mnimo de dos
nmeros naturales. Es importante observar que esta
funcin, por la forma en que se va rellenando la
matriz C, slo hace uso de los elementos calculados
hasta el momento.
La complejidad del algoritmo es de orden O(n3),
pues est compuesto por dos bucles anidados de
tamao n, que contienen la llamada a una funcin de
orden O(n), la que calcula el mnimo.

VI.

CONCLUSIONES

El estudio presentado en este artculo nos permiti

ampliar nuestro conocimiento respecto a cmo
resolver una problemtica en el menor tiempo
posible para encontrar una solucin ptima
utilizando programacin dinmica. Se encontr que
la programacin dinmica mayormente se basa en el
principio de Bellman y su forma de acercarse a un
problema y resolverlo por subpartes.
Por otra parte, se encontraron los distintos casos
donde se poda aplicar el principio de Bellman como
son los nmeros de Fibonacci y el viaje ms barato
por ro. En ambos casos para encontrar la solucion
era mas preciso hacer los clculos de forma
recursiva. Cuando utilizamos una funcin recursiva
nos pudimos dar cuenta que es ms eficiente ir
almacenando los nmeros en una tabla para poder
utilizarlos nuevamente, as ahorrando tiempo para el
algoritmo correr y conseguir el resultado en menor
tiempo. Adems, que la programacin dinmica nos
sugiere evitar repetir calculaciones hechas
anteriormente.
Pudimos ver que el principio de Bellman tiene sus
limitaciones ya que no podemos resolver un
problema que no est bien estructurado de forma
recursiva para llegar a la solucin ptima ya que esto
hara que el algoritmo tome ms tiempo ejecutndose
y puede que no encuentre una solucin final del
problema original debido a que no hay una buena
estructura definida para ser resuelto recursivamente
por subpartes.
La programacin dinmica es una tcnica
matemtica til que resuelve una serie de decisiones
secuenciales, cada una de las cuales afecta las
decisiones finales. Proporciona un procedimiento
sistemtico para determinar la combinacin de
decisiones que maximiza la efectividad total. Pero,

se debe tener en cuenta que una tabla es fundamental

para su funcionamiento eficiente.
Finalmente, se pudo presentar la base de la
programacin dinmica, sus caractersticas y casos
reales de estudio donde se puede apreciar la
programacin dinmica con la finalidad de optimizar
los procesos.
REFERENCIAS

(2007, 01). Programacin Dinmica. LCC. Obtenido

07,
2016,
de
http://www.lcc.uma.es/~av/Libro/CAP5.pdf
Chan, E. (2012, 11). Unidad V. Programacin
Dinmica. Slideshare. Obtenido 07, 2016, de
http://es.slideshare.net/elmergabrielchanpech/progra
macin-dinmica-15433493
Rodriguez, P. (2012, 10). Programacin Dinmica.
Buenas Tareas. Obtenido 07, 2016, de
http://www.buenastareas.com/ensayos/Programaci
%C3%B3n-Dinamica/6120435.html
Campos, J. (2013, 01). Esquemas algoritmicos.
Programacion Dinamica. Unizar. Obtenido 07, 2016,
de
http://webdiis.unizar.es/asignaturas/EDA/ea/slides/4
-Programacin %20dinamica.pdf
Flores, I. (2015, 04). Programacion Dinamica.
Ingenieria. UNAM. Obtenido 07, 2016, de
http://www.ingenieria.unam.mx/sistemas/PDF/Avis
os/Seminarios/SeminarioV/Sesion6_IdaliaFlores_20
abr15.pdf
Ojea, M. (2006, 06). Programacion Dinamica. CMS.
Obtenido
07,
2016,
de
http://cms.dm.uba.ar/materias/1ercuat2009/optimiza
cion/Maurette_Ojea.pdf