Resolução de problemas/Optimal array multiplication sequence

Otimização de multiplicação de matrizes

editar

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

 

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   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   ou  . 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   operações, enquanto que, na segunda,  .

Exemplificando, considere w=5, x=10, y=20 e z=35 para o caso acima. Teremos:
Para  
Para  

Pode-se ver que o cálculo de   é 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   matrizes em um vetor  , de   posições, de modo que as dimensões da matriz     possam ser recuperadas em   e  . Além disso serão usadas duas matrizes quadradas:  , de dimensões  , usada para armazenar a quantidade de multiplicações necessárias em cada sub-problema e a  , dimensões   usada para identificar qual a parentização utilizada.

Em cada  , sendo   e  , deve ser armazenado o menor custo para se calcular a multiplicação das matrizes   a  . Desta forma o custo total para a multiplicação de todas a matrizes deverá aparecer em   ao final do algoritmo.

Cada  , com   e  , deve armazenar um valor usado para localizar a posição da multiplicação mais externa a ser feita na multiplicação das matrizes   a  .   indica que devemos multiplicar o resultado da multiplicação das matrizes   a   com o resultado da multiplicação das matrizes   a  .

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   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   deve ser percorrida, diagonalmente, preenchendo as demais posições até obter-se o valor de  . 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   deve ser feita a atualização correspondente em  . O código a seguir demonstra o preenchimento de   e  :

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);
}