beste Reihenfolge bei der Matrixmultiplikation (Komplexität)?
Hallo
Ich frage mich gerade ob es einen Algorithmus gibt der mir die beste Reihenfolge der Matrixmultiplikation berechnet um die geringste Laufzeit zu bekommen.
wenn ich drei Matrizen A1x3, B3x5 und C5x2 habe und ich ABC berechnen möchte ist es ja besser erst AB=E und dann EC zu berechnen statt BC=E und dann AE da ich bei der ersten Variante 1x3x5+1x5x2 = 25 Rechenschritte habe und bei der zweiten Variante 3x5x2+1x3x2 = 36
Weiß zufällig jemand ob es hier einen Algorithmus gibt der mir das auch für n MAtrizen berechnet und wo ich so einen finden kann?
wäre sehr hilfreich
Vielen Dank
PS: ich hatte schon die Überlegung die kleinste Dimension zu suchen und dann alle Multiplikationen mit dieser nach links und rechts und zum Schluss mittig mit dieser auszuführen, doch auch hier habe ich Fälle gefunden bei denen eine andere Reihenfolge besser ist..
2 Antworten
ich bin mittlerweile selbst auf eine Lösung gestoßen
in diesem Video wird das ganze ganz gut erklärt: https://lecture2go.uni-hamburg.de/l2go/-/get/v/14610
zusammengefasst muss man schauen, dass immer die letzte Multiplikation optimal ist setzt hier die Klammern und geht in die beiden Klammern um hier die optimale Lösung zu finden. Man geht also rekursiv vor bis alle Klammern gesetzt wurden
hier der Code den ich geschrieben habe (man muss vector und climits einbinden):
int bestMult(vector<int> v) { if(v.size() == 3) return v[0]*v[1]*v[2]; //bei nur 3 Vektoren gibt es nur eine Lösung vector<int> v1, v2; int kwert=INT_MAX, k; for(int i = 1; i<v.size()-1; i++) //ansonsten aus allen Werten bis auf den ersten und letzten den kleinsten Wert suchen { int h = v[0]*v[i]*v[v.size()-1]; //hier würde es reichen nur das kleinste v[i] zu suchen und nach der Schleife v[0]*v[i]*v[v.size()-1] zu berechnen if(h < kwert) { kwert = h; k = i;} } for(int i = 0; i <= k; i++) //der Vektor wird auf zwei Vektoren aufgeteilt, wobei k der letzte Wert des ersten und der erste Wert des zweiten Vectors wird { v1.push_back(v[i]); } for(int i = k; i < v.size(); i++) { v2.push_back(v[i]); } if(v1.size() == 2) return v1[0]*v1[1]*v2[v2.size()-1]+bestMult(v2); if(v2.size() == 2) return v1[0]*v2[0]*v2[1]+bestMult(v1); return bestMult(v1) + bestMult(v2) + kwert; }
falls jemand Lust hat kann er den Code gerne noch optimieren :)
Dieser Algorithmus lohnt sich nur bei sehr grossen und vielen Matrizen, dürfte also in den meisten Fällen überflüssig sein.
Ausserdem müsste der Algorithmus die Faktoren berücksichtigen. Kommen in einer Matrix viele Nullen oder Einsen vor, muss nicht multipliziert werden, im Falle von +-1 höchstens addiert.
Einfache Faktoren wie 2 usw. lassen sich auch durch einfache Addition bewerkstelligen.
Auf einem schnellen Rechner dauert die Analyse länger als die sture Abarbeitung.
meine Frage war ob jemand so einen Algorithmus kennt oder weiß wo ich einen finde, nicht ob ein solcher Algorithmus Sinn machen würde...