Optimiertes Matrixprodukt

[charons_revenge]

Hallo liebe Comunity,

mein erster Post zu einem Problem dass zu lösen habe.
Ich hoffe dass mir jemand helfen kann, da ich weder in einiger Literatur (Güting, Datenstrukt. & Algorithmen, einigen Javabuechern) noch bei Google etwas finden konnte und ich langsam verzweifle..

Gesucht ist eine Implementierung einer Methode
public static int cmm(int[][] matDim), welche die optimale (also kleinstmögliche) Anzahl von Elementmultiplikationen berechnet, die von Nöten sind um mehrere Matrizen zu multiplizieren.
Als Beispiel werden die Matrizen A0(30x1), A1(1x40), A2(40x10) und A3(10x25)., die Elemente sind m*p und p*n bei der Multiplikation.


Mein Ansatz ist folgender:
Es gilt zwar nicht das kommutativgesetz, aber die Matrizen sind immer assoziativ.
Die Matrizen haben, je nach Klammerung, unterschiedlich viele Multiplikationen vor sich..

im Beispiel habe ich durch Trial and Error errechnet, dass A0((A1A2)A3) mit 1400 Multiplikationen offenbar den best case darstellt. Der Worst Case ist(A0A1)(A2A3) mit 41200 Multiplikationen.
Auffällig ist, dass die optimale Lösung immer optimale Teillösungen hat, d.h. ich suche die kürzesten Teilfolgen bzw. Matrixmultiplikationen und weite dann aus. Somit habe ich also einen (?) rekursiven Ansatz, erst alle kurzen (d.hg. 2 Matrixen) optimalen Kombinationen zu finden und dann darauf aufbauend weiterzugehen.


Frage :
Wie implementiere ich das ? Eine einfache Matrix kann ich proggen ud sie beispielsweile mit Zufallszahlen füllen, aber das hilft mir hier nicht weiter. Vielleicht sollte man auch einige Exceptions schmeissen wenn die Spaltenanzahl der ersten und die Zeilenanzahl der folgenden Matrix ungleich sind. Ich bin bei meiner Suche u.a. auf matDim gestoßen, konnte aber in der Collections von java nix dazu finden und auch nicht im "Handbuch der Java-Programmierung" von G. Krüger.

Wie genau kriege ich diese Idee, Stück für Stück nach dem Optimum zu suchen in Java hin? Muss ich quasi alles trail error mässig durchmultiplizieren, die ergebnisse in nem array abspeichern und dann vergleichen?
--> vermutlich ist das totaler quatsch, daraus seht ihr dass ich einfach kein gr. Programmierer bin.
Oder reicht es, wenn ich erstmal nur alle m*n ausprobiere, sie in ein Array speichere und dann nach dem kleinsten Element suche? Ne, das ist quatsch..es reicht vermutlich das kleinste Produkt an n*m, abspeichern, dann nächstes n*m ausrechnen, vergleichen und falls kleiner das alte Ergebnis ersetzen?.Dies dann rekrusiv implementieren ?
hm...

Ich hoffe dass mir jemand ne Idee geben kann (muss kein vollst. code sein, ich will ja selbst auch noch etwas tun =D..andererseits würd ich mich auch nicht wehren xD)
Im ernst, nach meiner anfänglichen Euphorie macht dieses Problem keinen Spass mehr und Eclipse widert mich an. Das darf natürlich nicht sein
Freue mich über jeden Denkanstoß,
danke und Gruß CR

 

[SlaterB]

die Matrizen stehen in einer Reihe, es gibt n Stück,
du erstellst dir eine Liste/ Array mit den Informationen (30x1, .. ), können Matrixenobjekte sein oder was anderes, wird sich aber verändern

die Liste musst du n-mal durchlaufen (keine Rekursion),
multiplizierts jeweils zwei benachbarte Zahlen, hast am Ende ein Minimum,
-> diese Info merkst du dir irgendwo,
für den nächsten Schritt musst du aber die Suchliste nun verändern,
an der Stelle, wo du zwei Matrixen zusammengefasst hast musst du auch ein Element streichen und das neue Element hinschreiben
(10x40 und 40x10 -> 10x10 oder 40x40, grad keine Ahnung )
du musst die Matrix nicht unbedingt ausrechnen, es geht hier bei der Suche allein um nxp, nebenher zu rechnen stört aber auch nicht

so, nun hast du die gleiche Ausgangssituation wie zuvor (nun Länge n-1), wieder die Liste durchlaufen und kleinstes Produkt finden,
die Ergebnisse jedes Suchlaufs wie gesagt irgendwo parallel verwerten,

theoretisch wäre es denkbar, diese Suche rekursiv durchzuführen, etwa bis die Suchliste nur noch eine oder zwei Matrixen enthält,
da aber die Anzahl der Schritte vorher bekannt ist (n), reicht auch eine normale Schleife

 

[charons_revenge]

Ah ok....d.h. ich multipliziere def. immer nur max. 2 Matrizen pro Durchlauf ?
D.h. dann aber dass ich ne Laufzeit von n² habe oder nicht ?
Schon mal danke fuer die schnelle Atwort ich versuche mich gleich nochmal daran..ich poste mal nachher zu welchem code ich gekommen bin.
DAnke und bis nachher
CR

 

[SlaterB]

naja, da eine Matrixenmultiplikation viel aufwendiger als die einfache Größenbestimmung ist,
ist dieses kleine n^2 nicht wirklich störend

außerdem du könntest noch optimieren falls du Lust hast:
die Produkte aus je zwei Matrixen ändern sich in einem Durchlauf ja kaum, die kannst du cachen
und nur da, wo zwei Matrixen zusammengefasst werden, ändert sich was für die beiden weiteren Nachbarn, wenn überhaupt

wenn du das ganze weiter umbaust, ginge eine Liste von Verbindungen a la
- 1 zu 2, Aufwand x,
- 2 zu 3, Aufwand y

die Liste musst du einmal berechnen, sortieren, die beste Verbindung steht ganz vorne,
diese verarbeiten, je nach Wahl zwei Verbindungen (zu den beiden weiteren Nachbarn, siehe oben) aktualisieren und neu sortieren,
und so immer mit einer sortierten Liste von oben aus arbeiten

das dürfte das ganze auf n log n kürzen

 

[charons_revenge]

hm,...ich habe porbleme mit dem implementieren, weiss schon nicht wie ich die matrizen übergeben soll..aber ich versuch mich erstnochmal daran bevor ich euch damit belästige

nochmal zur theorie..wie erreiche ich denn nlog n wenn ich n mal das array durchlaufe und zwischendurch noch sortiere ?
ich sortiere doch min. in nlog oder nicht ? also n*nlogn ?!?!
War nur eine Interessensfrage, also nicht wichtig =D

Wär schön wenn meine Codefragmnente (die unter aller sau sind, ich bin echt schlecht =D hier mal durchgeschaut werden könnten nachher..
danke aber & grüße rc

PS: ist ja saucool dass das so schnell geht und sich echt leute finden die die zeit opfern einem zu helfen...war etwas skeptisch rangegangen und bin nun euphorisch, dass ich das ding doch geschaukelt kriege

 

[SlaterB]

hmm, bei n*nlogn ist was dran, aber eben noch kleinerer Ausgangswert,
da nur noch Werte vergleichen werden müssen statt Produkte auszurechnen (oder gar ganze Matrixen)

Sortieren bringts dann also nicht (ich rate ja auch nur),
die Reihenfolge so lassen wie sie ist und mit n*n durchlaufen,

nur das Cachen der Produkte wäre noch denkbar,
bei so kleinen Aufwand für das Produkt aber auch etwas fragwürdig


-----------


edit: ich hatte jetzt hier einen langen Text, den ich aber nicht mehr für richtig halte,

kann es sein, dass es der optimale Weg ist, bei einer Teilmatrix mit einer möglichst kleinen Seite anzufangen?
in diesem Fall bei der 1 und von dort aus nach links und rechts zu mulitplizieren, so dass diese kleine Seite erhalten bleibt,
nach links gehts mit 30x1 nicht weiter, aber nach rechts lassen sich 1x40 und 40x10 zu 1x10 zusammenfassen und danach immer weiter

bei mehrerer Minima, z.B.
1x10, 10x30, 30x7, 7x1
scheinst auch egal zu sein, ob man links oder rechts beginnt

prüfe mal diese Überlegung, dann bist du bei Suchaufwand n, einmal Minimum finden und ab gehts

 

[Marco13]

Hm. Das ist ein Optimierungsproblem. Und der beschriebene Algorithmus ist ein "Greedy-Algorithmus". Und man kann (insbesondere, wenn sowas als Aufgabe an Schule oder Uni gestellt wird) in den allermeisten Fällen davon ausgehen, dass ein Greedy-Algorithmus zwar bei einfachsten Beispielen die optimale Lösung liefert (wie auch hier), aber man damit bei komplexeren Beispielen auf die Fresse fliegt (wie auch hier :wink: )

Zumindest vermute ich das - unter dem Vorbehalt, dass ich vielleicht irgendwo einen Fehler gemacht haben könnte :?

Wenn man noch zwei Matrizen
Matrix A4 = new Matrix("A4", 25, 1);
Matrix A5 = new Matrix("A5", 1, 20);
hinten dranhängt, liefert der beschriebene Greedy-Algorithmus die Lösung
Best ((A0(A1A2))((A3A4)A5))(30x20) with 7150 mul

Es gibt aber immerhin noch 13 bessere Lösungen:
(A0(((A1A2)(A3A4))A5))(30x20) with 1280 mul
((A0((A1A2)(A3A4)))A5)(30x20) with 1290 mul
(A0((((A1A2)A3)A4)A5))(30x20) with 1295 mul
((A0(((A1A2)A3)A4))A5)(30x20) with 1305 mul
(A0((A1(A2(A3A4)))A5))(30x20) with 1310 mul
((A0(A1(A2(A3A4))))A5)(30x20) with 1320 mul
(A0((A1A2)((A3A4)A5)))(30x20) with 1650 mul
(((A0(A1A2))(A3A4))A5)(30x20) with 1850 mul
(A0(((A1A2)A3)(A4A5)))(30x20) with 2250 mul
(((A0((A1A2)A3))A4)A5)(30x20) with 2750 mul
(A0(A1((A2(A3A4))A5)))(30x20) with 2850 mul
(((A0A1)(A2(A3A4)))A5)(30x20) with 3650 mul
(A0((A1A2)(A3(A4A5))))(30x20) with 6700 mul

Hab' das jetzt nur schnell hingeschrieben, ggf. kann da ja noch jemand verifizieren.

Die Lösungen habe ich durch stupides probieren aller Kombinationen gefunden, was natürlich keine gute Lösung ist. Man müßte da z.B. mit dynamischer Programmierung rangehen .... das ganze z.B. als "Kürzesete-Wege-Problem" auffassen und vielleicht einfach den Dijkstra drüberlaufen lassen oder so (je nachdem wie man das modelliert....)

 

[SlaterB]

> liefert der beschriebene Greedy-Algorithmus die Lösung

hmm, meinst du damit meinen?
die angebliche Best-Lösung und die tatsächlich beste Lösung haben gemein,
dass erstmal A1A2 und A3A4 zusammengefasst werden,
es bleibt vor der nächsten Entscheidung

A0 - A1A2 - A3A4 - A5
30x1 - 1x10 - 10x1 - 1x20

da glaube ich nicht, dass als nächstes A3A4 und A5 zusammengefasst werden, nach welcher Regel?

 

[SlaterB]

allerdings ist der Blick nur auf die einzelnen Produktkosten tatsächlich zu kurz gedacht,
in einem Beispiel mit
B0 - B1 - B2 - B3
1x100 - 100x2 - 2x4 - 4x3
würde B2 und B3 zu 2x3 zusammengefasst werden, was nicht optimal ist

deshalb wie in meinem vorletzten Post besser auf die 1 als kleine Seite achten,
in den Algorithmus setze ich noch Hoffnungen

 

[Marco13]

allerdings ist der Blick nur auf die einzelnen Produktkosten tatsächlich zu kurz gedacht

Hmja, ich habe jetzt als Kosten die "tatsächlichen" Kosten für das Produkt verwendet. Also sinngemäß
kosten(A*B) = kosten(A) + kosten(B) + kostenFürMultiplikation(A,B)

Wie sich die Ergebnisse oder Abläufe der Algorithmen verändern, wenn man NUR die Kosten für die jeweilige Multiplikation in Betracht zieht (unabhängig davon, wie "teuer" die beiden Faktoren für diese Multiplikation bisher waren) müßte man sich vielleicht mal überlegen. Da am Ende aber tatsächlich die Kosten der Faktoren dazugerechnet werden müssen, macht es IMHO keinen Sinn, bei der Suche nach der besten Multiplikation NUR die Kosten für die aktuell anstehende Multiplikation zu berücksichtigen (und damit zu ignorieren, dass die Faktoren ja schon teuer gewesen sein können).

Oder meintest du was anderes? ???:L

Auch nochmal sinnbildlich: Man hat
A * B * C * D
Und findet als jeweils "billigste" Produkte vielleicht
B*C mit 100 Multiplikationen
A*BC mit 500
ABC*D mit 300
Insgesamt hätte man also 900 Multiplikationen. Ich kann mir kaum vorstellen, dass damit sichergestellt ist, dass man NICHT z.B. auch eine Folge hätte bilden können, bei der man
AB mit 200 (schlechter als oben)
AB * C mit 200
ABC*D mit 400
rechnet und mit nur 800 Multiplikationen auskommt
(die Zahlen sind natürlich frei erfunden, aber FALLS das weiter oben gepostete Beispiel stimmt, wäre das ja so ein Fall, wo man mit Greedy eben nicht die optimale Lösung findet). Man könnte die Kosten sicher allgemein aufschreiben, und da dann vielleicht irgendwas allgemeines beweisen (irgendwie wuselt in meinem Kopf gerade das Wort "Dreiecksungleichung" rum ???:L ) aber ... das kann meinetwegen ein gelangweilter Mathematiker machen :wink:

 

[charons_revenge]

:toll: mir wächst dieses forum ans herz
Es erscheint mir als bewiesen, dass man tatsächlich nur dann zur optimalen Lösung kommt wenn alle Teillösungen der länge 2 (also AxAy) , daraufhin alle Teillösungen der Länge 3 etc bereits optimal sind.

Die Frage ist, garantiere ich dies bereits durch Suche der kleinsten Spalten / Zeilenzahl, d.h. suche ich nach Minima der Dimensionen, beispielsweise 1? Wenn ja, was mache ich bei mehreren Alternativen? Oder multipliziere ich stumpf alle Kombinationen aus ? ODER ist es eine raffinierte Mischung?

Hm...ich ess erstmal und hau mich dann nochmal rein
grüße cr

 

[SlaterB]

macht es IMHO keinen Sinn, bei der Suche nach der besten Multiplikation NUR die Kosten für die aktuell anstehende Multiplikation zu berücksichtigen (und damit zu ignorieren, dass die Faktoren ja schon teuer gewesen sein können).

so war aber der Vorschlag in meinem ersten Post und dachte den meinst du mit
> Und der beschriebene Algorithmus ist ein "Greedy-Algorithmus".
in deinem ersten Post,

wie auch immer, dass man nicht nur lokal auf die Kosten schauen darf dürfte nun in jedem Fall klar sein

-----

mein zweiter Vorschlag ist immer noch, von der kleinsten Seite aus stur nach links und rechts zu wandern

> Wenn ja, was mache ich bei mehreren Alternativen?

wie gesagt egal (Vermutung)

 

[Marco13]

Es erscheint mir als bewiesen...
So schnell würde ich das nicht sagen - aber ich gehe (nach meinen ersten Tests) so lange davon aus, bis mir jemand das Gegenteil beweist. Vielleicht habe ich ja auch irgendeinen Punkt von SlaterB's Algorithmus (wie z.B. sein Kriterium mit dem "Suchen nach der kleinsten Seite") noch nicht richtig verstanden.

Alle Kombinationen dumpf durchprobieren wäre aber ziemlich ineffizeint (wenn es um VIELE Matrizen geht). Wenn man das ganze geschickt formalisiert, kann man es (wie oben schon gesagt) vermutlich als ein Kürzeste-Wege-Problem auffassen, für das es dann effiziente Lösungen gibt. Ob der Aufwand gerechtfertigt ist, hängt aber auch davon ab, wofür du das brauchst (und welche Note du bekommen willst :wink: )

 

[SlaterB]

Vielleicht habe ich ja auch irgendeinen Punkt von SlaterB's Algorithmus (wie z.B. sein Kriterium mit dem "Suchen nach der kleinsten Seite") noch nicht richtig verstanden.

das hatte ich ja erst kurz vor deinem ersten Post gepostet, kann in dein Programm noch nicht eingeflossen sein (falls du das nicht selber kanntest),
hat mit meinem ersten Vorschlag nicht viel zu tun

 

[Marco13]

Mit Greedy-Algorithmus meinte ich sowas wie http://de.wikipedia.org/wiki/Greedy-Algorithmus : Man mach immer den Schritt, der die wenigsten Kosten verursacht. Die Fälle, wo man am Anfang einen teuren Schritt machen muss, und danach dann nurnoch billige Schritte (und bei denen die Gesamtlösung dann insgesamt billiger ist, als wenn man IMMER den (gerade) billigsten Schritt macht) werden damit nicht berücksichtigt.

 

[Marco13]

synchronized (discussion) { :wink:
Das "kurze-Kanten-Kriterum" könnte "helfen" aber ich habe es nicht so gut verstanden und nachvollzogen, dass ich mit Sicherheit sagen könnte, ob damit immer die beste Lösung gefunden wird...
}