Cet article décrit l'algorithme du problème de la multiplication de la matrice Java (programmation dynamique). Partagez-le pour votre référence, comme suit:
Description du problème: Étant donné n matrices: a1, a2, ..., an, où ai et ai + 1 sont multipliables, i = 1, 2 ..., n-1. Déterminez l'ordre de calcul du calcul du produit continu de matrice, de sorte que le nombre de multiplications nécessaires pour calculer le produit continu de la matrice dans cet ordre est le moins. Les données d'entrée sont le nombre de matrices et la taille de chaque matrice, et le résultat de sortie est l'ordre de calcul et le nombre minimum de multiplications pour le produit continu de la matrice.
Analyse des problèmes: Étant donné que la multiplication de la matrice satisfait la loi d'association, il peut y avoir de nombreux ordres de calcul différents pour calculer le produit continu de la matrice. Cet ordre de calcul peut être déterminé en ajoutant des supports. Si l'ordre de calcul d'un produit continu matriciel est complètement déterminé, c'est-à-dire que le produit continu a été entièrement entre parenthèses, alors l'algorithme standard pour la multiplication de deux matrices peut être appelé à plusieurs reprises dans cet ordre pour calculer le produit continu de la matrice.
Un produit matriciel complètement parenté peut être défini de manière récursive:
(1) la matrice unique est complètement crochetée;
(2) Le produit Matrix A est complètement crocheté, puis A peut être représenté comme le produit de 2 produits matriciels entièrement entre crochets B et C et supports ajoutés, c'est-à-dire a = (BC)
Par exemple, il existe 5 façons différentes de prendre complètement en charge le produit Matrix A1A2A3A4: (A1 (A2 (A3A4))), (A1 ((A2A3) A4)), ((A1A2) (A3A4)), ((A1 (A2A3)) A4). Chaque méthode de crochetage entièrement correspond à l'ordre de calcul d'un produit connecté à la matrice, qui détermine la quantité de calcul requise pour fabriquer le produit.
Voir l'exemple suivant, calculez la multiplication à trois matrices {a1, a2, a3}; Les dimensions sont de 10 * 100, 100 * 5, 5 * 50 respectivement. Calculez le nombre requis de fois dans cet ordre ((a1 * a2) * a3): 10x100x5 + 10x5x50 = 7500 fois, calculez le nombre requis de fois dans cet ordre (a1 * (a2 * a3)): 10 * 5 * 50 + 10 * 100 * 50 = 75000
La question est donc: comment déterminer l'ordre des opérations afin que le montant du calcul puisse être minimisé.
Idées d'algorithmes:
Exemple: Supposons que vous souhaitiez calculer le produit de multiplication de la matrice A1A2A3A4A5A6, où les dimensions de chaque matrice sont:
A1: 30 * 35; A2: 35 * 15; A3: 15 * 5; A4: 5 * 10; A5: 10 * 20; A6: 20 * 25
Relation récursive:
Le calcul de conception a [i: j], 1≤i≤j≤n, et le nombre minimum de multiplications requise m [i, j], alors la valeur optimale du problème d'origine est M [1, n].
Quand i = j, a [i: j] = ai, donc m [i] [i] = 0, i = 1,2,…, n
Lorsque i <j, si l'ordre optimal de A [i: j] est déconnecté entre ak et ak + 1, i <= k <j, alors: m [i] [j] = m [i] [k] + m [k + 1] [j] + pi-1pkpj. Étant donné que la position du point de déconnexion K n'est pas connue pendant le calcul, K n'a pas encore été déterminé. Cependant, il n'y a que Ji possible pour la position k. Par conséquent, K est la position où la position JI minimise la quantité de calcul.
En résumé, il existe des relations récursives comme suit:
Construisez la solution optimale:
Si la position de déconnexion K du M [i] [J] correspondant est désignée comme S [i] [J], après avoir calculé la valeur optimale M [i] [J], la solution optimale correspondante peut être construite récursive à partir de S [i] [J]. Le nombre dans s [i] [j] montre que la meilleure façon de calculer la chaîne de matrice a [i: j] doit être déconnectée entre la matrice AK et Ak + 1, c'est-à-dire que les parenthèses optimales devraient être (a [i: k]) (a [k + 1: j). Par conséquent, à partir des informations enregistrées par S [1] [n], nous pouvons voir que les parenthèses optimales pour calculer A [1: n] sont (a [1: s [1] [n]]) (a [s [1] [n] +1: n]). En outre, les parenthèses optimales pour A [1: S [1] [S [1] [S [1] [N]]) sont (a [s [1] [s [1] [n]] + 1: s [1] [s [1] [s [1] [s [1] [n]]). De même, il peut être déterminé que les parenthèses optimales d'un [s [1] [n] +1: n] sont cassées à s [s [1] [n] +1] [n] ... si nous continuons à le recourtrer, nous pouvons enfin déterminer les parenthèses complètes optimales d'un [1: n] et construire une solution optimale au problème.
Package Matrix; Matrix de classe publique {public static void matrixChain (int [] p, int n, int [] [] m, int [] [] s) {for (int i = 1; i <= n; i ++) {m [i] [i] = 0; } pour (int r = 2; r <= n; r ++) {pour (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; pour (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 ("Multipliez un" + i + "," + s [i] [j] + "et un" + (s [i] [j] + 1) + "," + j); } public static void main (String [] args) {System.out.println ("Wulin.com Résultats du test:"); Matrix mc = new Matrix (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = nouveau int [n] [n]; int s [] [] = nouveau 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); }}Résultats en cours:
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.