Matrix Chain Multiplication
Uma cadeia de matrizes é descrita por dims: a matriz i tem dims[i] linhas e dims[i+1] colunas, então cada matriz se encaixa na próxima. Multiplicar uma matriz p × q por uma matriz q × r requer p × q × r multiplicações escalares e resulta em uma matriz p × r. Todas as formas de colocar os parênteses dão o mesmo produto final, mas não com o mesmo custo. Retorne o menor número de multiplicações escalares necessário para multiplicar toda a cadeia.
Função
- dimsinteger-array
- os tamanhos ao longo da cadeia: a matriz i tem dimensões dims[i] × dims[i+1]
- Retornainteger
- o menor número de multiplicações escalares necessárias para multiplicar toda a cadeia
Restrições
2 ≤ dims.length ≤ 100, portanto, a cadeia contém entre 1 e 99 matrizes.1 ≤ dims[i] ≤ 100- A resposta é no máximo 98 × 106, bem dentro do limite de um inteiro de 32 bits com sinal.
Exemplos
- Entrada
- dims = [4, 10, 3, 12]
- Saída
- 264
- Explicação
- Multiplicar as duas primeiras custa 4 × 10 × 3 = 120 e resulta em uma matriz 4 × 3, que, multiplicada pela matriz 3 × 12, acrescenta 144: 264. A outra ordem custa 360 + 480 = 840.
- Entrada
- dims = [6, 2, 7, 3, 5]
- Saída
- 132
- Explicação
- Multiplique 2 × 7 por 7 × 3 (42), o resultado de 2 × 3 por 3 × 5 (30), depois 6 × 2 pelo resultado de 2 × 5 (60): 132 no total.
- Entrada
- dims = [3, 7]
- Saída
- 0
- Explicação
- Há apenas uma matriz, 3 × 7, então nada é multiplicado e o custo é 0.
Para ir além
Você também consegue contar quantas formas diferentes de parentetizar atingem o custo mínimo?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Esqueça a primeira multiplicação e pense na última. Qualquer que seja a ordem escolhida, a etapa final multiplica o produto de alguma parte à esquerda da cadeia pelo produto do restante.
O produto das matrizes entre dois limites
lefterighté sempre uma matrizdims[left] × dims[right]. Portanto, se a última etapa dividir esse trecho no limitesplit, o custo serádims[left] × dims[split] × dims[right], e as duas partes serão cópias menores do mesmo problema.Armazene em
best[left][right]a maneira mais barata de multiplicar as matrizes entre os limiteslefteright(0 para uma única matriz). Esse é o mínimo, considerando cadasplitestritamente entre eles, debest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]. Calcule os trechos mais estreitos antes dos mais largos.
Solução
A ordem altera o custo: 264 contra 840 no primeiro exemplo. Observe a última multiplicação. Ela une os produtos de uma parte à esquerda e de uma parte à direita da cadeia, e cada parte é o mesmo problema em uma cadeia mais curta. Uma tabela sobre os trechos da cadeia resolve cada um uma única vez, em tempo O(n³).
Tente cada divisão com recursão simples
Correta, mas não termina nos maiores testes
Intuição
Numere os limites da cadeia de 0 a m-1, onde m = dims.length: o limite k tem tamanho dims[k]. As matrizes entre os limites left e right se multiplicam, em qualquer ordem, formando uma matriz dims[left] × dims[right]. Portanto, se a última etapa divide esse trecho em split, seu custo é dims[left] × dims[split] × dims[right], independentemente do que aconteceu dentro dos dois blocos. Cada bloco deve ser construído com o menor custo possível, então cheapest(left, right) é a menor soma dos custos dos dois blocos mais essa última etapa, considerando todos os valores de split. Testar todas as possibilidades para a última etapa garante que o resultado esteja correto.
O algoritmo resolve os mesmos trechos repetidamente: n matrizes exigem 3^(n-1) chamadas, cerca de 1.2 × 10^9 para 20 matrizes, enquanto há apenas cerca de m²/2 trechos diferentes.
Algoritmo
- Escreva
cheapest(left, right)para as matrizes entre os limiteslefteright. - Se
right - left < 2, há uma matriz: retorne 0. - Para cada
splitestritamente entre eles, somecheapest(left, split),cheapest(split, right)edims[left] × dims[split] × dims[right]. - Retorne a menor soma.
- A resposta é
cheapest(0, m-1).
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)Recursão com memoização
Intuição
Uma chamada depende apenas de left e right. Salve o resultado em memo[left][right], com cada célula começando em -1, um valor que nenhum custo real pode assumir, e as chamadas posteriores leem a célula em vez de fazer recursão. Cada um dos cerca de m²/2 pares é resolvido uma vez com menos de m divisões: O(n³), ou 161.700 verificações de divisão para 99 matrizes. A recursão nunca é mais profunda do que o comprimento da cadeia, então 100 limites cabem em qualquer pilha de chamadas.
Algoritmo
- Aloca
memocommlinhas emcolunas, com todas as células iguais a -1. - Em
cheapest(left, right), um trecho de uma matriz retorna 0, e uma célula diferente de -1 retorna seu custo salvo. - Caso contrário, calcula o custo de cada
splitexatamente como a recursão simples faz e obtém o mínimo. - Grava esse mínimo em
memo[left][right]antes de retorná-lo. - A resposta é
cheapest(0, m-1).
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)Preencha a tabela esticando a largura
Intuição
Cada célula depende apenas de trechos mais estreitos, então os loops podem preencher best[left][right] da menor para a maior largura. A largura 1 corresponde a uma única matriz e permanece em 0; quando você chega a um trecho mais largo, as duas partes de cada divisão já foram calculadas. Com dims = [6, 2, 7, 3, 5]:
- Largura 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Largura 3:
best[0][3]é 78 (divisão 1: 0 + 42 + 36),best[1][4]é 72 (divisão 3: 42 + 0 + 30). - Largura 4: as divisões 1, 2 e 3 resultam em 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 e 78 + 0 + 90 = 168, então
best[0][4] = 132.
A divisão principal na fronteira 1 significa que a matriz 6 × 2 é multiplicada por último, como no segundo exemplo. O tempo e a memória são iguais aos da versão com memoização, sem recursão.
Algoritmo
- Defina
m = dims.lengthe aloque uma tabelam × mbestpreenchida com zeros. - Percorra
widthde 2 am-1. Dentro desse laço, percorraleftem ordem crescente a partir de 0 enquantoright = left + widthainda estiver dentro dos limites. - Para esse trecho, calcule
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]para cadasplitdeleft+1aright-1e armazene o mínimo embest[left][right]. - A resposta está em
best[0][m-1].
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
Armadilhas e casos extremos
- Multiplicar primeiro o par mais barato. Em
[10, 10, 1, 9], o último par é o mais barato (90), mas a etapa seguinte custa 900, totalizando 990. Multiplicar primeiro o primeiro par custa 190. - Ler a resposta da célula errada.
dimstem uma entrada a mais que o número de matrizes, então a resposta ébest[0][m-1], nãobest[0][m]. - Percorrer
leftem ordem crescente no loop externo. A linhaleftentão lêbest[split][right]de uma linha posterior que ainda é 0. Coloque a largura no loop externo ou conteleftem ordem decrescente. - Não considerar a matriz única.
[3, 7]deve retornar 0 e, em R, o loop2:(m-1)se transforma em2:1e é executado ao contrário, então proteja esse caso.
Perguntas frequentes3
Qual é a complexidade de tempo da multiplicação de cadeias de matrizes?
A tabela tem cerca de n²/2 intervalos, e cada um tenta até n divisões, então a programação dinâmica é executada em tempo O(n³) com memória O(n²). A recursão simples, sem memorização, faz 3^(n-1) chamadas para n matrizes.
Por que a ordem da multiplicação de matrizes importa?
A multiplicação de matrizes é associativa, então (AB)C e A(BC) produzem a mesma matriz, mas as matrizes intermediárias têm tamanhos diferentes. No primeiro exemplo, (AB)C cria uma matriz 4 × 3 e custa 264, enquanto A(BC) cria uma matriz 10 × 12 e custa 840.
Como encontrar a própria parentização ideal?
Armazene a divisão vencedora em choice[left][right] ao lado de best[left][right]. Para imprimir, uma única matriz imprime seu nome; um trecho mais longo imprime um parêntese de abertura, a parte até choice[left][right], a parte depois dela e um parêntese de fechamento. Isso adiciona memória O(n²).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def matrixChainOrder(dims):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
dims = [4, 10, 3, 12]
Saída Esperada
264