Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual algoritmo para otimização de multiplicação de cadeia de Matrizes usando DP?

+1 voto
698 visitas
perguntada Mai 23, 2016 em Ciência da Computação por Joao Ricardo (21 pontos)  

Considere o problema de fazer o produto de uma sequencia de matrizes. Escolha a ordem otima de realizar os produtos de forma que você realize o menor numero de produtos (em termos de complexidade computacional). Por exemplo, considere que você quer fazer o produto de três matrizes de ordens n x 1, 1 x n e n x 1. Se você fizer o produto das duas primeiras para depois multiplicar pela terceira, a complexidade computacional e O(n2). Por outro lado, se você fi zer o produto das duas ultimas para depois multiplicar pela primeira, a complexidade computacional e O(n).

Compartilhe

1 Resposta

+1 voto
respondida Mai 23, 2016 por Joao Ricardo (21 pontos)  
selecionada Jun 7, 2016 por Joao Ricardo
 
Melhor resposta

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()
...