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 , teríamos:

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 é uma matriz , é uma matriz , e é uma matriz . Podemos calcular o numero de operações,

e concluir que o primeiro método é mais eficiente. Com esta informação, o enunciado do problema pode ser refinado, como podemos determinar a melhor ordem para um produto de n matrizes? Poderíamos tentar todas as ordens 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 , calculamos o custo necessário para encontrar cada uma ()(), ()(), e ()(), fazer chamadas recursivas para encontrar o custo mínimo para calcular , , , e . Em seguida, escolhemos o mais eficiente. 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, na implementação do algorítimo, a resposta é igualmente lenta a tentativa de força bruta, dado ao número de trabalhos redundantes sendo performados. Por exemplo, no algoritmo acima a chamada recursiva para encontrar a forma mais eficiente para calcular ambo e . Mas encontrar o melhor custo para computar ABC também requer encontrar o melhor custo para .

Uma solução simples é chamada de memorização(do Inglês Memorization): Ao calcular 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 subsequências diferentes, onde é 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 a partir de 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 , com o comprimento , 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:// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n MatrixChainOrder(int dims[]) { // length[dims] = n + 1 n = dims.length - 1; // m[i,j] = Minimum number of scalar multiplications (i.e., cost) // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j] // The cost is zero when multiplying one matrix for (i = 1; i <= n; i++) m[i, i] = 0;

for (len = 2; len <= n; len++) { // Subsequence lengths for (i = 1; i <= n - len + 1; i++) { j = i + len - 1; m[i, j] = MAXINT; for (k = i; k <= j - 1; k++) { cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j]; if (cost < m[i, j]) { m[i, j] = cost; s[i, j] = k; // Index of the subsequence split that achieved minimal cost

Nota : O primeiro índice para dims é 0 e o primeiro índice para o e é 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:

public class MatrixOrderOptimization { protected int[][]m; protected int[][]s; public void matrixChainOrder(int[] dims) { int n = dims.length - 1; m = new int[n][n]; s = new int[n][n];

for (int lenMinusOne = 1; lenMinusOne < n; lenMinusOne++) { for (int i = 0; i < n - lenMinusOne; i++) { int j = i + lenMinusOne; m[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int cost = m[i][k] + m[k+1][j] + dims[i]*dims[k+1]*dims[j+1]; if (cost < m[i][j]) { m[i][j] = cost; s[i][j] = k;

public void printOptimalParenthesizations() { boolean[] inAResult = new boolean[s.length]; printOptimalParenthesizations(s, 0, s.length - 1, inAResult);

void printOptimalParenthesizations(int[][]s, int i, int j, /* for pretty printing: */ boolean[] inAResult) { if (i != j) { printOptimalParenthesizations(s, i, s[i][j], inAResult); printOptimalParenthesizations(s, s[i][j] + 1, j, inAResult); String istr = inAResult[i] ? "_result " : " "; String jstr = inAResult[j] ? "_result " : " "; System.out.println(" A_" + i + istr + "* A_" + j + jstr); inAResult[i] = true; inAResult[j] = true;

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 , embora eles sejam mais complexos.

Hu & Shing (1981) Um algoritmo publicado em 1981 por Hu e Shing atinge complexidade O(N \log(n)).Hu, TC; Shing, MT (1981) 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 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 matrizes na cadeia de multiplicação há operações binárias e maneiras de colocar parênteses, onde é o ()-ésimo número de Catalan. O algoritmo explora o fato de que há também possíveis triangulações de um polígono com 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. centro|400x400px Para o exemplo abaixo, existem quatro partes: e o resultado final . é uma matriz , é uma matriz , é uma matriz , e o resultado final é uma matriz . O polígono regular para este exemplo é um 4-gono, isto é, um quadrado: centro|125x125px A matriz produto é uma matriz e é uma matriz . As duas possíveis triangulações neste exemplo são: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:

Hu & Shing desenvolveram um algoritmo que encontra a solução ideal para o problema da partição de custo mínimo em .

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 sequência.G. Baumgartner, D. Bernholdt, D. Cociorva, R. Harrison, M. Nooijen, J. Ramanujam and P. Sadayappan. Um caso especial um pouco forçado desse problema é a concatenação de sequência de caracteres de uma lista de cadeias de caracteres. Em C, por exemplo, o custo de concatenar duas cadeias de caracteres de comprimento e usando strcat é , uma vez que precisamos de tempo para encontrar o final da primeira sequência de caracteres e o tempo para copiar a segunda sequê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 sequê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.Heejo Lee, Jong Kim, Sungje Hong, and Sunggu Lee.

Referências

Categoria:Matrizes