Seguiremos quatro passos para montar o algoritmo da questão, conforme descrito no livro "Introduction to Algorithms, Third Edition", de Thomas H. Cormen, pag. 373.
passo1: encontrar sub-estrutura ótima e usá-la para construir uma solução ótima para o problema a partir das soluções dos sub-problemas. Considere a multiplicação de n matrizes. O custo computacional de multiplicá-las é o mesmo custo que multiplicar as matrizes de 1 a k, mais o custo de multiplicar as matrizes de k+1 a n, mais o custo de multiplicar as matrizes resultantes das duas operações anteriores.
passo2: solução recursiva para em termos de solução dos sub-problemas. Seja 1<=i<=j<=n e m[i,j] o numero mínimo de multiplicações escalares necessários para calcular a multiplicação das matrizes de i a j. O problema é definido recursivamente como: se i=j, o problema é trivial; se i<>j, fazemos uso da estrutura do passo 1, recursivamente. Veja que a tabela m guarda valores calculados para uso posterior da árvore de recursão - programação dinâmica.
passo3: construção de algoritmo recursivo baseado na estrutura dos passos 1 e 2 para se obter o custo mínimo de operações m[1,n] para multiplicar as n matrizes. Além disso, o algoritmo deve também guardar onde realizaram-se as divisões ótimas da cadeia de matrizes: "k" para cada cadeia de matrizes, ou seja, duas a duas, três a três e assim por diante.
passo4: construção da solução ótima a partir da colocação de parêntesis na cadeia de matrizes para indicar a ordem ótima de multiplicação. A ideia é que conseguimos, a partir do momento que gravamos os "k" no passo três, montar um algoritmo recursivo para se colocar os parêntesis ótimos para a multiplicação da cadeia de matrizes
import sys
def f(i,j):
return str(i)+','+str(j)
def matrix_chain_order(p): #a entrada p é caracterizada como o exemplo: matrizes 30x35, 35x15, 15x5 = (30, 35, 15, 5)
n = len(p)-1 # numero de matrizes a serem multiplicadas
m, s = {}, {} # m[i,j] guardará o menor numero de operacoes para se multiplicar as matrizes de i a j;
for i in xrange(1, n+1):
m[f(i, i)] = 0 #salva em m[i,i] o numero de operacoes com uma unica matriz = 0
for l in xrange(2, n+1): # inicia com cadeia de duas matrizes: l=2 e vai aumentando
for i in xrange(1, n-l+2):
j = i+l-1
m[f(i, j)] = sys.maxint #m[i,j] = infinito
for k in xrange(i, j): # obtencao de m[i,j] por meio de solucao de recursao: step 2 pag.374 livro Cormen
q = m[f(i, k)]+m[f(k+1, j)]+p[i-1]*p[k]*p[j] #aqui entra programacao dinamica, pois varios valores da arvore de recursao ja foram calculados e sao trazidos de m
if q<m[f(i, j)]:
m[f(i, j)] = q #obtencao de m otimo para multiplicacao da cadeia de matrizes de i a j
s[f(i, j)] = k #onde ocorreu a divisao otima da cadeia de matrizes de i a j
return m, s
def get_optimal_parens(s, i, j): #step 4 pag 377 livro Cormen
res = ''
if i == j:
return "A"+str(j)
else:
res += "("
res += get_optimal_parens(s, i, s[f(i, j)])
res += get_optimal_parens(s, s[f(i, j)]+1, j)
res += ")"
return res
def main():
p = [30,35,15,5,10,20,25]
m, s = matrix_chain_order(p)
print 'optimal operations number：', m[f(1, len(p)-1)]
print 'optimal parens', get_optimal_parens(s, 1, len(p)-1)
if __name__ == '__main__':
main()