Parte de Algoritmos
de la asignatura de Programación
Master de Bioinformática
Programación dinámica
Web asignatura: http://dis.um.es/~domingo/algbio.html
E-mail profesor:
[email protected]
Transparencias preparadas a partir de las del curso de
Algoritmos y Estructuras de Datos II, del Grado de Ingeniería Informática
y An Introduction to Bioinformatics Algorithms
1
Método general
• La programación dinámica se suele utilizar en problemas
de optimización, donde una solución está formada por una
serie de decisiones.
• Resuelve el problema original combinando las soluciones
para subproblemas más pequeños.
• Se almacenan los resultados de los subproblemas en una
tabla, calculando primero las soluciones para los problemas
pequeños, y llegando hasta el tamaño deseado con un
proceso iterativo.
• Con esto se pretende evitar la repetición de cálculos para
problemas más pequeños.
2
Método general
• Ejemplo. Cálculo de los números de Fibonacci.
• Con método recursivo
Fibonacci (n: integer)
Si n<2 Devolver 1
Sino Devolver Fibonacci (n-1) + Fibonacci (n-2)
– Problema: Muchos cálculos están repetidos, tiempo de ejec.
exponencial.
– Solución: Calcular los valores de menor a mayor empezando por
0, e ir guardando los resultados en una tabla.
• Con programación dinámica.
Fibonacci (n: integer)
T[0] = 0; T[1] = 1
para i = 2,3, ...,n
T[i] = T[i-1] + T[i-2]
devolver T[n]
– Se utiliza la misma fórmula que en la versión anterior, pero de forma
más inteligente. El tiempo de ejecución es Q
(n).
3
Método general
• Aspectos a definir en un algoritmo de programación
dinámica:
– Ecuación recurrente, para calcular la solución de los
problemas grandes en función de los problemas más
pequeños.
– Determinar los casos base.
– Definir las tablas utilizadas por el algoritmo, y cómo se
rellenan.
– Cómo se recompone la solución global a partir de los
valores de las tablas.
4
Análisis de tiempos de ejecución
• El tiempo de ejecución depende de las características
concretas del problema a resolver.
• En general, será de la forma:
Tamaño de la tabla*Tiempo de rellenar cada elemento
de la tabla.
• Un aspecto importante de los algoritmos de programación
dinámica es que necesitan una tabla para almacenar los
resultados parciales, que puede ocupar mucha memoria.
• Además, algunos de estos cálculos pueden ser
innecesarios.
5
Problema del cambio de monedas
Problema: Dado un conjunto de n tipos de monedas, cada una con
valor vi, y con una cantidad de monedas de ese tipo ci, y dada una
cantidad P, encontrar el número mínimo de monedas que tenemos
que usar para obtener esa cantidad.
• El algoritmo voraz es muy eficiente, pero sólo funciona en un
número limitado de casos.
• Utilizando programación dinámica:
– Definimos el problema en función de problemas más
pequeños.
– Determinar los valores de los casos base.
– Definimos las tablas necesarias para almacenar los
resultados de los subproblemas.
– Establecemos una forma de rellenar las tablas y de
obtener el resultado.
6
Problema del cambio de monedas
Definición de la ecuación recurrente:
• Cambio (i, Q), el problema de calcular el número mínimo de monedas
necesario para devolver una cantidad Q, usando los i primeros tipos
de monedas (es decir los tipos 1...i).
• La solución de Cambio(i, Q) puede que utilice k monedas de tipo i o
puede que no utilice ninguna.
– Si no usa ninguna moneda de ese tipo:
Cambio(i, Q) = Cambio(i - 1, Q)
– Si usa k monedas de tipo i:
Cambio(i, Q) = Cambio(i, Q – k*vi) + k
• En cualquier caso, el valor será el mínimo:
Cambio(i, Q) = mink=0,1,...,min{Q/vi,ci} {Cambio(i-1, Q-k* vi)+k}
Casos base: Cambio(i, Q)
• Si (i£ 0) o (Q<0) entonces no existe ninguna solución al problema, y
Cambio(i, Q) = +¥
.
• En otro caso para cualquier i>0, Cambio(i, 0) = 0.
7
Problema del cambio de monedas
Definición de las tablas utilizadas:
• Necesitamos almacenar los resultados de todos los
subproblemas.
• El problema a resolver será: Cambio (n, P).
• Por lo tanto, necesitamos una tabla de nxP, de enteros, que
llamaremos D, siendo D[i, j ]= Cambio(i, j).
• Ejemplo. n= 3, P= 8, v= (1, 4, 6), no límite en c
D
Cantidad a devolver
Monedas
0
1
2
3
4
5
6
7
8
C1= 1
C2 = 4
C3 = 6
Forma de rellenar las tablas:
• De arriba hacia abajo y de izquierda a derecha, aplicar la
ecuación de recurrencia:
D[i, j] = mink=0,1,...,min{Q/vi,ci} {D(i-1, Q-k* vi)+k}
8
Problema del cambio de monedas
• Algoritmo.
Devolver-cambio (P: int; V: array [1..n] of int; C: array [1..n] of int; var D: array
[1..n, 0..P] of int);
para i = 1,2,...,n
D[i, 0] = 0
para i = 1,2,...,n
para j = 1,2,...,P
D[i, j] = mink=0,1,...,min{Q/vi,ci} {D(i-1, Q-k* vi)+k} { cae fuera de la tabla}
{Tener en cuenta si el valor }
• Ejemplo. n= 3, P= 8, v= (1, 4, 6), no límite en c
C1= 1
C2 = 4
C3 = 6
0
0
0
0
1
1
1
1
2
2
2
2
3
3
3
3
4
4
1
1
5
5
2
2
6
6
3
1
7
7
4
2
8
8
2
2
9
Problema del cambio de monedas
• ¿Cómo calcular cuántas monedas de cada tipo deben usarse, es decir la
solución (x1, x2, ..., xn)?
• Se usa otra tabla de decisiones tomadas:
Aux
C1 = 1
C2 = 4
C3 = 6
0
0
0
0
1
1
0
0
2
2
0
0
3
3
0
0
4
4
1
0
5
5
1
0
6
6
1
1
7
7
1
1
8
8
2
0
• Algoritmo para obtener una solución:
para i=n,n-1,...,1
xi=Aux[i,P]
P=P-xi*vi
Hacer un programa Perl para este problema.
10
fi
Programación dinámica en Bioinformática
Interesa conocer la similaridad entre genes, o de varios genes con
determinadas cadenas.
La Programación Dinámica se usa para estudiar similaridad entre
genes.
Veremos el algoritmo de Mayor Subcadena Común (Longest Common
Subsequence, LCS)
ver si se puede utilizar programación dinámica en la generación inicial
de soluciones en el trabajo individual, a partir de la explicación y el
programa del LCS
11
Problema de la Distancia de Manhattan
Buscamos un camino
del Origen al Destino
con el que podamos
visitar la mayor
cantidad de
atracciones (*). Solo
se puede andar a la
derecha y abajo.
Origen
* *
*
*
*
*
*
*
*
*
*
*
Destino
12
Problema de la Distancia de Manhattan
Se quiere encontrar el camino de longitud mayor
en una malla con pesos
Entrada: Una malla con pesos G con dos vértices
distinguidos, Origen y Destino
Salida: Un camino en G de longitud máxima para
ir del Origen al Destino
13
Problema de la Distancia de Manhattan
origen
C
o
o
r
d
e
n
a
d
a
i
0
1
2
3
4
3
3
0
3
0
0
1
4
4
5
1
3
0
6
4
6
2
2
7
3
2
5
2
5
5
8
3
1
4
4
3
0
2
3
9
4
13
2
15
2
0
2
4
2
5
2
14
4
3
1
19
1
20
3
23
Coordenada j
destino
Problema de la Distancia de Manhattan
¿Cómo podría ser un algoritmo de avance
rápido para este problema?
¿Se obtendría la solución óptima?
¿Qué tiempo de ejecución tendría?
¿Cómo podría ser un algoritmo por
backtracking para este problema?
¿Se obtendría la solución óptima?
¿Qué tiempo de ejecución tendría?
15
fi
fi
Problema de la Distancia de Manhattan
1
j
1
1
S0,1 = 1
0
5
5
S1,0 = 5
i
0
1
Para hacerlo por Programación Dinámica:
• Calcular el peso del camino óptimo para cada vértice de la malla
• En cada vértice el peso es el máximo del de los vértices anteriores
sumado con el peso de la arista que los une
16
MTP: Dynamic Programming
(cont’d)
j
2
source
i
0
1
2
0
1
3
S0,2 = 3
1
-5
2
1
3
4
S1,1 = 4
5
3
5
8
S2,0 = 8
17
MTP: Dynamic Programming
(cont’d)
source
3
0
j
1
2
i
0
1
2
3
1
-5
-5
5
3
0
5
8
8
S3,0 = 8
5
3
10
8
S3,0 = 8
13
S1,2 = 13
2
1
1
4
3
5
9
S2,1 = 9
18
MTP: Dynamic Programming (cont’d)
j
0
source
3
8
-5
8
S1,3 = 8
1
1
4
9
3
5
0
2
1
3
2
3
10
-3
13
5
-5
12
S2,2 = 12
9
S3,1 = 9
19
i
0
1
2
3
1
-5
-5
0
5
3
0
5
8
8
greedy alg.
MTP: Dynamic Programming
(cont’d)
source
3
0
j
1
2
i
0
1
2
3
1
-5
-5
0
5
3
0
5
8
8
2
1
3
5
-5
3
3
13
12
10
-3
-5
1
4
9
3
5
0
0
9
9
S3,2 = 9
8
8
-5
2
15
S2,3 = 15
20
MTP: Dynamic Programming
(cont’d)
source
2
3
j
0
1
i
0
1
2
3
1
-5
-5
0
5
3
0
5
8
8
2
1
3
1
4
9
3
5
0
3
13
12
10
-3
-5
0
9
9
5
-5
3
0
-5
2
1
Done!
8
8
(showing all back-traces)
15
16
S3,3 = 16
21
Problema de la Distancia de Manhattan
Se utiliza una ecuación de recurrencia para calcular
el valor en cada punto:
si, j = max
si-1, j + peso de la arista entre (i-1, j) y (i, j)
si, j-1 + peso de la arista entre (i, j-1) y (i, j)
El tiempo de ejecución es n x m
Y la solución que se obtiene es óptima
22
Problema de la Secuencia Común más Larga (LCS)
• Dadas dos secuencias
v = v1 v2…vm y w = w1 w2…wn
• La LCS de v y w es una secuencia de posiciones en
v: 1 < i1 < i2 < … < it < m
y otra secuencia de posiciones en
w: 1 < j1 < j2 < … < jt < n
tal que la it -sima letra de v es igual a la jt-sima letra de w
y t es máximo
23
Problema de la Secuencia Común más Larga (LCS)
Coord. i:
elements of v
elements of w
Coord. j:
0
0
1
2
2
3
A T -- C
-- T G C
3
0
2
1
3
--
A
4
4
5
6
7
8
T G A T C
T -- A -- C
7
5
5
6
6
(0,0)(1,0)(2,1)(2,2)(3,3)(3,4)(4,5)(5,5)(6,6)(7,6)(8,7)
Las coincidencias en rojo
Posiciones de v:
Posiciones de w:
2 < 3 < 4 <
Comentarios de: Programación dinámica (0)
No hay comentarios