# Optimale Matrixmultiplikation



## Lala87 (15. Mai 2010)

Also, erstmal vorweg: Ich bin ein absoluter Programmier und Java - Neuling. Muss mich in meinem Grundstudium damit befassen - bezweifle aber, dass ich mich später im Beruf also Hauptaufgabe der Programmierung widmen werde bzw mich freiwillig damit befassen werde.

Zur Aufgabe:
Gegeben ist ein Pseudocode, der die optimale Auswertreihenfolge für ein Matrixprodukt M1*....*M_n berechnet. Diesen soll ich nun in Java realisieren. Und die optimale Auswertreihenfolge soll als Text ausgegeben werden.
Die Methode soll die Dimensionen der Matrizen als Parameter übergeben bekommen.
Beispiel: Matrizen: 10x20 , 20x50 , 50x1 , 1x100

public static String matrixoptimierung (int [] r)

mit int [] r = {10,20,50,1,100
system.out.println(matrixoptimierung (r1)); > Ausgabe: (M[1]* (M[2]*M[3]) )*M[4] , Aufwand: 2200 Operationen

so zum pseudocode:

for i:= 1 until n do m_i,i = 0;
for i:= 1 until n-1 do 
for i:= 1 until n-1 do 
      begin
           j:= i + l;
          m_i,j:= min_(i<=k<j) ({m_i,k + m_k+1,j + ri?1 · rk · rj}  // m_i,j sind die minimalen Koste/Anzahl an Operationen
          k_i,j := zum Minimum gehördens k, //klammerung
end;

Ich dachte mir, den pseudecode muss ich vom Prinzip her ja erstmal am tippen:
Mein Problem: Muss ich für die m und k zuerst ein Array anlegen? also quasi vorher sowas wie 
int a = r.length; //Anzahl der zu multiplizierenden Matrizen
 int [] m = new int [a]; //Anzahl der minimal nötigen Operationen
int [] km = new int [a]; //Klammerung

müssen diese dann nicht aber so aussehen int [][], aber dann weiß ich auch nicht wie groß ich die machen soll....

for (int i=1; i<= a; i++)
            mi,i = 0;
        for (int l=1; i< a; l++) //l = Länge der Klammerung
            for( int i=1; i<=a-l; i++){
                int j = i + l;
                m(i,j) = min( m(i,k) + m(k+1,j) + r(i-1)*r(k)*r(j));
                km(i,j) = argmin( m(i,k) + m(k+1,j) + r(i-1)*r(k)*r(j));


Danke schon mal für Hilfe und Erklärungen!
mfg


----------

