beste Reihenfolge bei der Matrixmultiplikation (Komplexität)?

2 Antworten

LonelyBronco
10.07.2017, 09:09

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 :)
surbahar53
09.07.2017, 19:23

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.
LonelyBronco 
Fragesteller
 10.07.2017, 09:12

meine Frage war ob jemand so einen Algorithmus kennt oder weiß wo ich einen finde, nicht ob ein solcher Algorithmus Sinn machen würde...

0