# 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.

## Um Algoritmo de Programação Dinâmica

Para começar, vamos assumir que tudo o que realmente quero saber é o custo mínimo, ou o número mínimo de operações aritméticas, necessário para multiplicar as matrizes. Se estamos apenas fazendo a multiplicação de duas matrizes, só há uma maneira de multiplicar, de modo que o mínimo custo é o custo de fazer isso. Em geral, podemos encontrar o custo mínimo usando o seguinte algoritmo recursivo:
* Tome a sequência de matrizes e separe-a em duas subsequências.
* Encontre o custo mínimo de multiplicar cada subsequência.
* Adicione esses custos, e adicione o custo de multiplicar as duas matrizes resultantes.
* Faça isso para cada posição possível na qual a sequência de matrizes pode ser dividida, e tome o mínimo sobre todos eles.
Por exemplo, se temos quatro matrizes ABCD, calculamos o custo necessário para encontrar cada uma (A)(BCD), (AB)(CD), e (ABC)(D), fazer chamadas recursivas para encontrar o custo mínimo para calcular ABC, AB, CD, e BCD. Em seguida, escolhemos o melhor. Melhor ainda, isso produz não apenas o custo mínimo, mas também demonstra a melhor maneira de fazer a multiplicação: agrupe-o da maneira que gere o menor custo total, e faça o mesmo para cada fator.
No entanto, se implementarmos esse algoritmo, vamos descobrir que ele é tão lento quanto o modo ingênuo de tentar todas as permutações! O que deu errado? A resposta é que estamos fazendo um monte de trabalho redundante. Por exemplo, no algoritmo acima fizemos uma chamada recursiva para encontrar o melhor custo para computar ambos ABC e AB. Mas encontrar o melhor custo para computar ABC também requer encontrar o melhor custo para AB. À medida que a recursão aprofunda, mais e mais desse tipo de repetição desnecessária ocorre.
Uma solução simples é chamada de memoização(do Inglês Memoization): cada vez que calculamos o custo mínimo necessário para multiplicar uma determinada subsequência, podemos salvá-lo. Se em alguma vez precisarmos calculá-lo novamente, basta recuperar o valor salvo, e não o recalculamos. Como há cerca de n$^2$/2 subsequências diferentes, onde n é o número de matrizes, o espaço necessário para fazer isso é razoável. Pode ser mostrado que este simples truque traz o tempo de execução para baixo a O(n$^3$) a partir de O(2$^n$), que é mais eficiente do que o bastante para aplicações reais. Isso é a programação dinâmica top-down.
A seguinte abordagem bottom-up calcula, para cada 2 ≤ k ≤ n, os custos mínimos de todas as subsequências de comprimento k, usando os custos de subsequências menores já calculado. Tem o mesmo tempo de execução assintótico e não requer recursão.
Pseudocódigo:
* Nota : O primeiro índice para dims é 0 e o primeiro índice para o m e s é 1
Uma implementação em java utilizando índices de matrizes com base zero, juntamente com a conveniência do método para imprimir as ordens das operações resolvidas:
No final deste programa, temos o custo mínimo para a sequência completa.

## Algoritmos Mais Eficientes

Existem algoritmos que são mais eficientes que o algoritmo de programação dinâmica O(n$^3$) , embora eles sejam mais complexos.

### Hu & Shing (1981)

Um algoritmo publicado em 1981 por Hu e Shing atinge complexidade O(n log n). Eles mostraram como a multiplicação de cadeias de matrizes é um problema que pode ser transformado (ou reduzido) para o problema da triangulação de um polígono regular. O polígono é orientado de tal forma que há uma horizontal inferior do lado, chamado base, que representa o resultado final. Os outros n lados do polígono, no sentido dos ponteiros do relógio, representam as matrizes. Os vértices em cada extremidade de um lado são as dimensões da matriz representada por esse lado. Com n matrizes na cadeia de multiplicação há n-1 operações binárias e C$_{n-1}$ maneiras de colocar parênteses, onde C$_{n-1}$ é o (n-1)-ésimo número de Catalan. O algoritmo explora o fato de que há também C$_{n-1}$ possíveis triangulações de um polígono com n+1 lados.
Estas imagens ilustram triangulações possíveis de um hexágono. Estes correspondem a diferentes maneiras que os parênteses podem ser colocados para ordenar a multiplicação de 5 matrizes.
Para o exemplo abaixo, existem quatro partes: A, B, C e o resultado final ABC. A é uma matriz 10×30, B é uma matriz 30×5, C é uma matriz 5×60, e o resultado final é uma matriz 10×60. O polígono regular para este exemplo é um 4-gono, isto é, um quadrado:
A matriz produto AB é uma matriz 10x5 e BC é uma matriz 30x60. As duas possíveis triangulações neste exemplo são:
* Polígono representação de (AB)C
* Polígono representação de UM(BC)
O custo de um único triângulo em termos do número de multiplicações necessárias é o produto dos seus vértices. O custo total de uma determinada triangulação do polígono é a soma dos custos de todos os seus triângulos:
    (AB)C: (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 multiplicações
    Um(BC): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 multiplicações
Hu & Shing desenvolveram um algoritmo que encontra a solução ideal para o problema da partição de custo mínimo em O(n log n).

## Generalizações

O problema da multiplicação de cadeias de matrizes pode ser generalizado para um problema mais abstrato: dada uma sequência linear de objetos, uma operação binária associativa sobre os objetos, e uma maneira de calcular o custo de executar a operação em quaisquer dois objetos (bem como todos os resultados parciais), calcular o modo de custo mínimo de agrupar os objetos para aplicar a operação sobre a seqüência. Um caso especial um pouco forçado desse problema é a concatenação de seqüência de caracteres de uma lista de cadeias de caracteres. Em C, por exemplo, o custo de concatenar duas cadeias de caracteres de comprimento m e n usando strcat é O(m + n), uma vez que precisamos de O(m) tempo para encontrar o final da primeira seqüência de caracteres e O(n) o tempo para copiar a segunda seqüência de caracteres para o fim. Usando esta função de custo, podemos escrever um algoritmo de programação dinâmica para encontrar o caminho mais rápido para concatenar uma seqüência de cadeias de caracteres. No entanto, esta optimização é bastante inútil, porque podemos facilmente concatenar cadeias de caracteres em um tempo proporcional à soma de seus comprimentos. Um problema semelhante existe para listas encadeadas.
Outra generalização é resolver o problema quando processadores paralelos estão disponíveis. Neste caso, em vez de adicionar os custos de computação de cada fator de um produto matricial, podemos tomar o máximo porque nós podemos fazê-las simultaneamente. Isso pode afetar drasticamente o custo mínimo e o agrupamento final ideal; agrupamentos mais "equilibrados" que mantêm todos os processadores ocupados são preferidos. Há abordagens ainda mais sofisticadas.