Este artigo descreve o algoritmo Java Matrix Multiplication Problem (Dynamic Programming). Compartilhe -o para sua referência, como segue:
Descrição do problema: dadas n matrizes: A1, A2, ..., An, onde ai e ai+1 são multiplicáveis, i = 1, 2 ..., n-1. Determine a ordem de cálculo do cálculo do produto contínuo da matriz, para que o número de multiplicações necessárias para calcular o produto contínuo da matriz nessa ordem seja o mínimo. Os dados de entrada são o número de matrizes e o tamanho de cada matriz, e o resultado da saída é a ordem de cálculo e o número mínimo de multiplicações para o produto contínuo da matriz.
Análise de problemas: Como a multiplicação da matriz satisfaz a lei da associação, pode haver muitas ordens de cálculo diferentes para calcular o produto contínuo da matriz. Esta ordem de cálculo pode ser determinada adicionando colchetes. Se a ordem de cálculo de um produto contínuo da matriz estiver completamente determinada, ou seja, o produto contínuo foi totalmente entre colchetes, o algoritmo padrão para multiplicação de duas matrizes poderá ser chamado repetidamente nesta ordem para calcular o produto contínuo da matriz.
Um produto de matriz completamente parênteses pode ser definido recursivamente como:
(1) a matriz única é completamente colcheada;
(2) O produto Matrix A é completamente colcário, então A pode ser representado como o produto de 2 produtos Matrix completamente entre colchetes B e C e colchetes adicionados, ou seja, a = (BC)
Por exemplo, existem 5 maneiras diferentes de proteger completamente o produto da matriz A1A2A3A4: (A1 (A2 (A3A4))), (A1 ((A2A3) A4)), ((a1a2) (A3A4)), ((a1 (a2a3)) a4). Cada método de suporte completo corresponde à ordem de cálculo de um produto conectado à matriz, que determina a quantidade de cálculo necessária para fabricar o produto.
Consulte o exemplo a seguir, calcule a multiplicação de três matrizes {A1, A2, A3}; As dimensões são 10*100, 100*5, 5*50, respectivamente. Calcule o número necessário de vezes nesta ordem ((a1*a2)*a3): 10x100x5+10x5x50 = 7500 vezes, calcule o número necessário de vezes nesta ordem (a1*(a2*a3)): 10*5*50+10*100*50 = 75000 vezes
Portanto, a questão é: como determinar a ordem das operações para que a quantidade de cálculo possa ser minimizada.
Ideias de algoritmo:
Exemplo: Suponha que você queira calcular o produto de multiplicação da matriz A1A2A3A4A5A6, onde são as dimensões de cada matriz:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
Relacionamento recursivo:
O cálculo do projeto a [i: j], 1≤i≤j≤n e o número mínimo de multiplicações necessárias m [i, j], então o valor ideal do problema original é m [1, n].
Quando i = j, a [i: j] = ai, portanto, m [i] [i] = 0, i = 1,2,…, n
Quando i <j, se a ordem ideal de a [i: j] estiver desconectada entre Ak e Ak+1, i <= k <j, então: m [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. Como a posição do ponto de desconexão K não é conhecida durante o cálculo, K ainda não foi determinado. No entanto, há apenas ji possível para a posição K. Portanto, k é a posição em que a posição JI minimiza a quantidade de cálculo.
Em resumo, existem relacionamentos recursivos da seguinte forma:
Construa a solução ideal:
Se a posição de desconexão K do m [i] [j] correspondente for denotada como s [i] [j], depois de calcular o valor ideal m [i] [j], a solução ideal correspondente poderá ser construída recursivamente a partir de s [i] [j]. O número em s [i] [j] mostra que a melhor maneira de calcular a cadeia matricial A [i: j] deve ser desconectada entre a matriz AK e AK+1, ou seja, os parênteses ideais devem ser (a [i: k]) (a [k+1: j). Portanto, a partir das informações registradas por S [1] [N], podemos ver que os parênteses ideais para calcular a [1: n] são (a [1: s [1] [n]]) (a [s [1] [n] +1: n]). Ainda mais recursivamente, os parênteses ideais para [1: s [1] [s [1] [s [1] [n]]) são (a [s [1] [s [1] [n]]+1: s [1] [s [s] [s [s] [s [1] [n]]). Da mesma forma, pode -se determinar que os parênteses ideais de A [s [1] [n] +1: n] estão quebrados em s [s [1] [n] +1] [n] ... Se continuarmos a recorrir, podemos finalmente determinar os parênteses completos completos de A [1: n] e construir uma solução ideal para o problema.
matriz de pacote; classe pública matriz {public static void matrixChain (int [] p, int n, int [] [] m, int [] [] s) {for (int i = 1; i <= n; i ++) {m [i] [i] = 0; } para (int r = 2; r <= n; r ++) {for (int i = 1; i <= n-r+1; i ++) {int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; s [i] [j] = i; for (int k = i+1; k <j; k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; if (t <m [i] [j]) {m [i] [j] = t; s [i] [j] = k; }}}}} public static void traceback (int i, int j, int [] [] s) {if (i == j) return; Traceback (i, s [i] [j], s); Traceback (s [i] [j] + 1, j, s); System.out.println ("multiplique a" + i + "," + s [i] [j] + "e a" + (s [i] [j] + 1) + "," + j); } public static void main (string [] args) {System.out.println ("Wulin.com Resultados dos testes:"); Matriz MC = new Matrix (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = new int [n] [n]; int s [] [] = new int [n] [n]; int l = p.Length-1; Mc.MatrixChain (P, L, M, S); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (m [i] [j]+"/t"); } System.out.println (); } System.out.println (); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (s [i] [j]+""); } System.out.println (); } mc.traceback (1, 6, s); }}Resultados em execução:
Para obter mais informações sobre os algoritmos Java, os leitores interessados neste site podem visualizar os tópicos: "Estrutura de dados Java e tutorial de algoritmo", "Resumo das dicas de nó da operação Java Dom", "Resumo de dicas de operação de Java e Operação de Java" e "Resumo de Java cache" Tips "TIPS"
Espero que este artigo seja útil para a programação Java de todos.