Teilsumme aus "Rechtecken" < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:15 So 25.04.2010 | | Autor: | XeZZ |
Hallo,
ich versuche mich an einem effektiven Algorithmus um aus Mehrdimensionalen Arrays die maximale Summe zu bestimmen. Das soll in etwas so Aussehen:
1 2 3 4 5 6
7 8 9 -5 -4 10
-1 1 1 5 8 -15
Nun soll in diesem Rechteck ein Teilrechteck gefunden werden in dem die Summe der Elemente maximal ist. In diesem Fall wäre das:
1 2 3
7 8 9
-1 1 1
Es sind also vier Indizes gesucht nämlich z1 (Startzeile) z2 (Endzeile) s1 und s2 (Spalten)
So nun bin ich mir nicht sicher wie ich das als einen Algorithmus verwirklichen kann. Eine Möglichkeit wäre natürlich alle Möglichkeiten durchzuprobieren, was aber schon bei dem oben gegebenen Rechteck ziemlich lange dauern dürfte da es ja nun enorm viele Möglichkeiten gibt.
Einen Algorithmus der auf einem eindimensionalen Array operiert und dort die maximale Summe berechnet bekomme ich hin. Aber durch die zweite Dimension fehlt mir da der Ansatz.
|
|
| |
|
Hallo XeZZ,
Beim Brute-Force-Ansatz betrachtet man in deinem Fall ein Rechteck nach dem Anderen. Dabei kann sich das nächste Rechteck mit einem Vorherigen überlappen. Könnte man das nicht irgendwie ausnutzen, indem man zuerst bei den kleinsten Rechtecken anfängt und die so entstandenen Summen und die zugehörigen Rechteck-Koordinaten irgendwo irgendwie abspeichert. Bei größeren Rechtecken könnte man dann vielleicht auf Teilsummen der nächst(!)-kleineren Rechtecke zugreifen, die im aktuellen Rechteck enthalten sind, wodurch man bei einem größeren Rechteck nicht alles nochmal aufsummieren muß. Ich gebe zu, die Idee ist sehr vage. Aber wenn man die Rechtecke in irgendeiner Struktur mit Hashing-Funktionalität speichert, könnte es einen Geschwindigkeitszuwachs bei einem Brute-Force-Ansatz bringen.
Ansonsten erinnert mich deine Aufgabe ein wenig an das Subset-Sum-Problem.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:32 So 25.04.2010 | | Autor: | XeZZ |
Also erstmal: Es ist eine Spezialisierung dieses Subset-Sum-Problems (Danke für den namen in english unter Teilfolgenproblem findet man nichts so tolles ;))
Und zu der Idee ich hab keine Ahnung wie man Hashzeug oder so programmiert ich bin Zweitsemester und was wir da so lernen ist echt verdammt mager so was direkte Programmierung angeht...
Aber die Idee ist garnicht so übel. Man könnte mit dem Element 0,0 beginnen und das als max speichern (und die vier Indizes in dem fall 0,0,0,0). von da aus gibt es dann drei Möglichkeiten eine bessere Summe zu erhalten entweder ein nach rechts oder ein runter oder beides. (Also Zeile erhöhen oder Spalte erhöhen oder eben beides) und immer prüfen und gegebenenfalls Indizes und Max wert erhöhen.
Das Dauert aber immernoch verdammt lang, da man jedes Element einmal als Startelement verwenden müsste...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:21 Mi 28.04.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
