Matrix Ketten Multiplikation in PHP

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 Zeilen

Hierbei 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

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
        )

)

Kommentar verfassen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Scroll to Top