Resolução de problemas/Optimal array multiplication sequence

Otimização de multiplicação de matrizes

Dadas as matrizes A e B, e $n$ o número de colunas de A e o número de linhas de B, é possível calcular a matriz $R=A\times B$ usando a seguinte definição:

$R_{i,j}=\sum _{k=1}^{n}A_{i,k}\times B_{k,j}$

As dimensões da matriz R gerada serão, o número de linhas igual ao de A e o número de colunas igual ao de B.

Sejam, então, A de dimensões (x,k) e B de dimensões (k,y), a matriz calculada, C, terá dimensões (x,y). No processo deste cálculo deverão ser feitas $x\times k\times y$ multiplicações, conforme a definição.

Agora, vejamos o caso de três matrizes A, B e C de dimensões (w,x), (x,y) e (y,z), respectivamente. Como a multiplicação de matrizes é uma operação associativa, podemos calcular $R=(A\times B)\times C$ ou $R=A\times (B\times C)$. O resultado será o mesmo em ambos os casos. A diferênça está no custo do cálculo de cada uma das alternativas. Na primeira dela serão necessárias $(w\times x\times y)+(w\times y\times z)$ operações, enquanto que, na segunda, $(x\times y\times z)+(w\times x\times z)$.

Exemplificando, considere w=5, x=10, y=20 e z=35 para o caso acima. Teremos:
Para $R=(A\times B)\times C\Rightarrow (5\times 10\times 20)+(5\times 20\times 35)=1000+3500=4500$
Para $R=A\times (B\times C)\Rightarrow (10\times 20\times 35)+(5\times 10\times 35)=7000+1750=8750$

Pode-se ver que o cálculo de $(A\times B)\times C$ é bem menos custoso (efetua menos operações) e, portanto, preferível.

A questão, então é: como definir a melhor sequência de multiplicação para um grupo de matrizes qualquer?

Este problema possui duas características interessantes: sub-estrutura ótima e sobreposição de sub-problemas. Ou seja, a solução ótima para o problema pode ser encontrada a partir da solução ótima de suas partes (sub-problemas) e o mesmo sub-problema pode ser usado para resolver vários problemas maiores. Assim sendo, a programação dinâmica é uma boa técnica a ser usada para solucioná-lo.

A abordagem usada será bottom-up, onde são solucionados os sub-problemas mais básicos e, partir deles, os demais subproblemas em ordem crescente de complexidade, até atingir a solução do problema dado.

Definida a técnica de programação a ser usada, o próximo passo será a escolha das estruturas de dados. Devido à repetição das dimensões em matrizes vizinhas (o número de colunas na primeira é sempre igual ao número de linhas da segunda) podemos armazenar as dimensões de $n$ matrizes em um vetor $D$, de $n+1$ posições, de modo que as dimensões da matriz $i$ $(0\leq i<n)$ possam ser recuperadas em $D_{i}$ e $D_{i+1}$. Além disso serão usadas duas matrizes quadradas: $M$, de dimensões $(n-1,n-1)$, usada para armazenar a quantidade de multiplicações necessárias em cada sub-problema e a $S$, dimensões $(n,n)$ usada para identificar qual a parentização utilizada.

Em cada $M_{i,j}$, sendo $0\leq i<n$ e $i\leq j<n$, deve ser armazenado o menor custo para se calcular a multiplicação das matrizes $i$ a $j+1$. Desta forma o custo total para a multiplicação de todas a matrizes deverá aparecer em $M_{0,n-2}$ ao final do algoritmo.

Cada $S_{i,j}$, com $0<i\leq n$ e $i<j\leq n$, deve armazenar um valor usado para localizar a posição da multiplicação mais externa a ser feita na multiplicação das matrizes $i$ a $j$. $S_{i,j}=x$ indica que devemos multiplicar o resultado da multiplicação das matrizes $i$ a $j-x-1$ com o resultado da multiplicação das matrizes $j-x$ a $j$.

O primeiro passo para a solução do problema é calcular o custo da multiplicação das matrizes vizinhas. Estes valores serão armazenados na diagonal principal da matriz $M$ da seguinte forma:

 for(i = 0; i < n - 1; i++)
 	M[i][i] = D[i] * D[i + 1] * D[i + 2];

Em seguida, a matriz $M$ deve ser percorrida, diagonalmente, preenchendo as demais posições até obter-se o valor de $M_{0,n-2}$. Para cada posição da matriz deve ser localizada a melhor posição para a multiplicação das matrizes correspondes a partir dos resultados já calculados. A cada atualização de $M$ deve ser feita a atualização correspondente em $S$. O código a seguir demonstra o preenchimento de $M$ e $S$:

for(y = 1; y < n - 1; y++)
{
    for(j = y - 1; j < n - 2; j++)
    {
        i = j - y + 1;
 	M[i][j  +1] = 2147483647;
 	for (x = 1; x <= j - i + 2; x++)
        {
 	    k = ((x-j+i-2)?M[i][j + 1 - x]:0) + ((x - 1)?M[j + 3 - x][j + 1]:0) + (D[i] * D[j + 3 - x] * D[j + 3]);
 	    if(k < M[i][j + 1])
            {
 		M[i][j + 1] = k;
 		S[i][j + 2] = x - 1;
 	    }
        }
    }
}

Tudo pronto! Agora só falta exibir o resultado. A chamada da função parenthesize(0,n-1) exibe a multiplicação parentizada.

 void parenthesize(int i, int j)
{
    if (i != j)
    {
        printf("(");
 	parenthesize(i, j - 1 - S[i][j]);
 	printf(" x ");
 	parenthesize(j - S[i][j],j);
 	printf(")");
    }
    else
 	printf("A%d", i + 1);
}