Resolução de problemas: Problemas de baixa complexidade: Numéricos: Optimal array multiplication sequence

De Wikibooks

[editar] Otimização de multiplicação de matrizes

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

A 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 calculo 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 seqüê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 encontra a partir da solução ótima de suas partes (sub-problemas) e o mesmo sub-problema pode ser usado para resover vários problemas maiores. Assim sendo, a programação dinâmica é uma boa técnica a ser usada para solucioná-lo.

A bordagem usada será bottom-up, onde a são solucionados o 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 estrutudas 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 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 e , deve ser armazendo o menor custo para ser calcular a multilicaçã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 algorítmo.

Cada S_i,j, 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 i a . 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. Este 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 resuldos já calculados. A cada atualiçã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 resutado. A chamada da função parenthesize(0,n-1) exibe a multiplicação parentizada.

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