Este artículo describe el algoritmo de problema de multiplicación de matriz Java (programación dinámica). Compártelo para su referencia, como sigue:
Descripción del problema: Dadas n matrices: a1, a2, ..., an, donde ai y ai+1 son multiplicables, i = 1, 2 ..., n-1. Determine el orden de cálculo de calcular el producto continuo de la matriz, de modo que el número de multiplicaciones requeridas para calcular el producto continuo de la matriz en este orden sea el menor. Los datos de entrada son el número de matrices y el tamaño de cada matriz, y el resultado de salida es el orden de cálculo y el número mínimo de multiplicaciones para el producto continuo de la matriz.
Análisis de problemas: dado que la multiplicación de la matriz satisface la ley de asociación, puede haber muchas órdenes de cálculo diferentes para calcular el producto continuo de la matriz. Este orden de cálculo se puede determinar agregando corchetes. Si el orden de cálculo de un producto continuo de la matriz está completamente determinado, es decir, el producto continuo se ha rango completamente entre corchetes, entonces el algoritmo estándar para la multiplicación de dos matrices puede llamarse repetidamente en este orden para calcular el producto continuo de la matriz.
Un producto de matriz completamente entregados se puede definir recursivamente como:
(1) La matriz única está completamente entre corchetes;
(2) El producto de la matriz A está completamente entre paréntesis, luego A se puede representar como el producto de 2 productos de matriz completamente entre corchetes B y C y soportes agregados, es decir, A = (BC)
Por ejemplo, hay 5 formas diferentes de hacer que el producto matriz A1A2A3A4: (A1 (A2 (A3A4)))), (A1 ((A2A3) A4)), ((A1A2) (A3A4)), ((A1 (A2A3))). Cada método de soporte por completo corresponde al orden de cálculo de un producto conectado a la matriz, lo que determina la cantidad de cálculo requerido para hacer el producto.
Vea el siguiente ejemplo, calcule la multiplicación de tres matriz {a1, a2, a3}; Las dimensiones son 10*100, 100*5, 5*50 respectivamente. Calcule el número requerido de veces en este orden ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 veces, calcule el número requerido de veces en este orden (A1*(A2*A3)): 10*5*50+10*100*50 = 75000 veces)
Entonces, la pregunta es: cómo determinar el orden de las operaciones para que la cantidad de cálculo pueda minimizarse.
Ideas de algoritmo:
Ejemplo: Suponga que desea calcular el producto de multiplicación de matriz A1A2A3A4A5A6, donde las dimensiones de cada matriz son:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
Relación recursiva:
El cálculo de diseño A [I: J], 1≤i≤j≤n, y el número mínimo de multiplicaciones requeridas m [i, j], entonces el valor óptimo del problema original es m [1, n].
Cuando i = j, a [i: j] = ai, por lo tanto, m [i] [i] = 0, i = 1,2, ..., n
Cuando i <j, si el orden óptimo de a [i: j] está desconectado entre Ak y Ak+1, i <= k <j, entonces: m [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. Dado que la posición del punto de desconexión K no se conoce durante el cálculo, K aún no se ha determinado. Sin embargo, solo hay JI posible para la posición K. Por lo tanto, K es la posición donde la posición de JI minimiza la cantidad de cálculo.
En resumen, hay relaciones recursivas de la siguiente manera:
Construya la solución óptima:
Si la posición de desconexión K de la M [i] [j] correspondiente se denota como s [i] [j], después de calcular el valor óptimo m [i] [j], la solución óptima correspondiente se puede construir recursivamente a partir de S [i] [j]. El número en S [i] [j] muestra que la mejor manera de calcular la cadena de matriz A [I: J] debe desconectarse entre la matriz AK y AK+1, es decir, las paréntesis óptimas deberían ser (A [I: K]) (A [K+1: J). Por lo tanto, a partir de la información registrada por S [1] [n], podemos ver que las paréntesis óptimas para calcular A [1: N] es (A [1: S [1] [N]]) (A [S [1] [N] +1: N]). Más recursivamente, las paréntesis óptimas para A [1: S [1] [S [1] [S [1] [N]]) son (A [S [1] [S [1] [N]]+1: S [1] [S [1] [S [1] [S [1] [N]]). Del mismo modo, se puede determinar que los paréntesis óptimos de a [S [S [1] [N] +1: N] se rompen en S [S [S [1] [N] +1] [N] ... Si continuamos recurriendo esto, finalmente podemos determinar las paréntesis completas óptimas de A [1: N] y construir una solución óptima al problema.
Matrix de paquete; Matrix de clase pública {public static void matrixchain (int [] p, int n, int [] [] m, int [] [] s) {para (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 traza (int i, int j, int [] [] s) {if (i == j) return; Traza (i, s [i] [j], s); Traza (s [i] [j] + 1, j, s); System.out.println ("multiplicar a" + i + "," + s [i] [j] + "y a" + (s [i] [j] + 1) + "," + j); } public static void main (string [] args) {System.out.println ("Wulin.com Resultados de la prueba:"); Matrix 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); para (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 (); para (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 de ejecución:
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.