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 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³) a partir de O(2ⁿ), 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:

// 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 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:

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 O(n³) , 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.