O problema da Multiplicação de Cadeia de Matrizes (Matrix Chain Multiplication) pergunta: dada uma sequência de matrizes a serem multiplicadas, qual a ordem de parentetização que minimiza o número total de operações escalares? A multiplicação de matrizes é associativa — (AB)C = A(BC) — mas a ordem dos parênteses pode fazer uma diferença enorme no custo computacional.
Este problema aparece em otimização de consultas em bancos de dados (planos de execução), compiladores (otimização de expressões), computação gráfica (transformações encadeadas) e qualquer sistema que precise encadear operações com custos variáveis.
O Problema
Entrada: Uma sequência de n matrizes A_1, A_2, ..., A_n, onde a matriz A_i tem dimensões p[i-1] x p[i].
Objetivo: Determinar a parentetização que minimiza o número total de multiplicações escalares.
Exemplo:
Matrizes: A(10x30), B(30x5), C(5x60)
Dimensões: p = [10, 30, 5, 60]
Ordem 1: (AB)C
AB: 10*30*5 = 1500 operações -> resultado 10x5
(AB)C: 10*5*60 = 3000 operações
Total: 1500 + 3000 = 4500
Ordem 2: A(BC)
BC: 30*5*60 = 9000 operações -> resultado 30x60
A(BC): 10*30*60 = 18000 operações
Total: 9000 + 18000 = 27000
Ordem ótima: (AB)C com 4500 operações (6x mais eficiente!)
Abordagem Ingênua (Força Bruta)
O número de parentetizações possíveis é dado pelos números de Catalan: C(n-1) = (2(n-1))! / (n! * (n-1)!), que cresce exponencialmente. Para 4 matrizes são 5 formas; para 10 matrizes são 4862; para 20 são mais de 1,7 bilhão.
/// Força bruta: testa todas as parentetizações.
/// Complexidade: O(2^n) — exponencial (números de Catalan).
fn mcm_bruta(p: &[u64], i: usize, j: usize) -> u64 {
// Caso base: uma única matriz, custo zero
if i == j {
return 0;
}
let mut minimo = u64::MAX;
// Tenta cada ponto de divisão k entre i e j
for k in i..j {
let custo = mcm_bruta(p, i, k) // Custo do lado esquerdo
+ mcm_bruta(p, k + 1, j) // Custo do lado direito
+ p[i - 1] * p[k] * p[j]; // Custo de combinar
minimo = minimo.min(custo);
}
minimo
}
fn main() {
let p = vec![10, 30, 5, 60];
let n = p.len() - 1; // 3 matrizes
println!("Custo mínimo: {}", mcm_bruta(&p, 1, n)); // 4500
}
Identificando Subestrutura Ótima
A recorrência para o custo mínimo de multiplicar as matrizes A_i ... A_j:
dp[i][j] = 0 se i == j
dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]) para i <= k < j
O ponto de divisão k divide a cadeia em dois grupos: (A_i ... A_k) e (A_{k+1} ... A_j). O custo de combinar os dois resultados é p[i-1] * p[k] * p[j].
- Subestrutura ótima: a parentetização ótima de
A_i..A_jcontém parentetizações ótimas deA_i..A_keA_{k+1}..A_j. - Subproblemas sobrepostos: subcadeias são compartilhadas entre diferentes partições.
Visualização da Tabela DP
A tabela é preenchida por diagonais (por comprimento crescente da cadeia).
Para p = [10, 30, 5, 60] (matrizes A1(10x30), A2(30x5), A3(5x60)):
j=1 j=2 j=3
+--------+--------+--------+
i=1 | 0 | 1500 | 4500 |
+--------+--------+--------+
i=2 | | 0 | 9000 |
+--------+--------+--------+
i=3 | | | 0 |
+--------+--------+--------+
Preenchimento por diagonais:
Diagonal 0 (comprimento 1): cadeias de 1 matriz
dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0
Diagonal 1 (comprimento 2): cadeias de 2 matrizes
dp[1][2]: k=1 -> p[0]*p[1]*p[2] = 10*30*5 = 1500
dp[2][3]: k=2 -> p[1]*p[2]*p[3] = 30*5*60 = 9000
Diagonal 2 (comprimento 3): cadeia completa
dp[1][3]: k=1 -> dp[1][1] + dp[2][3] + p[0]*p[1]*p[3]
= 0 + 9000 + 10*30*60 = 27000
k=2 -> dp[1][2] + dp[3][3] + p[0]*p[2]*p[3]
= 1500 + 0 + 10*5*60 = 4500 <-- mínimo!
dp[1][3] = 4500 (k_ótimo = 2, ou seja: (A1*A2)*A3)
Para um exemplo maior, p = [40, 20, 30, 10, 30] (4 matrizes):
j=1 j=2 j=3 j=4
+--------+--------+--------+--------+
i=1 | 0 | 24000 | 18000 | 30000 |
+--------+--------+--------+--------+
i=2 | | 0 | 6000 | 12000 |
+--------+--------+--------+--------+
i=3 | | | 0 | 9000 |
+--------+--------+--------+--------+
i=4 | | | | 0 |
+--------+--------+--------+--------+
dp[1][4] = 30000, parentetização: ((A1(A2*A3))*A4)
Complexidade
| Abordagem | Tempo | Espaço | Observação |
|---|---|---|---|
| Força Bruta | O(2^n) Catalan | O(n) pilha | Números de Catalan |
| Top-Down (Memoização) | O(n^3) | O(n^2) | n^2 subproblemas, O(n) cada |
| Bottom-Up (Tabulação) | O(n^3) | O(n^2) | Preenchimento diagonal |
| Otimizado (Hu-Shing) | O(n log n) | O(n) | Algoritmo avançado, raro na prática |
Implementação: Top-Down (Memoização)
use std::collections::HashMap;
/// Multiplicação de cadeia de matrizes com memoização.
fn mcm_memo(
p: &[u64],
i: usize,
j: usize,
cache: &mut HashMap<(usize, usize), u64>,
) -> u64 {
if i == j {
return 0;
}
if let Some(&valor) = cache.get(&(i, j)) {
return valor;
}
let mut minimo = u64::MAX;
for k in i..j {
let custo = mcm_memo(p, i, k, cache)
+ mcm_memo(p, k + 1, j, cache)
+ p[i - 1] * p[k] * p[j];
minimo = minimo.min(custo);
}
cache.insert((i, j), minimo);
minimo
}
fn main() {
let p = vec![10, 30, 5, 60];
let n = p.len() - 1;
let mut cache = HashMap::new();
let resultado = mcm_memo(&p, 1, n, &mut cache);
println!("Custo mínimo: {}", resultado); // 4500
// Exemplo maior
cache.clear();
let p2 = vec![40, 20, 30, 10, 30];
let n2 = p2.len() - 1;
let resultado2 = mcm_memo(&p2, 1, n2, &mut cache);
println!("Custo mínimo: {}", resultado2); // 30000
}
Implementação: Bottom-Up (Tabulação)
/// Multiplicação de cadeia de matrizes com tabulação.
/// Retorna o custo mínimo e a tabela de pontos de divisão.
fn mcm_tabular(p: &[u64]) -> (u64, Vec<Vec<u64>>, Vec<Vec<usize>>) {
let n = p.len() - 1; // Número de matrizes
// dp[i][j] = custo mínimo para multiplicar A_i ... A_j
let mut dp = vec![vec![0u64; n + 1]; n + 1];
// div[i][j] = ponto de divisão ótimo para dp[i][j]
let mut div = vec![vec![0usize; n + 1]; n + 1];
// Preenche por comprimento crescente da cadeia
for comprimento in 2..=n {
for i in 1..=n - comprimento + 1 {
let j = i + comprimento - 1;
dp[i][j] = u64::MAX;
// Testa cada ponto de divisão
for k in i..j {
let custo = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if custo < dp[i][j] {
dp[i][j] = custo;
div[i][j] = k;
}
}
}
}
(dp[1][n], dp, div)
}
fn main() {
let p = vec![10, 30, 5, 60];
let (custo, _dp, _div) = mcm_tabular(&p);
println!("Custo mínimo: {}", custo); // 4500
let p2 = vec![40, 20, 30, 10, 30];
let (custo2, _dp2, _div2) = mcm_tabular(&p2);
println!("Custo mínimo: {}", custo2); // 30000
// Exemplo com 6 matrizes
let p3 = vec![30, 35, 15, 5, 10, 20, 25];
let (custo3, _dp3, _div3) = mcm_tabular(&p3);
println!("Custo mínimo: {}", custo3); // 15125
}
Otimização de Espaço
Diferente de Fibonacci e mochila, a multiplicação de cadeia de matrizes não pode ser facilmente otimizada para espaço O(n). Cada célula dp[i][j] pode depender de qualquer célula na mesma linha ou coluna, exigindo a tabela completa O(n^2). O algoritmo de Hu-Shing alcança O(n log n) tempo e O(n) espaço, mas é significativamente mais complexo de implementar.
Para fins práticos, O(n^2) de espaço raramente é um problema — o gargalo está no tempo O(n^3).
Reconstruindo a Solução
Para reconstruir a parentetização ótima, usamos a tabela div:
/// Reconstrói e imprime a parentetização ótima.
fn imprimir_parentetizacao(div: &[Vec<usize>], i: usize, j: usize) -> String {
if i == j {
return format!("A{}", i);
}
let k = div[i][j];
let esquerda = imprimir_parentetizacao(div, i, k);
let direita = imprimir_parentetizacao(div, k + 1, j);
format!("({} x {})", esquerda, direita)
}
fn main() {
let p = vec![10, 30, 5, 60];
let (custo, _dp, div) = mcm_tabular(&p);
let parentetizacao = imprimir_parentetizacao(&div, 1, p.len() - 1);
println!("Custo: {} -> {}", custo, parentetizacao);
// Custo: 4500 -> ((A1 x A2) x A3)
let p2 = vec![40, 20, 30, 10, 30];
let (custo2, _dp2, div2) = mcm_tabular(&p2);
let par2 = imprimir_parentetizacao(&div2, 1, p2.len() - 1);
println!("Custo: {} -> {}", custo2, par2);
// Custo: 30000 -> ((A1 x (A2 x A3)) x A4)
let p3 = vec![30, 35, 15, 5, 10, 20, 25];
let (custo3, _dp3, div3) = mcm_tabular(&p3);
let par3 = imprimir_parentetizacao(&div3, 1, p3.len() - 1);
println!("Custo: {} -> {}", custo3, par3);
// Custo: 15125 -> ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
}
fn mcm_tabular(p: &[u64]) -> (u64, Vec<Vec<u64>>, Vec<Vec<usize>>) {
let n = p.len() - 1;
let mut dp = vec![vec![0u64; n + 1]; n + 1];
let mut div = vec![vec![0usize; n + 1]; n + 1];
for comprimento in 2..=n {
for i in 1..=n - comprimento + 1 {
let j = i + comprimento - 1;
dp[i][j] = u64::MAX;
for k in i..j {
let custo = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
if custo < dp[i][j] {
dp[i][j] = custo;
div[i][j] = k;
}
}
}
}
(dp[1][n], dp, div)
}
Exemplo Completo: Multiplicação Real de Matrizes
Para demonstrar que a ordem realmente importa, podemos simular a multiplicação:
/// Representa uma matriz como Vec<Vec<f64>>.
/// Multiplica duas matrizes e conta as operações escalares.
fn multiplicar(
a: &Vec<Vec<f64>>,
b: &Vec<Vec<f64>>,
ops: &mut u64,
) -> Vec<Vec<f64>> {
let linhas_a = a.len();
let colunas_a = a[0].len();
let colunas_b = b[0].len();
let mut resultado = vec![vec![0.0; colunas_b]; linhas_a];
for i in 0..linhas_a {
for j in 0..colunas_b {
for k in 0..colunas_a {
resultado[i][j] += a[i][k] * b[k][j];
*ops += 1; // Conta cada multiplicação escalar
}
}
}
resultado
}
fn main() {
// Matrizes com dimensões 10x30, 30x5, 5x60
let a = vec![vec![1.0; 30]; 10]; // 10x30
let b = vec![vec![1.0; 5]; 30]; // 30x5
let c = vec![vec![1.0; 60]; 5]; // 5x60
// Ordem 1: (AB)C
let mut ops1 = 0;
let ab = multiplicar(&a, &b, &mut ops1);
let _abc1 = multiplicar(&ab, &c, &mut ops1);
println!("(AB)C: {} operações", ops1); // 4500
// Ordem 2: A(BC)
let mut ops2 = 0;
let bc = multiplicar(&b, &c, &mut ops2);
let _abc2 = multiplicar(&a, &bc, &mut ops2);
println!("A(BC): {} operações", ops2); // 27000
println!("Razão: {:.1}x mais eficiente", ops2 as f64 / ops1 as f64);
}
Exercícios Práticos
Contagem de parentetizações: Calcule quantas parentetizações distintas existem para
nmatrizes. Implemente tanto por recursão com memoização quanto pela fórmula dos números de Catalan.Custo máximo: Em vez de minimizar, encontre a parentetização que maximiza o número de operações. Útil para entender o pior caso.
Cadeia com custos variáveis: Generalize para o caso onde multiplicar matrizes de dimensões
p x q x rtem custow(p,q,r)arbitrário (não necessariamentep*q*r).Triangulação de polígono: O problema da triangulação ótima de um polígono convexo tem a mesma estrutura recursiva. Implemente-o usando a mesma abordagem de DP.
Veja Também
- Vec — Vetores dinâmicos — base para as matrizes e tabela DP
- Arrays — Tamanho fixo — alternativa para matrizes de tamanho conhecido
- Tipos Numéricos — tipos usados nas dimensões e contagens
- Fibonacci com DP — introdução a programação dinâmica
- Problema da Mochila — outro clássico de DP com reconstrução
- Soma de Subconjuntos — outro problema de DP com tabela bidimensional