SESION 3-1 Programacion Dinamica

Programación Dinámica
M.Sc. Ing. R. Fabrizio Calienes Rodriguez
◼ Introducción
◼ Elementos de la programación dinámica
◼ Principio de optimalidad de Bellman
◼ Definición recursiva de la solución óptima
◼ Cálculo de la solución óptima
◼ Ejemplos
◼ Multiplicación encadenada de matrices
◼ Subsecuencia de mayor longitud (LCS)
◼ Selección de actividades con pesos
◼ Problema de la mochila
◼ Caminos mínimos: Algoritmos de Floyd y Bellman-Ford
◼ Distancia de edición
◼ Aplicaciones 1
Esta técnica se aplica sobre problemas que presentan
las siguientes características:
◼ Subproblemas optimales: La solución óptima a un

problema puede ser definida en función de soluciones
óptimas a subproblemas de tamaño menor.
◼ Solapamiento entre subproblemas: Al plantear la

solución recursiva del problema, un mismo problema
se resuelve más de una vez.
Enfoque ascendente (bottom-up):
◼ Primero se calculan las soluciones óptimas para
problemas de tamaño pequeño.
◼ Luego, utilizando dichas soluciones, encuentra
soluciones a problemas de mayor tamaño.
Clave: Memorización
Almacenar las soluciones de los subproblemas en
alguna estructura de datos para reutilizarlas
posteriormente. De esa forma, se consigue un
algoritmo más eficiente que la fuerza bruta, que
resuelve el mismo subproblema una y otra vez.
3
Memorización
Para evitar calcular lo mismo varias veces:
◼ Cuando se calcula una solución, ésta se almacena.
◼ Antes de realizar una llamada recursiva para un
subproblema Q, se comprueba si la solución ha sido
obtenida previamente:
◼ Si no ha sido obtenida, se hace la llamada recursiva
y, antes de devolver la solución, ésta se almacena.
◼ Si ya ha sido previamente calculada, se recupera la
solución directamente (no hace falta calcularla).
◼ Usualmente, se utiliza una matriz que se rellena
conforme las soluciones a los subproblemas son
calculados (espacio vs. tiempo). 4
Uso de la programación dinámica:
1. Caracterizar la estructura de una solución óptima.
2. Definir de forma recursiva la solución óptima.
3. Calcular la solución óptima de forma ascendente.
4. Construir la solución óptima a partir de los datos

almacenados al obtener soluciones parciales.
5
Estrategias de diseño
Algoritmos greedy:
Se construye la solución incrementalmente, utilizando
un criterio de optimización local.
Programación dinámica:
Se descompone el problema en subproblemas
solapados y se va construyendo la solución con las
soluciones de esos subproblemas.
Divide y vencerás:
Se descompone el problema en subproblemas
independientes y se combinan las soluciones de
esos subproblemas.
6
Programación
Principio de Dinámica
Optimalidad
Para poder emplear programación dinámica, una
secuencia óptima debe cumplir la condición de que
cada una de sus subsecuencias también sea óptima:
Dado un problema P con n elementos,

si la secuencia óptima es e1e2...ek...en entonces:
◼ e1e2...ek es solución al problema P considerando los
k primeros elementos.
◼ ek+1...en es solución al problema P considerando los
elementos desde k+1 hasta n.
7
Principio de Optimalidad
En otras palabras:
La solución óptima de cualquier instancia no trivial

de un problema es una combinación de las soluciones
óptimas de sus subproblemas.
◼ Se busca la solución óptima a un problema

como un proceso de decisión “multietápico”.
◼ Se toma una decisión en cada paso, pero ésta

depende de las soluciones a los subproblemas
que lo componen.
8
Programación
Optimalidad
Un poco de historia: Bellman, años 50…
Enfoque está inspirado en la teoría de control:

Se obtiene la política óptima para un problema de
control con n etapas basándose en una política óptima
para un problema similar, pero de n-1 etapas.
Etimología: Programación dinámica = Planificación temporal

En una época “hostil” a la investigación matemática, Bellman
buscó un nombre llamativo que evitase posibles confrontaciones:
◼ “it's impossible to use dynamic in a pejorative sense”
◼ “something not even a Congressman could object to”
9
Richard E. Bellman: “Eye of the Hurricane: An Autobiography”
Principio de Optimalidad de Bellman
[Bellman, R.E.: “Dynamic Programming”. Princeton University Press, 1957]
“Una política óptima tiene la propiedad de que,

sean cuales sea el estado inicial y la decisión inicial,
las decisiones restantes deben constituir una solucíón
óptima con respecto al estado resultante de la primera
decisión”.
En Informática, un problema que puede descomponerse

de esta forma se dice que presenta subestructuras
optimales (la base de los algoritmos greedy y de la
programación dinámica). 10
Programación
Optimalidad
El principio de optimalidad se verifica

si toda solución óptima a un problema está compuesta
por soluciones óptimas de sus subproblemas.
¡Ojo!
El principio de optimalidad no nos dice que,
si tenemos las soluciones óptimas de los subproblemas,
entonces podamos combinarlas para obtener la solución
óptima del problema original…
11
Ejemplo: Cambio en monedas

◼ La solución óptima para 0.07 euros
es 0.05 + 0.02 euros.
es 0.05 + 0.01 euros.
no es (0.05 + 2) + (0.05 + 0.01) euros.
Sin embargo, sí que existe alguna forma de
descomponer 0.13 euros de tal forma que las
soluciones óptimas a los subproblemas nos den
12
una solución óptima (p.ej. 0.11 y 0.02 euros).
Definición del problema…
Para aplicar programación dinámica:
1. Se comprueba que se cumple el principio de

optimalidad de Bellman, para lo que hay que
encontrar la “estructura” de la solución.
2. Se define recursivamente la solución óptima del

problema (en función de los valores de las soluciones
para subproblemas de menor tamaño).
13
… y cálculo de la solución óptima
3. Se calcula el valor de la solución óptima utilizando un
enfoque ascendente:
◼ Se determina el conjunto de subproblemas que
hay que resolver (el tamaño de la tabla).
◼ Se identifican los subproblemas con una
solución trivial (casos base).
◼ Se van calculando los valores de soluciones
más complejas a partir de los valores
previamente calculados.
4. Se determina la solución óptima

a partir de los datos almacenados en la tabla.
14
ProgramaciónDinámica
Ejemplos
Sucesión de Fibonacci fib(n) = fib(n −1) + fib(n − 2)
◼ Implementación recursiva: O(n)

◼ Implementación usando programación dinámica: (n)
if (n == 0) return 0;
else if (n == 1) return 1;
else {
previo = 0; actual = 1;
for (i=1; i<n; i++) {
fib = previo + actual;
previo = actual; actual = fib;
}
return actual;
} 15
Ejemplos
Números combinatorios:
Combinaciones de n sobre p
◼ Implementación inmediata…  n  = n!
 p  p!( n − p )!
◼ Implementación usando programación dinámica…
Triángulo de Pascal
 n  =  n −1  +  n −1
 p   p −1   p 
16
Ejemplos
Números combinatorios:  n  =  n −1  + n −1 

Combinaciones de n sobre p −1
  
p p   p 
Orden de eficiencia: (np) 17

Ejemplos
Números combinatorios:  n  =  n −1  +  n −1 
Combinaciones de n sobre p
 p   p −1   p 
int combinaciones (int n, int p)
{
for (i=0; i<=n; i++) {
for (j=0; j<=min(i,p); j++) {
if ((j==0) || (j==i))
c[i][j] = 1
else
c[i][j] = c[i-1][j–1]+c[i-1][j];
}
}
return c[n][p];
}
18
Orden de eficiencia: (np) en tiempo, (np) en espacio.
Ejemplos
Números combinatorios:  n  =  n −1  + n −1 

Combinaciones de n sobre p −1
  
p p   p 
int combinaciones (int n, int p)
{
b[0] = 1;
for (i=1; i<=n; i++) {
b[i] = 1;
for (j=i–1; j>0; j--) {
b[j] += b[j – 1];
}
}
return b[p];
}
19
Orden de eficiencia: (np) en tiempo, (n) en espacio.
Devolver el cambio…
Existen casos para los que no se puede aplicar el
algoritmo greedy (por ejemplo, devolver 8 peniques
con monedas de 6, 4 y 1 penique).
Definición recursiva de la solución

 cambio({m1 ,..., mi−1}, C)
cambio({m1 ,..., mi },C) = min 
1+ cambio({m1 ,..., mi },C − mi )
Cálculo de la solución con programación dinámica:

◼ Orden de eficiencia proporcional al tamaño de la tabla,
O(Cn), donde n es el número de monedas distintas.
20
Devolver el cambio…
 cambio({m1 ,..., mi−1}, C)

cambio({m1 ,..., mi },C) = min 
1+ cambio({m1 ,..., mi }, C − mi )
0 1 2 3 4 5 6 7 8
{1} 0 1 2 3 4 5 6 7 8
{1,4} 0 1 2 3 1 2 3 4 2
{1,4,6} 0 1 2 3 1 2 1 2 2
m={1,4,6}, C=8
Solución: 2 monedas, S={4,4}.
21
Multiplicación encadenada de matrices
Propiedad asociativa del producto de matrices:
Dadas las matrices A1 (10x100), A2 (100x5) y A3 (5x50),

◼ (A1A2)A3 implica 7500 multiplicaciones
◼ A1(A2A3) implica 75000 multiplicacione
“Parentizaciones” posibles:
n−1 1 si n =1  4n 
P(n) =  P(k)P(n − k)  2 

 k =1
si n 1
n 
22
Si cada matriz Ak tiene un tamaño pk-1pk,
el número de multiplicaciones necesario será:
m(1,n) = m(1,k) + m(k +1, n) + p0 pk pn
A1 x A2 x A3 x…x Ak x Ak+1 x Ak+2 x … x An
De forma general:
m(i, j) = m(i, k) + m(k +1, j) + pi−1 pk p j

23
Matriz Ak de tamaño pk-1pk
Definición recursiva de la solución óptima:

◼ Si i=j, entonces
m(i, j) = 0
◼ Si i≠j, entonces
m(i, j) = minm(i, k) + m(k +1, j) + p i−1 pk p j 
ik j
A1 x A2 x A3 x…x Ak x Ak+1 x Ak+2 x … x An

24
Implementación:
◼ Tenemos n2 subproblemas distintos m(i,j).
◼ Para calcular m(i,j) necesitamos los valores

almacenados en la fila i y en la columna j
m(i, j) = minm(i, k) + m(k +1, j) + p i−1 pk p j 
ik j
◼ Para calcular cada valor necesitamos O(n),

por lo que el algoritmo resultante es de orden O(n3).
25
Implementación:
for (i=1; i<=n; i++)
m[i,i] = 0;
for (s=2; s<=n; l++)

for (i=1; i<=n-s+1; i++) {
j = i+s-1;
m[i,j] = ∞;
for (k=i; k<=j-1; k++) {
q = m[i,k] + m[k+1,j] + p[i-1]*p[k]p[j]
if (q < m[i,j]) {
m[i,j] = q;
s[i,j] = k;
}
}
26
}
Implementación:
// Suponiendo que hemos calculado previamente s[i,j]…
MultiplicaCadenaMatrices (A, i, j)
{
if (j>i) {
x = MultplicaCadenaMatrices (A, i, s[i,j]); y =
MultplicaCadenaMatrices (A, s[i,j]+1, j); return
MultiplicaMatrices(x, y);
} else {
return A[i];
}
}
27
Subsecuencia de mayor longitud (LCS)
Problema:
Comparar dos cadenas y encontrar la subsecuencia

común de mayor longitud.
Ejemplo:
Cadenas:
X = (A B C B D A B),
Y = (B D C A B A),
Subsecuencia común de mayor longitud:

LCS = (B C B A)
X = ( A B C B D A B )
Y = ( B D C A B A ) 28
Un algoritmo de fuerza bruta compararía cualquier
subsecuencia de X con los símbolos de Y:
Si |X|=m, |Y|=n, entonces hay 2m subsecuencias de X

que debemos comparar con Y (n comparaciones), por
lo que nuestro algoritmo sería de orden O(n2 m ).
Sin embargo, LCS tiene subestructuras optimales:
Si buscamos la LCS para pares de prefijos de X e Y,

podemos calcular la solución de nuestro problema…
29
Si buscamos la LCS para pares de prefijos de X e Y,
podemos calcular la solución de nuestro problema…
Xi Prefijo de X de longitud i.
Yj Prefijo de Y de longitud j.
c(i,j) Longitud de la LCS para Xi e Yj.
 c(i −1, j −1)+1 si x[i] = y[ j]

c(i, j) = 
max{c(i −1, j), c(i, j −1)} en otro caso
La longitud de la subsecuencia de mayor longitud

(LCS) de X e Y será c(m,n), con |X|=m, |Y|=n. 30
Definición recursiva de la solución:
◼ Caso base:
c(0,0) = 0 (Subcadena vacía)
c(0,j) = c(i,0) = 0 (LCS de la cadena vacía
y cualquier otra cadena)
◼ Cálculo recursivo:
◼ Primer caso (x[i]=y[j]=s): Se emparejan ambos
símbolos y la LCS aumenta de longitud:
LCS(Xi,Yj)= LCS(Xi-1,Yj-1)+{s}.
◼ Segundo caso (x[i]≠y[j]): No se pueden emparejar
los símbolos x[i] e y[j], por lo que LCS(Xi,Yj) será
la mejor entre LCS(Xi-1,Yj) y LCS(Xi,Yj-1). 31
Implementación iterativa del algoritmo:
int[][] LCS (X, Y)

{
for (i=0; i<=X.length; i++) c[i][0]=0; // Y0
for (j=1; j<=T.length; j++) c[0][j]=0; // X0
for (i=1; i<=X.length; i++) // Xi

for (j=1; j<=Y.length; j++) // Yj
if ( X[i] == Y[j] )
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max ( c[i-1][j], c[i][j-1] );
return c;
} 32
Ejemplo:
Yj B D C A B
X = (A B C B), 0 1 2 3 4 5
Y = (B D C A B),
Xi 0 0 0 0 0 0 0
A 1 0
B 2 0
C 3 0
B 4 0
for (i=0; i<=X.length; i++) c[i][0]=0; // Y0

for (j=1; j<=T.length; j++) c[0][j]=0; // X0
33
Ejemplo:
Yj B D C A B
X = (A B C B), 0 1 2 3 4 5
Y = (B D C A B),
Xi 0 0 0 0 0 0 0
A 1 0 0 0 0
B 2 0
C 3 0
B 4 0
if ( X[i] == Y[j] )
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max ( c[i-1][j], c[i][j-1] ); 34
Ejemplo:
Yj B D C A B
X = (A B C B), 0 1 2 3 4 5
Y = (B D C A B),
Xi 0 0 0 0 0 0 0
A 1 0 0 0 0 1
B 2 0
C 3 0
B 4 0
if ( X[i] == Y[j] )
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max ( c[i-1][j], c[i][j-1] ); 35
Ejemplo:
Yj B D C A B
X = (A B C B), 0 1 2 3 4 5
Y = (B D C A B),
Xi 0 0 0 0 0 0 0
A 1 0 0 0 0 1 1
B 2 0
C 3 0
B 4 0
if ( X[i] == Y[j] )
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max ( c[i-1][j], c[i][j-1] ); 36
Ejemplo:
Yj B D C A B
X = (A B C B), 0 1 2 3 4 5
Y = (B D C A B),
Xi 0 0 0 0 0 0 0
LCS = (B C B) A 1 0 0 0 0 1 1
B 2 0 1 1 1 1 2
X = ( A B C B )
C 3 0 1 1 2 2 2
Y = ( B D C A B )
B 4 0 1 1 2 2 3
NOTA:
A partir del valor c[i][j] podemos determinar cómo
se calculó éste y encontrar la LCS hacia atrás… 37
Selección de actividades con pesos
Enunciado del problema
Dado un conjunto C de n tareas o actividades, con
si = tiempo de comienzo de la actividad

fi = tiempo de finalización de la actividad i
vi = valor (o peso) de la actividad i
encontrar el subconjunto S de actividades compatibles

de peso máximo (esto es, un conjunto de actividades
que no se solapen en el tiempo y que, además, nos
proporcione un valor máximo). 38
Recordatorio
Existe un algoritmo greedy para este problema cuando

todas las actividades tienen el mismo valor (elegir las
actividades en orden creciente de hora de finalización).
Sin embargo, el algoritmo greedy no funciona en general:
valor = 999 b
valor = 1 a
39
Observación
Si, como en el algoritmo greedy, ordenamos las
actividades por su hora de finalización…
8 Tiempo 40
Observación
… podemos definir p(j) como el mayor índice i<j
tal que la actividad i es compatible con la actividad j
p(1)=0
p(2 )=0
p(3)=0
p(4)=1
p(5)=0
p(6 )=2
p(7 )=3
p(8)=5 Tiempo 41
 0 si j =0
OPT ( j) = 
max{v( j) + OPT ( p( j)),OPT ( j −1)} si j 0
◼ Caso 1: Se elige la actividad j.

◼ No se pueden escoger actividades incompatibles >p(j).
◼ La solución incluirá la solución óptima para p(j).
◼ Caso 2: No se elige la actividad j.

◼ La solución coincidirá con la solución óptima
para las primeras (j-1) actividades.
42
Implementación iterativa del algoritmo
SelecciónActividadesConPesos (C: actividades): S

{
Ordenar C según tiempo de finalización; // O(n log n)
Calcular p[1]..p[n]; // O(n log n)
mejor[0] = 0; // O(1)
for (i=1; i<=n, i++) // O(n)
mejor[i] = max ( valor[i]+mejor[p[i]],
mejor[i-1] );
return Solución(mejor); // O(n)

}
43
El problema de la mochila 0/1
Tenemos un conjunto S de n objetos, en el que cada
objeto i tiene un beneficio bi y un peso wi positivos.
Objetivo: Seleccionar
los elementos que nos
garantizan un beneficio
máximo pero pero con
un peso global menor
o igual que W.
44
Dado el conjunto S de n objetos,
sea Sk el conjunto de los k primeros objetos (de 1 a k):
Podemos definir B(k,w) como la ganancia de la mejor

solución obtenida a partir de los elementos de Sk para
una mochila de capacidad w.
Ahora bien, la mejor selección de elementos del

conjunto Sk para una mochila de tamaño w se puede
definir en función de selecciones de elementos de Sk-1
para mochilas de menor capacidad…
45
¿Cómo calculamos B(k,w)?
O bien la mejor opción para Sk coincide con la mejor

selección de elementos de Sk-1 con peso máximo w
(el beneficio máximo para Sk coincide con el de Sk-1),
o bien es es el resultado de añadir el objeto k a la mejor

selección de elementos de Sk-1 con peso máximo
w−wk (el beneficio para Sk será el beneficio que se
obtenía en Sk-1 para una mochila de capacidad w−wk
más el beneficio bk asociado al objeto k).
46
Definición recursiva de B(k,w):
 B(k −1,w) si xk = 0
B(k,w) = 
B(k −1, w − wk ) + b k si xk =1
Para resolver el problema de la mochila nos

quedaremos con el máximo de ambos valores:
B(k, w) = max{B(k −1, w), B(k −1, w − wk ) + bk }
47
Cálculo ascendente de B(k,w)
usando una matriz B de tamaño (n+1) x (W+1):
int[][] knapsack (W, w[1..n], b[1..n])

{
for (p=0; p<=W; p++)
B[0][p]=0;
for (k=1; k<=n; k++) {

for (p=0; p<w[k]; p++)
B[k][p] = B[k-1][p];
for (p=w[k]; p<=W; w++)
B[k][p] = max ( B[k-1][p−w[k]]+b[k], B[k-1][p] );
}
return B; 48
}
¿Cómo calculamos la solución óptima a partir de B(k,w)?
Calculamos la solución para B[k][w]

utilizando el siguiente algoritmo:
Si B[k][w] == B[k-1][w],
entonces el objeto k no se selecciona y se seleccionan
los objetos correspondientes a la solución óptima para
k-1 objetos y una mochila de capacidad w:
la solución para B[k-1][w].
Si B[k][w] != B[k-1][w],
se selecciona el objeto k
y los objetos correspondientes a la solución óptima
para k-1 objetos y una mochila de capacidad w-w[k]:
la solución para B[k-1][w-w[k]].
49
Eficiencia del algoritmo
Tiempo de ejecución: (n W)

◼ “Pseudopolinómico” (no es polinómico sobre el tamaño
de la entrada; esto es, sobre el número de objetos).
◼ El problema de la mochila es NP.
NOTA: Existe un algoritmo polinómico de

orden O(n2v*) que proporciona una solución
aproximada al 0.01% del óptimo [Kleinberg
& Tardos, sección 11.8: “Arbitrarily Good
Approximations: The Knapsack Problem”].
50
Ejemplo Objeto Valor Peso
Mochila de tamaño W=11 1 1 1
Número de objetos n=5 2 6 2
3 18 5
Solución óptima {3,4} 4 22 6
5 28 7
0 1 2 3 4 5 6 7 8 9 10 11
 0 0 0 0 0 0 0 0 0 0 0 0
{1} 0 1 1 1 1 1 1 1 1 1 1 1
{ 1, 2 } 0 1 6 7 7 7 7 7 7 7 7 7
{ 1, 2, 3 } 0 1 6 7 7 18 19 24 25 25 25 25
{ 1, 2, 3, 4 } 0 1 6 7 7 18 22 24 28 29 29 40
{ 1, 2, 3, 4, 5 } 0 1 6 7 7 18 22 28 29 34 35 40 51
Caminos mínimos: Algoritmo de Floyd
Problema:
Calcular el camino más corto que une cada par de
vértices de un grafo, considerando que no hay pesos
negativos.
Posibles soluciones:
◼ Por fuerza bruta (de orden exponencial).
◼ Aplicar el algoritmo de Dijkstra para cada vértice.
◼ Algoritmo de Floyd (programación dinámica). 52
Definición recursiva de la solución:
D k (i,j): Camino más corto de i a j usando sólo los k

primeros vértices del grafo como puntos intermedios.
Expresión recursiva:
Dk (i, j) = min{Dk −1 (i, j), Dk −1 (i, k ) + Dk −1 (k, j)}
Caso base:
D0 (i, j) = cij
53
Algoritmo de Floyd (1962): (V 3 )
for (i=0; i<n; i++)

for (j=0; j<n; j++)
D[i][j] = coste(i,j);
for (k=0; k<n; k++)

for (i=0; i<n; i++)
for (j=0; j<n; j++)
if (D[i][k] + D[k][j] < D[i][j] )
D[i][j] = D[i][k] + D[k][j];
Dk (i, j) = min{Dk −1 (i, j), Dk −1 (i, k ) + Dk −1 (k, j)} 54
Caminos mínimos: Algoritmo de Bellman-Ford
Si sólo nos interesan los caminos mínimos desde un

vértice concreto del grafo G(V,E), podemos utilizar el
algoritmo greedy de Dijkstra, de orden O(E log V),
siempre y cuando tengamos pesos no negativos.
El algoritmo de Dijkstra no funciona con pesos negativos:
2 3
s
1 -6
t
¡Ojo!
Tampoco podemos sumarle una constante a cada peso. 55
Si tenemos pesos negativos, podemos utilizar el

algoritmo de Bellman-Ford, basado en programación
dinámica y de orden O(EV), siempre y cuando no
tengamos ciclos de peso negativo:
 si i = 0
Di (w)=  min{D
 i−1 (w), min {Di−1 (v) + cvw }} en otro caso
(v,w)E
NOTA: Si un camino de s a t incluye un ciclo de peso negativo,

no existe un camino “más corto” de s a t (y, en cualquier caso,
Bellman-Ford tampoco encontraría el camino simple más corto). 56
Algoritmo de Bellman-Ford: (EV)
foreach v  V {
D[v] = ;
predecesor[v] = null;
}
D[s] = 0;
for (i=1; i<n; i++) {
foreach (v, w)  E {
if (D[v] + coste(v,w) < D[w]) {
D[w] = D[v] + coste(v,w);
predecesor[w] = v;
}
}
} 57
Distancia de edición
También conocida como distancia Levenshtein, mide
la diferencia entre dos cadenas s y t como el número
mínimo de operaciones de edición que hay que
realizar para convertir una cadena en otra:
d(“data mining”, “data minino”) = 1

d(“efecto”, “defecto”) = 1
d(“poda”, “boda”) = 1
d(“night”,”natch”) = d(“natch”,”noche”) = 3
Aplicaciones: Correctores ortográficos, reconocimiento

de voz, detección de plagios, análisis de ADN…
58
Para datos binarios: Distancia de Hamming.
 d (i −1, j −1) si s[i] = t[ j]

d(i, j) = 
1+ min{d (i −1, j), d (i, j −1), d (i −1, j −1)} si s[i]  t[ j]
CASOS
◼ Mismo carácter: d(i-1,j-1)
◼ Inserción: 1 + d(i-1,j)
◼ Borrado: 1 + d(i,j-1)
◼ Modificación: 1 + d(i-1,j-1)
59
int LevenshteinDistance (string s[1..m], string t[1..n])
{
for (i=0; i<=m; i++) d[i,0]=i;
for (j=0; j<=n; j++) d[0,j]=j;
for (j=1; j<=n; j++)

for (i=1; i<=m; i++)
if (s[i]==t[j])
d[i,j] = d[i-1, j-1]
else
d[i,j] = 1+ min(d[i-1,j],d[i,j-1],d[i-1,j-1]);
return d[m,n];
}
 d (i −1, j −1) si s[i] = t[ j]

d(i, j) = 
1+ min{d (i −1, j), d (i, j −1), d (i −1, j −1)} si s[i]  t[ j] 60
Aplicaciones
◼ Distancia entre dos series temporales: O(n2)
DTW [Dynamic Time Warping]
◼ Análisis sintáctico: O(n3)
◼ Algoritmo CKY [Cocke-Kasami-Younger]
◼ Algoritmo de Earley
◼ Algoritmo de Viterbi: HMMs [Hidden Markov Models]
◼ Decodificación de señales (p.ej. modems, GSM, wi-fi)
◼ Procesamiento del lenguaje natural
◼ Bioinformática
◼ Optimización de consultas en bases de datos relacionales
◼ Comparación de ficheros con diff
◼ … 61

SESION 3-1 Programacion Dinamica

Cargado por

Copyright:

SESION 3-1 Programacion Dinamica

Cargado por

Información del documento

Derechos de autor

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

SESION 3-1 Programacion Dinamica

Cargado por

Copyright:

Programación Dinámica

M.Sc. Ing. R. Fabrizio Calienes Rodriguez

◼ Subproblemas optimales: La solución óptima a un

◼ Solapamiento entre subproblemas: Al plantear la

1. Caracterizar la estructura de una solución óptima.

2. Definir de forma recursiva la solución óptima.

3. Calcular la solución óptima de forma ascendente.

4. Construir la solución óptima a partir de los datos

Dado un problema P con n elementos,

La solución óptima de cualquier instancia no trivial

◼ Se busca la solución óptima a un problema

◼ Se toma una decisión en cada paso, pero ésta

Enfoque está inspirado en la teoría de control:

Etimología: Programación dinámica = Planificación temporal

“Una política óptima tiene la propiedad de que,

En Informática, un problema que puede descomponerse

El principio de optimalidad se verifica

Ejemplo: Cambio en monedas

1. Se comprueba que se cumple el principio de

2. Se define recursivamente la solución óptima del

4. Se determina la solución óptima

◼ Implementación recursiva: O(n)

Orden de eficiencia: (np) 17

Definición recursiva de la solución

Cálculo de la solución con programación dinámica:

 cambio({m1 ,..., mi−1}, C)

Dadas las matrices A1 (10x100), A2 (100x5) y A3 (5x50),

m(1,n) = m(1,k) + m(k +1, n) + p0 pk pn

A1 x A2 x A3 x…x Ak x Ak+1 x Ak+2 x … x An

m(i, j) = m(i, k) + m(k +1, j) + pi−1 pk p j

Definición recursiva de la solución óptima:

A1 x A2 x A3 x…x Ak x Ak+1 x Ak+2 x … x An

◼ Tenemos n2 subproblemas distintos m(i,j).

◼ Para calcular m(i,j) necesitamos los valores

◼ Para calcular cada valor necesitamos O(n),

for (s=2; s<=n; l++)

Comparar dos cadenas y encontrar la subsecuencia

Subsecuencia común de mayor longitud:

Si |X|=m, |Y|=n, entonces hay 2m subsecuencias de X

Sin embargo, LCS tiene subestructuras optimales:

Si buscamos la LCS para pares de prefijos de X e Y,

 c(i −1, j −1)+1 si x[i] = y[ j]

La longitud de la subsecuencia de mayor longitud

int[][] LCS (X, Y)

for (i=1; i<=X.length; i++) // Xi

for (i=0; i<=X.length; i++) c[i][0]=0; // Y0

Dado un conjunto C de n tareas o actividades, con

si = tiempo de comienzo de la actividad

encontrar el subconjunto S de actividades compatibles

Existe un algoritmo greedy para este problema cuando

Sin embargo, el algoritmo greedy no funciona en general:

◼ Caso 1: Se elige la actividad j.

◼ Caso 2: No se elige la actividad j.

SelecciónActividadesConPesos (C: actividades): S

return Solución(mejor); // O(n)

Podemos definir B(k,w) como la ganancia de la mejor

Ahora bien, la mejor selección de elementos del

O bien la mejor opción para Sk coincide con la mejor

o bien es es el resultado de añadir el objeto k a la mejor

Para resolver el problema de la mochila nos

B(k, w) = max{B(k −1, w), B(k −1, w − wk ) + bk }

int[][] knapsack (W, w[1..n], b[1..n])

for (k=1; k<=n; k++) {

Calculamos la solución para B[k][w]