algorithms_aula11

Prévia do material em texto

Projeto e Análise de Algoritmos I - 2019-1
Programação Dinâmica: multiplicação iterada de
matrizes
Carlos H. A. Higa
Faculdade de Computação
Universidade Federal de Mato Grosso do Sul
Programação Dinâmica
PD - multiplicação iterada de matrizes
# Dada uma sequência de matrizes 〈A1 ,A2 , . . . ,An〉,
desejamos calcular o produto A1A2 · · ·An ;
# A multiplicação de matrizes é associativa;
# Um produto de matrizes é completamente parentizado se
ele é uma única matriz ou o produto de dois produtos
completamente parentizados, envolvido por parênteses;
# Exemplo: para 〈A1 ,A2 ,A3 ,A4〉 temos:
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
A maneira como parentizamos tem impacto no custo da
multiplicação das matrizes.
PD - multiplicação iterada de matrizes
Matrix-Multiply(A, B)
1 if A.columns , B.rows
2 error “incompatible dimensions”
3 else let C be a new A.rows × B.columns matrix
4 for i � 1 to A.rows
5 for j � 1 to B.columns
6 ci j � 0
7 for k � 1 to A.columns
8 ci j � ci j + aik · bk j
9 return C
PD - multiplicação iterada de matrizes
# Se A é p × q e B é q × r,
ci j �
∑
k
aik · bk j ;
# Número de multiplicações escalares (linha 8): p · q · r;
Exemplo
# 〈A1 ,A2 ,A3〉, 10 × 100, 100 × 5 e 5 × 50, respectivamente;
# ((A1A2)A3):
A1A2 custa 10 · 100 · 5 � 5000; o resultado é
uma matriz 10 × 5. Mais 10 · 5 · 50 � 2500multiplicações
para multiplicar esta matriz por A3. Total: 7500.
# (A1(A2A3)):
A2A3 custa 100 · 5 · 50 � 25000; o resultado é
uma matriz 100 × 50. Mais 10 · 100 · 50 � 50000
multiplicações para multiplicar esta matriz por A1. Total:
75000.
PD - multiplicação iterada de matrizes
# Se A é p × q e B é q × r,
ci j �
∑
k
aik · bk j ;
# Número de multiplicações escalares (linha 8): p · q · r;
Exemplo
# 〈A1 ,A2 ,A3〉, 10 × 100, 100 × 5 e 5 × 50, respectivamente;
# ((A1A2)A3): A1A2 custa 10 · 100 · 5 � 5000; o resultado é
uma matriz 10 × 5. Mais 10 · 5 · 50 � 2500multiplicações
para multiplicar esta matriz por A3. Total: 7500.
# (A1(A2A3)):
A2A3 custa 100 · 5 · 50 � 25000; o resultado é
uma matriz 100 × 50. Mais 10 · 100 · 50 � 50000
multiplicações para multiplicar esta matriz por A1. Total:
75000.
PD - multiplicação iterada de matrizes
# Se A é p × q e B é q × r,
ci j �
∑
k
aik · bk j ;
# Número de multiplicações escalares (linha 8): p · q · r;
Exemplo
# 〈A1 ,A2 ,A3〉, 10 × 100, 100 × 5 e 5 × 50, respectivamente;
# ((A1A2)A3): A1A2 custa 10 · 100 · 5 � 5000; o resultado é
uma matriz 10 × 5. Mais 10 · 5 · 50 � 2500multiplicações
para multiplicar esta matriz por A3. Total: 7500.
# (A1(A2A3)): A2A3 custa 100 · 5 · 50 � 25000; o resultado é
uma matriz 100 × 50. Mais 10 · 100 · 50 � 50000
multiplicações para multiplicar esta matriz por A1. Total:
75000.
PD - multiplicação iterada de matrizes
O problema da multiplicação iterada de matrizes
Dada uma sequência 〈A1 ,A2 , . . . ,An〉 dematrizes, ondeAi tem
dimensão pi−1 × pi , para i � 1, 2, . . . , n, parentizar o produto
A1A2 · · ·An de maneira a minimizar o número de multiplica-
ções escalares.
# Note que não estamos multiplicando as matrizes, apenas
encontrando o jeito mais barato de fazer isso;
# Checar todas as possibilidades é muito caro;
# Quantas maneiras de parentizar uma sequência de n matrizes?
P(n) �

1 se n � 1 ,
n−1∑
k�1
P(k)P(n − k) se n ≥ 2 .
# Números de Catalão (Ω(4n/n3/2)).
PD - multiplicação iterada de matrizes
O problema da multiplicação iterada de matrizes
Dada uma sequência 〈A1 ,A2 , . . . ,An〉 dematrizes, ondeAi tem
dimensão pi−1 × pi , para i � 1, 2, . . . , n, parentizar o produto
A1A2 · · ·An de maneira a minimizar o número de multiplica-
ções escalares.
# Note que não estamos multiplicando as matrizes, apenas
encontrando o jeito mais barato de fazer isso;
# Checar todas as possibilidades é muito caro;
# Quantas maneiras de parentizar uma sequência de n matrizes?
P(n) �

1 se n � 1 ,
n−1∑
k�1
P(k)P(n − k) se n ≥ 2 .
# Números de Catalão (Ω(4n/n3/2)).
PD - multiplicação iterada de matrizes
n 1 2 3 4 5 6 7 8 9 10 11
P(n) 1 1 2 5 14 42 132 429 1430 4862 16796
Pode ser mostrado que P(n) � Ω(2n).
Aplicar a Programação Dinâmica
# Caracterizar a estrutura de uma solução ótima;
# Definir o valor da solução ótima de maneira recursiva;
# Calcular o valor da solução ótima;
# Construir a solução ótima a partir da informação calculada.
PD - multiplicação iterada de matrizes
Subestrutura ótima
Se
((A1A2)(A3((A4A5)A6)))
é uma solução ótima para 〈A1 ,A2 ,A3 ,A4 ,A5 ,A6〉, então
(A1A2) e (A3((A4A5)A6))
também são soluções ótimas para 〈A1 ,A2〉 e 〈A3 ,A4 ,A5 ,A6〉,
respectivamente.
Decomposição: ParamultiplicarAiAi+1 · · ·A j , podemosdividir
em dois subproblemas (Ai · · ·Ak)(Ak+1 · · ·A j).
Esta decomposição sugere um algoritmo recursivo.
PD - multiplicação iterada de matrizes
Solução recursiva
# m[i , j]: número mínimo de multiplicações para calcular
AiAi+1 · · ·A j , onde 1 ≤ i ≤ j ≤ n;
# Assim, o valor da solução ótima será calculada em m[1, n];
# Se i � j, o problema é trivial. Logo, m[i , i] � 0, para
i � 1, 2, . . . , n;
# Se i < j, usamos a estrutura da solução ótima para calcular
m[i , j]:
m[i , j] �
{
0 se i � j ,
min
i ≤ k < j
{m[i , k] + m[k + 1, j] + pi−1pkp j} se i < j .
# Por exemplo:
m[3, 7] � min
3≤ k < 7
{m[3, k] + m[k + 1, 7] + p2pkp7}
PD - multiplicação iterada de matrizes
Matrix-Chain-Order(p)
1 n � p. length − 1
2 let m[1 . . n][1 . . n] and s[1 . . n − 1][2 . . n] be new tables
3 for i � 1 to n
4 m[i , i] � 0
5 for l � 2 to n // l is the chain length
6 for i � 1 to n − l + 1
7 j � i + l − 1
8 m[i , j] � ∞
9 for k � i to j − 1
10 q � m[i , k] + m[k + 1, j] + pi−1pkp j
11 if q < m[i , j]
12 m[i , j] � q
13 s[i , j] � k
14 return m and s
PD - multiplicação iterada de matrizes
matriz Ai A1 A2 A3 A4 A5 A6
dim. pi−1 × pi 30 × 35 35 × 15 15 × 5 5 × 10 10 × 20 20 × 25
m[2, 5] � min

m[2, 2] + m[3, 5] + p1p2p5 � 0 + 2500 + 35 · 15 · 20 � 13000
m[2, 3] + m[4, 5] + p1p3p5 � 2625 + 1000 + 35 · 5 · 20 � 7125
m[2, 4] + m[5, 5] + p1p4p5 � 4375 + 0 + 35 · 10 · 20 � 11375
PD - multiplicação iterada de matrizes
# Matrix-Chain-Order é O(n3);
# Para mostrar como multiplicar as matrizes, devemos usar a
tabela s em Print-Optimal-Parens:
Print-Optimal-Parens(s , i , j)
1 if i == j
2 print “A”i
3 else print “(”
4 Print-Optimal-Parens(s , i , s[i , j])
5 Print-Optimal-Parens(s , s[i , j] + 1, j)
6 print “)”
PD - multiplicação iterada de matrizes
Print-Optimal-Parens(s , 1, 6) imprime ((A1(A2A3))((A4A5)A6)).
	Programação Dinâmica