PREDA - UNED
Programación y Estructuras de Datos Avanzadas
Capítulo 5
Programación dinámica
Planteamiento
• Almacenar resultados parciales ya calculados para
reutilizarlos repetidamente durante la resolución del
problema, reduciendo el coste de cómputo
• Comparte algunos casos de aplicación con el esquema
"divide y vencerás"
• Conviene si:
• existen llamadas recursivas repetidas
• se cumple el Principio de Optimalidad de Bellman
• dada una secuencia óptima de decisiones, toda sub secuencia de
ella es, a su vez, óptima
• Se suele usar una tabla para guardar los resultados
parciales (coste temporal vs. coste espacial)
PD vs. DyV
• PD • DyV
1. Divide el problema en 1. Divide el problema en
subproblemas subproblemas
2. Los subproblemas son 2. Los subproblemas son
dependientes entre sí independientes entre sí
3. Se almacena la 3. No se almacena la
solución de un solución de un
subproblema subproblema
4. Algoritmo Bottom-Up 4. Algoritmo Top-Down
Proceso
• Establecimiento de las ecuaciones que representan
el problema
• Identificación de los resultados parciales
• Construcción de la tabla de resultados parciales:
• Inicialización de la tabla con los casos base que
establece la ecuación del problema
• Establecimiento del orden de llenado de la tabla, de
forma que se calculen en primer lugar los resultados
parciales que requieren pasos posteriores
• Sustitución de las llamadas recursivas del algoritmo por
consultas a la tabla
Ejemplo
•
[0..n]
Añadir:
dev t[n]
Los coeficientes binomiales
• Definición:
• Ejemplo:
x2
x3 x2
x3
• Solución: PD + Triángulo de Pascal
Los coeficientes binomiales
matriz[0..n, 0..k] de entero
• Definición:
• Ejemplo:
i-1 x2
x3 x2
x3
Añadir:
dev t[n, k]
• Solución: PD + Triángulo de Pascal
matriz[1..N, 0..C] de entero
Devolución del
cambio
• Con N tipos de monedas
(imposible con algoritmo voraz)
• Coste O(NC)
• Construcción de la tabla
• T[i,j] = Nº monedas
de tipo xi o menos
para la cantidad Cj
x2
x3
• Posibilidad de usar un
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas
0 de tipo xi o menos
{1}
para la cantidad Cj
x2=4 0
{1,4}
x2
x3=6
x3
0
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº
+1 monedas
+1 +1
0 de tipo
1 xi o2 menos3
{1}
para la cantidad Cj
x2=4 0 1 2 3
{1,4}
x2
x3=6
x3
0 1 2 3
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas +1
0 de tipo
1 xi o2 menos 3 4
{1}
para la cantidad Cj
x2=4 0 1 2 3 +1
1
{1,4}
x2
x3=6
x3
0 1 2 3 1
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas +1
0 de tipo
1 xi o2 menos 3 4 5
{1}
para la cantidad Cj
x2=4 0 1 2 3 1 +1
2
{1,4}
x2
x3=6
x3
0 1 2 3 1 2
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas +1
0 de tipo
1 xi o2 menos 3 4 5 6
{1}
para la cantidad Cj
x2=4 0 1 2 3 1 2 +1
3
{1,4}
x2
x3=6
x3
0 1 2 3 1 2 +1
1
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas +1
0 de tipo
1 xi o2 menos 3 4 5 6 7
{1}
para la cantidad Cj
x2=4 0 1 2 3 1 2 3 +1
4
{1,4}
x2
x3=6
x3
0 1 2 3 1 2 1 +1
2
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
matriz[1..N, 0..C] de entero
Devolución del
cambio • Monedas = {1, 4, 6}
Ejemplo:
• C=8
• Con N tipos de monedas
(imposible con algoritmo voraz)
T[i,j] = min ( t[i-1,j] , t[i, j-xi] + 1 ) si xi j
• Coste O(NC)
• Construcción
T 0 1 de la
2 tabla
3 4 5 6 7 8
x1=1• T[i,j] = Nº monedas +1
0 de tipo
1 xi o2 menos 3 4 5 6 7 8
{1}
para la cantidad Cj
x2=4 0 1 2 3 1 2 3 4 +1
2
{1,4}
x2
x3=6
x3
0 1 2 3 1 2 1 2 +1
2
• Posibilidad de usar un
{1,4,6}
algoritmo voraz (O(C))
para saber las
monedas usadas
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
El viaje por el río
• ¿Cuál es la forma más barata de ir de uno de los
embarcaderos a cualquier otro que esté río abajo?
T: Tabla de precios
C: Tabla de costes
mínimos
• Construcción de la tabla C por diagonales
Añadir T como 1er
El viaje por el río parámetro en declaración
y llamada a MinMultiple
• ¿Cuál es la forma más barata de ir de uno de los
embarcaderos a cualquier otro que esté río abajo?
T: Tabla de precios
C: Tabla de costes
mínimos
• Construcción de la tabla C por diagonales
Coste O(N3)
(2 bucles anidados más llamada)
La mochila
• Se dispone de n objetos con un volumen entero vi y un beneficio
positivo bi , y una mochila con una capacidad máxima V (o W)
• Objetivo: llenar la mochila de manera que se maximice el
beneficio total considerando el volumen máximo:
xi = 0 ó 1
• Ecuación de recurrencia:
máximo
beneficio para
un volumen libre
W considerando
los objetos entre
1 e i, siendo in
La mochila
• Construimos la tabla M (objetos x volumen)
• Sólo es posible si los volúmenes son enteros
• Para calcular M[i, j] necesitamos 2 posiciones de la fila i-1
• Si solo queremos el beneficio (no los objetos) basta con un vector
• El valor M[n, V] de la última fila nos da la solución
• Ejemplo:
• Coste: O(nV)
• Posibilidad de recorrer la tabla y construir un vector binario
indicando los objetos seleccionados
La mochila
• ¿Cómo saber los objetos incluidos?
• Empezamos en t[n, W]
• Si t[i, j] == t[i-1, j]: el objeto i NO se incluye y seguir en t[i-1, j]
• Si t[i, j] != t[i-1, j]: el objeto i SI se incluye y seguir en t[i-1, j-vi]
-v2
-v4
( , , , , ) → ( , , , ,0) → ( , , ,1,0) → ( , ,0,1,0) → ( ,1,0,1,0) → (0,1,0,1,0)
La mochila
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
v/b 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/1 0
2/6 0
5/18 0
6/22 0
7/28 0
Ejercicio de examen
v/b 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/1 0 1
2/6 0
5/18 0
6/22 0
7/28 0
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1
5/18 0 1
6/22 0 1
7/28 0 1
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6
5/18 0 1
6/22 0 1
7/28 0 1
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7
5/18 0 1
6/22 0 1
7/28 0 1
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7
6/22 0 1 6 7 7
7/28 0 1 6 7 7
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18
6/22 0 1 6 7 7
7/28 0 1 6 7 7
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19
6/22 0 1 6 7 7
7/28 0 1 6 7 7
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24
6/22 0 1 6 7 7
7/28 0 1 6 7 7
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25
6/22 0 1 6 7 7
7/28 0 1 6 7 7
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29 34
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29 34 35
Ejercicio de examen
v/b 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/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29 34 35 40
Ejercicio de examen
v/b 0 1 2 3 4 5 6 7¿Qué8 objetos
9 10 hemos
11introducido?
- 0 0 0 0 0 0 0 0 ?0 0? 0 ? 0 ? ?
1/1 0 1 1 1 1 1 1 1 1 1 1 1
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29 34 35 40
Ejercicio de examen
v/b 0 1 2 3 4 5 6 7¿Qué8 objetos
9 10 hemos
11introducido?
- 0 0 0 0 0 0 0 0 00 00 0 1 0 1 0
1/1 0 1 1 1 1 1 1 1 1 1 1 1
0 + 0 + 18 + 22 + 0
2/6 0 1 6 7 7 7 7 7 7 7 7 7
5/18 0 1 6 7 7 18 19 24 25 25 25 25
6/22 0 1 6 7 7 18 22 24 28 29 29 40
7/28 0 1 6 7 7 18 22 28 29 34 35 40
Multiplicación asociativa de
matrices
• Multiplicar A (m x n) por B (n x p) da una matriz de m x p
y requiere m x n x p productos escalares
• Objetivo: hallar el número mínimo de multiplicaciones
escalares para el producto de una secuencia de matrices
• Ejemplo:
Multiplicación asociativa de
matrices
• ¿Y si lo hacemos por fuerza bruta?
¿De cuantas formas podemos agrupar las matrices?
• Si hay 1 o 2 matrices…
solo hay 1 agrupación posible: (A) o (AB)
• Si hay 3 matrices…
hay 2: ((AB)C), (A(BC))
• Si hay 4 matrices…
hay 5: (((AB)C)D)), ((AB)(CD)), ((A(BC))D), (A((BC)D)), (A(B(CD)))
• Si hay 5 matrices…
hay… ¡14 agrupaciones posibles!
• Y con más… ¡sigue creciendo exponencialmente!
Siguen la secuencia de los números de Catalan
• No es una solución válida
Multiplicación asociativa de
matrices
• Ecuación de recurrencia
• di: Nº columnas de la matriz Mi (número de filas será di-1)
• E(i, j): Nº mínimo de productos escalares para multiplicar
las matrices Mi..Mj
• Ejemplo: M1(60x2) x M2(2x30) x M3(30x5) x M4(5x20)
j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4
i=1 0 i=1 0 3600 i=1 0 3600 900 i=1 0 3600 900 2900
i=2 0 i=2 0 300 i=2 0 300 500 i=2 0 300 500
i=3 0 i=3 0 3000 i=3 0 3000 i=3 0 3000
i=4 0 i=4 0 i=4 0 i=4 0
Multiplicación asociativa de
M1(60x2) x M2(2x30) x M3(30x5) x M4(5x20)
matrices j=1 j=2 j=3 j=4 mínimo
i=1
• Ecuación de 0 3600
recurrencia 900 ?
2900
i=2 0 300 500 + 60x2x20 = 2900
i=3 0 3000 + 60x30x20 = 39000
i=4 0 + 60x5x20 = 6900
• di: Nº columnas de la matriz Mi (número de filas será di-1)
• E(i, j): Nº mínimo de productos escalares para multiplicar
mejor j=1
las matrices Mi..Mj j=2 j=3 j=4 Posibilidad de
K guardar la posición de
• Ejemplo: M1(60x2)
i=1 - x M2(2x30)
1 1 x M3(30x5)
1 losx paréntesis:
M4(5x20)
Función recursiva que
i=2 - 2 3 empieza en [1,N] y se
j=1 j=2 j=3 j=4 i=3 j=1 j=2 j=3 j=4 bifurca en [i,k] y [k+1,
-j=1 j=2 3j=3 j=4
j] siendo
j=1 j=2
k el valor
j=3 j=4
i=1 0 i=1 0 3600 i=1 0 3600 900 i=1 0 3600 900 2900
i=2 0 i=4 i=2 0 300 i=2 0 - almacenado
300 500 i=2 0 300 500
i=3 0 i=3 0 3000 i=3 0 3000 i=3 0 3000
i=4 0 i=4 ABCD →0 (A((BC)D))
i=4 0 i=4 0
Multiplicación asociativa de
3
matrices Coste O(N )
(2 bucles anidados más llamada)
Coste espacial O(N2)
• Ecuación de recurrencia (tabla de NxN)
• di: Nº columnas de la matriz Mi (número de filas será di-1)
• E(i, j): Nº mínimo de productos escalares para multiplicar
las matrices Mi..Mj
• Ejemplo: M1(60x2) x M2(2x30) x M3(30x5) x M4(5x20)
j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4 j=1 j=2 j=3 j=4
i=1 0 i=1 0 3600 i=1 0 3600 900 i=1 0 3600 900 2900
i=2 0 i=2 0 300 i=2 0 300 500 i=2 0 300 500
i=3 0 i=3 0 3000 i=3 0 3000 i=3 0 3000
i=4 0 i=4 0 i=4 0 i=4 0
Ejercicio de examen
Antes vimos T
girada 90 a la
dcha.
Ejercicio de examen
T’ 1 2 3 4 5 6
6 3 ? ? ? ? -
5 ? -
4 ? -
3 ? -
2 ? -
1 -
• T’[6,1] = min(0+10500+30·35·25,
15750+5375+30·15·25, 7875+3500+30·5·25,
9375+5000+30·10·25, 11875+0+30·20·25)
• T’[6,1] = min(36750, 32375, 15125, 21875, 26875)
Ejercicio de examen
T’ 1 2 3 4 5 6
6 3 5 ? -
5 ? -
4 -
3 1 ? -
2 ? -
1 -
• T’[3,1] = min(0+2625+30·35·5, 15750+0+30·15·5)
• T’[3,1] = min(7875, 18000)
• T’[6,4] = min(0+5000+5·10·25, 1000+0+5·20·25)
• T’[6,4] = min(6250, 3500)
Ejercicio de examen
T’ 1 2 3 4 5 6
6 3 5 -
5 -
4 -
3 1 -
2 -
1 -
(A1A2A3A4A5A6) →
((A1A2A3)(A4A5A6)) →
((A1(A2A3))((A4A5)A6))
Camino de coste mínimo en un
grafo dirigido
• Algoritmo de Floyd como alternativa al algoritmo
de Dijkstra (ver alg. voraz), los dos con O(N3)
• Ecuación de recurrencia • M(i, j, k): Coste mínimo entre los nodos i y j
pudiendo pasar por los nodos entre 1 y k
• A[i, j]: el coste de la arista entre i y j
• Para calcular M(i, j, k) sólo necesitamos los datos
tras incluir el nodo k-1, así que utilizamos una tabla
NxN que se va reescribiendo
Camino de coste mínimo en un
grafo dirigido
• Algoritmo de Floyd1
como alternativa al algoritmo
de Dijkstra (ver alg. 1voraz), los dos con O(N3)
• Ecuación de recurrencia • M(i, j, k): Coste mínimo entre los nodos i y j
pudiendo pasar por los nodos entre 1 y k
• A[i, j]: el coste de la arista entre i y j
• Para calcular M(i, j, k) sólo necesitamos los datos
tras incluir el nodo k-1, así que utilizamos una tabla
NxN que se va reescribiendo
Distancia de edición
• Objetivo: encontrar el número mínimo de cambios
para transformar la cadena X=x1,…,xn en la cadena
Y=y1,…,ym con los siguientes cambios posibles:
• Borrar un carácter de X
• Insertar uno de los caracteres de Y en X
• Sustituir un carácter de X por uno de los de Y
• Ecuación de recurrencia: • C(i, j): Nº mínimo de cambios para convertir
x1,…, xi en y1,…yj
Distancia de edición
Coste O(nm)
• Objetivo: encontrar el número mínimo de cambios
(2 bucles anidados)
para transformar la cadena X=xCoste
1,…,x en O(nm)
espacial
n la cadena
(tabla de n x m)
Y=y1,…,ym con los siguientes cambios posibles:
• Borrar un carácter de X
• Insertar uno de los caracteres de Y en X
• Sustituir un carácter de X por uno de los de Y
• Ecuación de recurrencia: • C(i, j): Nº mínimo de cambios para convertir
x1,…, xi en y1,…yj
Ejercicio de examen
Ejercicio de examen
Resumen de ejemplos
• Fibonacci
- Almacenar los 2 últimos valores
• Coeficientes binomiales
- Triángulo de Pascal
• Devolución del cambio (para cualquier tipo de monedas)
- T[i,j] = nº monedas de tipo xi o menos para la cantidad Cj
• Viaje por el río
- Ir almacenando el coste en saltos de distancia 1, 2,…
• Mochila (objetos NO fraccionables)
- T[i,j] = beneficio máximo con objetos 1..i y volumen libre j
• Multiplicación asociativa de matrices
- T(i, j) = Nº mínimo de productos escalares para las matrices Mi..Mj
• Camino de coste mínimo en un grafo dirigido
- Alg. de Floyd (alternativa a Dijkstra): consideramos cada vez más nodos
• Distancia de edición
- T(i, j) = Nº mínimo de cambios para las posiciones i y j de las cadenas x,y
