Mostrar código-fonte de Resolução de problemas/Optimal array multiplication sequence

==Otimização de multiplicação de matrizes==

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

<math>R_{i,j}=\sum_{k=1}^n A_{i,k} \times B_{k,j}</math>

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 <math>x \times k \times y</math> 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 <math>R=(A \times B) \times C</math> ou <math>R=A \times (B \times C)</math>. 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 <math>(w \times x \times y)+(w \times y \times z)</math> operações, enquanto que, na segunda, <math>(x \times y \times z)+(w \times x \times z)</math>.

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

Pode-se ver que o cálculo de <math>(A \times B) \times C</math> é 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 <math>n</math> matrizes em um vetor <math>D</math>, de <math>n+1</math> posições, de modo que as dimensões da matriz <math>i</math> <math>(0 \leq i < n)</math> possam ser recuperadas em <math>D_i</math> e <math>D_{i+1}</math>. Além disso serão usadas duas matrizes quadradas: <math>M</math>, de dimensões <math>(n-1,n-1)</math>, usada para armazenar a quantidade de multiplicações necessárias em cada sub-problema e a <math>S</math>, dimensões <math>(n,n)</math> usada para identificar qual a parentização utilizada.

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

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

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 <math>M</math> da seguinte forma:
<syntaxhighlight lang="cpp">
 for(i = 0; i < n - 1; i++)
 	M[i][i] = D[i] * D[i + 1] * D[i + 2];
</syntaxhighlight>

Em seguida, a matriz <math>M</math> deve ser percorrida, diagonalmente, preenchendo as demais posições até obter-se o valor de <math>M_{0,n-2}</math>. 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 <math>M</math> deve ser feita a atualização correspondente em <math>S</math>. O código a seguir demonstra o preenchimento de <math>M</math> e <math>S</math>:
<syntaxhighlight lang="cpp">
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;
 	    }
        }
    }
}
</syntaxhighlight>

Tudo pronto! Agora só falta exibir o resultado. A chamada da função ''parenthesize(0,n-1)'' exibe a multiplicação parentizada.
<syntaxhighlight lang="cpp">
 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);
}
</syntaxhighlight>
{{AutoCat}}