Dieser Artikel beschreibt den Algorithmus zur Java -Matrix -Multiplikationsproblem (dynamischer Programmierung). Teilen Sie es für Ihre Referenz wie folgt weiter:
Problembeschreibung: Angegebene n Matrizen: A1, A2, ..., an, wobei Ai und Ai+1 multiplikativ sind, i = 1, 2 ..., n-1. Bestimmen Sie die Berechnung der Berechnung der Matrix -kontinuierliche Produkte, so dass die Anzahl der zur Berechnung des Matrix kontinuierlichen Produkts in dieser Reihenfolge erforderlichen Multiplikationen am wenigsten ist. Die Eingabedaten sind die Anzahl der Matrizen und die Größe jeder Matrix, und das Ausgabeergebnis ist die Berechnungsreihenfolge und die minimale Anzahl von Multiplikationen für das kontinuierliche Produkt der Matrix.
Problemanalyse: Da die Matrixmultiplikation das Gesetz des Vereins erfüllt, kann es viele verschiedene Berechnungsaufträge geben, um das kontinuierliche Produkt der Matrix zu berechnen. Diese Berechnungsreihenfolge kann durch Hinzufügen von Klammern bestimmt werden. Wenn die Reihenfolge der Berechnung eines Matrix -kontinuierlichen Produkts vollständig bestimmt wird, dh das kontinuierliche Produkt wurde vollständig festgelegt, kann der Standardalgorithmus zur Multiplikation von zwei Matrizen wiederholt in dieser Reihenfolge aufgerufen werden, um das kontinuierliche Matrix -Produkt zu berechnen.
Ein komplett auftretendes Matrixprodukt kann rekursiv definiert werden als:
(1) Die Einzelmatrix ist vollständig festgehalten;
(2) Das Matrixprodukt A ist vollständig klammert, dann kann A als Produkt von 2 vollständig klammernden Matrixprodukten B und C dargestellt und Klammern hinzugefügt werden, dh a = (BC)
Zum Beispiel gibt es 5 verschiedene Möglichkeiten, das Matrixprodukt A1A2A3A4 vollständig zu klammern: (A1 (A2 (A3A4)), (A1 ((A2A3) A4), ((A1A2) (A3A4), ((A1 (A2A3)) A4. Jede Methode zur vollständigen Klammerung entspricht der Berechnungsreihenfolge eines von Matrix verbundenen Produkts, das die Berechnung bestimmt, die zur Herstellung des Produkts erforderlich ist.
Siehe das folgende Beispiel, berechnen Sie die drei Matrix -Multiplikation {A1, A2, A3}; Die Abmessungen betragen 10*100, 100*5, 5*50. Berechnen Sie die erforderliche Anzahl in dieser Reihenfolge ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 Mal, berechnen Sie die erforderliche Anzahl in dieser Reihenfolge (a1*(a2*a3): 10*5*50+10*100*50 = 75000 -mal
Die Frage lautet also: So bestimmen Sie die Reihenfolge der Operationen, damit der Berechnungsbetrag minimiert werden kann.
Algorithmus -Ideen:
Beispiel: Angenommen, Sie möchten das Matrix -Multiplikationsprodukt A1A2A3A4A5A6 berechnen, wobei die Abmessungen jeder Matrix sind:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
Rekursive Beziehung:
Die Entwurfsberechnung A [I: J], 1 ≤ i ≤ j ≤ N und die minimale Anzahl von Multiplikationen, die m [i, j] erforderlich sind, ist der optimale Wert des ursprünglichen Problems M [1, n].
Wenn i = j, a [i: j] = ai, daher m [i] [i] = 0, i = 1,2,…, n
Wenn ich <j, wenn die optimale Reihenfolge eines [i: j] zwischen AK und AK+1 getrennt ist, dann: M [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. Da die Position des Trennungspunkts k während der Berechnung nicht bekannt ist, wurde K noch nicht bestimmt. Für die K -Position ist jedoch nur JI möglich. Deshalb ist k die Position, in der die JI -Position den Berechnungsbetrag minimiert.
Zusammenfassend gibt es rekursive Beziehungen wie folgt:
Erstellen Sie die optimale Lösung:
Wenn die Trennungsposition k des entsprechenden M [i] [j] als S [i] [j] bezeichnet wird, kann nach Berechnung des optimalen Wertes m [i] [j] die entsprechende optimale Lösung rekursiv aus S [i] [j] rekursiv konstruiert werden. Die Zahl in s [i] [j] zeigt, dass der beste Weg, die Matrixkette A [i: j] zu berechnen, zwischen der Matrix AK und AK+1 getrennt werden sollte, dh die optimalen Klammern sollten sein (a [i: k]) (a [k+1: j). Aus den von S [1] [n] aufgezeichneten Informationen können wir daher sehen, dass die optimalen Klammern zur Berechnung eines [1: n] (a [1: s [1] [n]]) (A [s [1] [n] +1: n]) lautet. Ferner rekursiv ist die optimalen Klammern für a [1: s [1] [s [1] [s [1] [n]]) (a [s [1] [s [1] [n]]+1: s [1] [s [1] [S [1] [S [1] [N]]). In ähnlicher Weise kann festgestellt werden, dass die optimalen Klammern von A [s [1] [n] +1: n] bei s [s [1] [n] +1] [n] ... wenn wir dies weiterhin wiederholen und dies weiterhin wiederholen können, können wir schließlich die optimalen vollständigen Klammern eines [1: n] bestimmen und eine optimale Lösung für das Problem konstruieren.
Paketmatrix; öffentliche Klasse matrix {public static void matrixchain (int [] p, int n, int [] [] m, int [] [] s) {für (int i = 1; i <= n; i ++) {m [i] [i] = 0; } für (int r = 2; r <= n; r ++) {für (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; für (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 ("Multiplizieren Sie" + i + "," + s [i] [j] + "und A" + (s [i] [j] + 1) + "," + J); } public static void main (String [] args) {System.out.println ("Wulin.com Testergebnisse:"); 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); für (int i = 1; i <n; i ++) {für (int j = 1; j <n; j ++) {System.out.print (m [i] [j]+"/t"); } System.out.println (); } System.out.println (); für (int i = 1; i <n; i ++) {für (int j = 1; j <n; j ++) {System.out.print (s [i] [j]+""); } System.out.println (); } mc.traceback (1, 6, s); }}Auslaufergebnisse:
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.