Multiplicação de cadeia de matrizes
Multiplicação de cadeia de matrizes (ou problema da ordenação de cadeia de matrizes) é um problema de otimização que pode ser resolvido usando programação dinâmica. Dada uma sequência de matrizes, o objetivo é encontrar a forma mais eficiente de multiplicar essas matrizes. O problema não é na realidade para "realizar" a multiplicação, mas apenas para decidir a sequência de multiplicações das matrizes envolvidas.

Temos muitas opções, pois a multiplicação de matrizes é associativa. Em outras palavras, não importa como por entre parênteses o produto, o resultado obtido será o mesmo. Por exemplo, se tivéssemos quatro matrizes "A", "B", "C", e "D", teríamos:
: (("AB")"C")"D" = (A("A"("BC"))"D") = ("AB")("CD") = "A"(A("BC")"D") = "A"("B"("CD")).
No entanto, a ordem em que se põe entre parênteses o produto afeta o número de operações aritméticas simples necessárias para calcular o produto, ou a "eficiência". 
Por exemplo, suponha que A é uma matriz 10 × 30, B é uma matriz 30 × 5, e C é uma matriz 5 × 60. Então,
: ("AB")"C" = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operações
: "A"("BC") = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operações.
Claramente, o primeiro método é mais eficiente. Com esta informação, o enunciado do problema pode ser refinado, como podemos determinar a melhor parentização de um produto de "n" matrizes? Poderíamos tentar todas as parentizações possíveis (força bruta), exigindo um tempo de execução que é exponencial no número de matrizes, o que é muito lento e impraticável para grandes valores de "n". Uma solução mais rápida para este problema pode ser obtida dividindo o problema em um conjunto de subproblemas relacionados . Através da resolução de subproblemas uma vez e da reutilização dessas soluções, podemos reduzir drasticamente o tempo de execução necessário. Este conceito é conhecido como programação dinâmica.
Q984063
problema de otimização
Concept
Q380679
programação dinâmica
Concept
Q1049914
multiplicar essas matrizes
Concept
Q177251
associativa
Concept
Q850362
força bruta
Concept
Q2393193
tempo de execução
Concept
Q380679
programação dinâmica
Concept
Q917612
Multiplicação de cadeia de matrizes
Concept
+10^^http://www.w3.org/2001/XMLSchema#decimal
10
NUMBER
+30^^http://www.w3.org/2001/XMLSchema#decimal
30
NUMBER
+30^^http://www.w3.org/2001/XMLSchema#decimal
30
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+60^^http://www.w3.org/2001/XMLSchema#decimal
60
NUMBER
+10^^http://www.w3.org/2001/XMLSchema#decimal
10
NUMBER
+30^^http://www.w3.org/2001/XMLSchema#decimal
30
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+10^^http://www.w3.org/2001/XMLSchema#decimal
10
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+60^^http://www.w3.org/2001/XMLSchema#decimal
60
NUMBER
+1500^^http://www.w3.org/2001/XMLSchema#decimal
1500
NUMBER
+3000^^http://www.w3.org/2001/XMLSchema#decimal
3000
NUMBER
+4500^^http://www.w3.org/2001/XMLSchema#decimal
4500
NUMBER
+30^^http://www.w3.org/2001/XMLSchema#decimal
30
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+60^^http://www.w3.org/2001/XMLSchema#decimal
60
NUMBER
+10^^http://www.w3.org/2001/XMLSchema#decimal
10
NUMBER
+30^^http://www.w3.org/2001/XMLSchema#decimal
30
NUMBER
+60^^http://www.w3.org/2001/XMLSchema#decimal
60
NUMBER
+9000^^http://www.w3.org/2001/XMLSchema#decimal
9000
NUMBER
+18000^^http://www.w3.org/2001/XMLSchema#decimal
18000
NUMBER
+27000^^http://www.w3.org/2001/XMLSchema#decimal
27000
NUMBER
instance of