Umsetzung der Matrix Kettenmultiplikation in der Programmiersprache PHP. Beispiele Klammerungen, Feststellungen, Laufzeit und Programmcode.
Wenn man Matrizen miteinander multipliziert, kann man unterschiedliche Klammerungsmöglichkeiten verwenden. Die Martizenmultiplikation ist assoziativ, das heißt die Reihenfolge der Berechnung der Teilprobleme ist egal. Ich kann zuerst den „rechten“ Teil oder auch den „linken“ Teil berechnen. Dies macht keinen Unterschied, solange die Dimensionen zueinander passen.
Beispiel Klammerung
Ausgang: ((40×20 20×30) (30×10 10×30))
Schritt 1: (40×30 30×30)
Schritt 2: 40×30
Ausgang: (40×20 (20×30 (30×10 10×30)))
Schritt 1: (40×20 (20×30 30×30))
Schritt 2: (40×20 20×30)
Schritt 3: 40×30
Feststellung
Wie wir sehen macht die Klammerung logischerweise keinen Unterschied in der Lösung, jedoch einen erheblichen Unterschied in der Laufzeit.
Beispiel Laufzeit
Die Laufzeit beziehungsweise die Anzahl skalarer Multiplikationen von Matrizen berechnet sich wie folgt:
1. Matrix Zeilen * 2. Matrix Spalten + 1. Matrix Spalten / 2. Matrix ZeilenHierbei ist es egal, ob wir zuletzt die Spalten der 1. Matrix oder die Zeilen der 2. Matrix verwenden, da diese identisch sein müssen bei einer Multiplikation.
Ausgang: ((40×20 20×30) (30×10 10×30))
Schritt 1: 40 * 30 * 20 + 30 * 30 * 10
Schritt 2: 24.000 + 9.000
Es werden bei dieser Klammerung 33.000 skalare Multiplikationen benötigt.
Ausgang: (40×20 (20×30 (30×10 10×30)))
Schritt 1: (40×20 (20×30 30×30)) – 30 * 30 * 10 = 9.000
Schritt 2: (40×20 20×30) – 20 * 30 * 30 = 18.000
Schritt 3: 40×30 – 40 * 30 * 20 = 24.000
In Summe werden bei dieser Klammerung 51.000 skalare Multiplikationen benötigt.
Daraus folgt:
Die Wahl der Klammerung macht erhebliche unterschiede in der Laufzeit.
https://de.wikipedia.org/wiki/Matrix-Kettenmultiplikation
https://de.wikipedia.org/wiki/Dynamische_Programmierung
https://de.wikipedia.org/wiki/Rekursion
https://de.wikipedia.org/wiki/Optimierungsproblem
https://de.wikipedia.org/wiki/Landau-Symbole
https://de.wikipedia.org/wiki/Assoziativgesetz
Programmcode Matrix Kettenmultiplikation
Folgender Programmcode berechnet rekursiv die Anzahl skalarer Multiplikationen von Matrix Ketten, beziehungsweise die optimale Klammerung.
$p sind hierbei die Dimensionen der Matrizen. Wenn n die Anzahl an Matrizen ist, enthält dieses Array n+1 Werte, da die Zeilen der 1. Matrix mit den Spalten der 2. Matrix übereinstimmen und man sich diese sparen kann.
Beispiel:
$p = array(40, 20, 30, 10, 30); 5 Werte
40×20 20×30 30×10 10×30 4 Matrizen
Das Ergebnis beträgt hierbei eine minimale Anzahl von 26.000 skalaren Multiplikationen.
<?php
function Recursive_Matrix_Chain($m,$s,$p,$i,$j) {
global $m, $s;
echo "Funktionsaufruf i $i j $j\n";
if($i == $j) {
// Problem nicht loesbar, da lediglich ein Element
echo "Error - i und j gleich\n";
return 0;
}
$m[$i][$j] = PHP_INT_MAX;
for($k = $i; $k < $j; $k++) {
echo "k $k i $i j $j\n";
$q = Recursive_Matrix_Chain($m,$s,$p,$i,$k)
+ Recursive_Matrix_Chain($m,$s,$p,$k+1,$j)
+ $p[$i-1] * $p[$k] * $p[$j];
echo "q $q m[i][j] $m[$i][$j]\n";
if($m[$i][$j] > $q) {
$m[$i][$j] = $q;
$s[$i][$j] = $k;
}
}
return $m[$i][$j];
}
// $m 2 dimensionales Array zur Speicherung der minimalen Anzahl skalarer Multiplikationen
// $s 2 dimensionales Array zur Speicherung der Klammerungsstellen
// $p Array welches die Dimensionen der Matrizen enthaelt
// 40x20, 20x30, 30x10, 10x30
// n - 1 Matrizen
$p = array(40, 20, 30, 10, 30);
// 30x5 5x6 - 30 * 6 * 5 = 900
//$p = array(30, 5, 6);
//$p = array(10, 20, 30, 40, 30);
// 10x20 20x30 = 10 * 30 * 20 = 6000
// Formel: 1. Matrix Zeilen * 2. Matrix Spalten + 1. Matrix Spalten / 2. Matrix Zeilen
//$p = array(10, 20, 30);
// $i Beginn des Teilproblems
$i = 1;
// $j Ende des Teilproblems
$j = sizeof($p)-1;
$ergebnis = Recursive_Matrix_Chain($m,$s,$p,$i,$j);
echo "Ergebnis: ".$ergebnis."\n";
print_r($m);
print_r($s);
// https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
?>Ausgabe
Mathiass-MacBook-Pro:Desktop mathias$ php -f matrix2.php
Funktionsaufruf i 1 j 4
k 1 i 1 j 4
Funktionsaufruf i 1 j 1
Error - i und j gleich
Funktionsaufruf i 2 j 4
k 2 i 2 j 4
Funktionsaufruf i 2 j 2
Error - i und j gleich
Funktionsaufruf i 3 j 4
k 3 i 3 j 4
Funktionsaufruf i 3 j 3
Error - i und j gleich
Funktionsaufruf i 4 j 4
Error - i und j gleich
q 9000 m[i][j] Array[4]
q 27000 m[i][j] Array[4]
k 3 i 2 j 4
Funktionsaufruf i 2 j 3
k 2 i 2 j 3
Funktionsaufruf i 2 j 2
Error - i und j gleich
Funktionsaufruf i 3 j 3
Error - i und j gleich
q 6000 m[i][j] Array[3]
Funktionsaufruf i 4 j 4
Error - i und j gleich
q 12000 m[i][j] Array[4]
q 36000 m[i][j] Array[4]
k 2 i 1 j 4
Funktionsaufruf i 1 j 2
k 1 i 1 j 2
Funktionsaufruf i 1 j 1
Error - i und j gleich
Funktionsaufruf i 2 j 2
Error - i und j gleich
q 24000 m[i][j] Array[2]
Funktionsaufruf i 3 j 4
k 3 i 3 j 4
Funktionsaufruf i 3 j 3
Error - i und j gleich
Funktionsaufruf i 4 j 4
Error - i und j gleich
q 9000 m[i][j] Array[4]
q 69000 m[i][j] Array[4]
k 3 i 1 j 4
Funktionsaufruf i 1 j 3
k 1 i 1 j 3
Funktionsaufruf i 1 j 1
Error - i und j gleich
Funktionsaufruf i 2 j 3
k 2 i 2 j 3
Funktionsaufruf i 2 j 2
Error - i und j gleich
Funktionsaufruf i 3 j 3
Error - i und j gleich
q 6000 m[i][j] Array[3]
q 14000 m[i][j] Array[3]
k 2 i 1 j 3
Funktionsaufruf i 1 j 2
k 1 i 1 j 2
Funktionsaufruf i 1 j 1
Error - i und j gleich
Funktionsaufruf i 2 j 2
Error - i und j gleich
q 24000 m[i][j] Array[2]
Funktionsaufruf i 3 j 3
Error - i und j gleich
q 36000 m[i][j] Array[3]
Funktionsaufruf i 4 j 4
Error - i und j gleich
q 26000 m[i][j] Array[4]
Ergebnis: 26000
Array
(
[1] => Array
(
[4] => 26000
[2] => 24000
[3] => 14000
)
[2] => Array
(
[4] => 12000
[3] => 6000
)
[3] => Array
(
[4] => 9000
)
)
Array
(
[3] => Array
(
[4] => 3
)
[2] => Array
(
[4] => 3
[3] => 2
)
[1] => Array
(
[4] => 3
[2] => 1
[3] => 1
)
)