Programação
Dinâmica
Multiplicação de Cadeia de Matrizes
1
O Problema


Seja a seqüência (cadeia) <A1, A2,…, An> de n
matrizes. Computar o produto A1A2…An de
forma a minimizar o número de multiplicações
Duas matrizes A e B podem ser multiplicadas
se forem compatíveis


Número de colunas de A = Número de linhas de B
A(p*q) * B(q*r)  C(p*r)

O número de multiplicações é p*q*r
2

Exemplo:

<A1, A2, A3> (10, 100, 5, 50)


((A1A2)A3)  10*100*5 + 10*5*50 = 5000 + 2500 =
7500
(A1(A2A3))  100*5*50 + 10*100*50 = 25000 + 50000
= 75000
3
O Problema



Seja Ai de dimensão pi-1*pi
Encontrar forma de definir parêntesis para
minimizar o número de multiplicações.
Quantas formas diferentes?
(2n)
Impraticável verificar todas as possibilidades
4
Multiplicação de Duas Matrizes
Multiplica-Matriz(A, B)
1. if colunas[A] ≠ linhas[B]
2.
then ERRO
// matrizes incompatíveis
3.
else for i ← 1 to linhas[A]
4.
for j ← 1 to colunas[B]
5.
C[i, j] ← 0
6.
for k ← 1 to colunas[A]
7.
C[i, j] ← C[i, j] + A[i, k].B[k, j]
8.
return C
5
Qual a Idéia?


Notação: Ai..j = resultado da avaliação de
AiAi+1…Aj (i  j)
Qualquer forma de colocar parêntesis em
AiAi+1…Aj deve dividir a cadeia entre Ak e
Ak+1 , para algum inteiro k, i  k < j



Custo = custo de computar Ai..k + custo de computar
Ak+1..j + custo de multiplicar Ai..k e Ak+1..j
A sub-cadeia AiAi+1…Ak deve ter parentização ótima
A sub-cadeia Ak+1Ai+1…Aj deve ter parentização ótima
6
Subestrutura Ótima
A1A2A3A4A5A6A7A8A9
Suponha
((A1A2)(A3((A4A5)A6))) ((A7A8)A9)
Mínimo
Custo_A1..6 +
Custo_A7..9+p0p6p9
É ótima
então
(A1A2) (A3((A4A5)A6))
Deve ser ótima para A1A2A3A4A5A6
senão, se
(A1(A2 A3)) ((A4A5)A6)
É ótima para A1A2A3A4A5A6
então ((A1(A2 A3)) ((A4A5)A6))
((A7A8)A9) Seria melhor do que
((A1A2)(A3((A4A5)A6))) ((A7A8)A9)
7
A Solução



Sub-problema: determinar o custo mínimo de
AiAi+1…Aj (1  i  j  n)
m[i..j] = número mínimo de multiplicações
para calcular a matriz Ai..j
s[i, j] = k, em que m[i, j] = m[i, k] + m[k+1, j] +
pi-1pkpj
se i  j 
0,


m[i, j ]  
{m[i, k ]  m[ k  1, j ]  pi 1 pk p j se i  j 
min


 1 k  j

8





A resposta está em m[1, n]
Necessidade de Programação Dinâmica:
overlap de problemas
Caso base: m[i, i] = 0
Calcular primeiro m[i, i+1], depois m[i, i+2], …
Caminhamento por diagonal
9
O(n3),  (n3) (n3) running time
(n2) space
10
l =3
l=2
35*15*5=
2625
10*20*25
=5000
m[3,5] = min
m[3,4]+m[5,5] + 15*10*20
=750 + 0 + 3000 = 3750
m[3,3]+m[4,5] + 15*5*20
=0 + 1000 + 1500 = 2500
11
Colocando os Parêntesis

s[i, j] armazena o valor de k ótimo para
AiAi+1…Aj, dividindo a matriz em Ak e Ak+1


A1..n  A1..s[1..n] As[1..n]+1..n
A1..s[1..n]  A1..s[1, s[1..n]] As[1, s[1..n]]+1..s[1..n]
12