# 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:
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$:
Tudo pronto! Agora só falta exibir o resultado. A chamada da função parenthesize(0,n-1) exibe a multiplicação parentizada.