[JavaScript] Matrix-Problem

Hallo,

vor einigen Tagen habe ich angefangen etwas Javascript zu lernen. Nun habe ich ein Problem bei dem ich nicht weiter komme:

- Es muss die Zahlenkombination errechnen werden, die unter folgenden Bedingungen die grösste Summe ergibt:

- Ich habe eine Matrix mit 20 Zeilen und 8 Spalten.

- Von jeder Zeile muss eine Zahl genommen werden (dürfen aber nicht mehr sein).

- Es dürfen maximal 5 Zahlen aus der selben Spalte genommen werden

Ich hoffe jemand kann mir weiterhelfen.

ähm ... whatisthematrix.com ... klingt eher als seist du auf der Suche nach einem Algorithmus.

ein Wert aus jeder der m Zeilen - max. k Werte aus einer Spalte

PHP-Code:

m=8; n=20; k=5;
matrix = new Array(
    1,  2,  3,  4,  5,  6,  7,  8,
   11, 12, 13, 14, 15, 16, 17, 18,
  ...
  191,192,193,194,195,196,197,198,
  201,202,203,204,205,206,207,208
); 


das einfachste wär natürlich brute force (brutale Gewalt) = für alle Kombinationen mit n Werten aus verschiedenen Zeilen - erst Vailiditäts-Check (max. k Werte je Spalte?), dann Summe berechnen:

PHP-Code:

ergebnisse = new Array();
zaehler = new Array();
zaehler.length = m;
// kombi mit der ersten passenden Kombination initialisieren
// Ergebnis: kombi = (0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3)
kombi = new Array();
kombi.length = n;
for(zeile=0,wert=-1; zeile<n; zeile++)
{
  if (!(zeile % k)) wert++; // alle k Zeilen wert erhöhen
  kombi[zeile] = wert;
}
maxkombi = '-'; maxsumme=0;
do
{
  // maximal 5 Werte aus einer Spalte?
  // (= max. 5x den gleichen Buchstaben)
  // dabei gleich die Summe bilden
  summe = 0;
  for(spalte=0; spalte<m; spalte++)
    zaehler[spalte] = 0;
  for(ok = true, zeile=0; ok && zeile<n; zeile++)
  {
    spalte = kombi[zeile];
    if (++zaehler[spalte] > k)
      ok = false;
    else
      summe += matrix[zeile*m + spalte];
  }

  // ja: Summe mit bisherigem Maximum vergleichen
  if (ok && summe>maxsumme)
  {
    maxsumme = summe;
    maxkombi = kombi.join(',');
  }

  // Hochzählen
  for(zeile=n-1; zeile>=0; zeile--)
  {
    wert = kombi[zeile]+1;
    if (m==wert) wert = 0; // Überlauf bei m
    kombi[zeile] = wert;
    if (wert) break; // kein Überlauf: Abbruch
  }
} while(zeile>=0) // Abbruch bei Überlauf an erster Stelle
alert ('Kombination mit der höchsten Summe: '
  + maxkombi + '; Summe=' + maxsumme); 


Bei den Dimensionen deiner Matrix wären das etwa 20^8 = 25,6 Milliarden Durchläufe; und das ist wohl weniger akzeptabel. Selbst wenn dein Rechner zehn Millionen Durchläufe pro Sekunde schaffen sollte, braucht das Skript über 40 Minuten, um ein Ergebnis auszuspucken - und bis dahin hat dein Browser das Skript schon x-mal unterbrochen, um dich zu fragen ob es weiter ausgeführt werden soll.

Aber es gibt ein paar einfache Methoden, das etwas zu beschleunigen, und ein paar kompliziertere. Der flotteste Algorithmus, der mir auf die Schnelle einfällt ist dieser hier; eine Art quadriertes Backtracking:

Der erste Schritt für alle Beschleunigungsmaßnahmen bei diesem Problem: Man erstelle eine Index-Matrix, in der für jede Zeile die Indizes der Werte in absteigender Reihenfolge gespeichert werden.
ein Beispiel - 3x3-Matrix; es darf maximal ein Wert aus jeder Spalte kommen:
m=n=3; k=1;
matrix = new Array(
8, 15, 22,
3, 17, 9,
12, 3, 21
);
die Index-Matrix sieht so aus: (
2, 1, 0,
1, 2, 0,
2, 0, 1
);
Höchster Wert in der ersten Zeile ist die 22 an dritter Stelle = Position 2,
danach kommen 15 an Position 1 und die 8 ganz vorne (Position 0).
Die anderen Zeilen werden analog erstellt.

Dann fängt die Iteration an ... es werden jeweils für die ersten n Zeilen der Matrix die erste gefundene zulässige Index-Kombination samt der dazugehörigen Teilsumme gespeichert. Dadurch dass wir die Werte über die Index-Matrix absteigend sortiert haben, bekommen wir automatisch die beste.

bei obigem Beispiel ohne Vailidierung:
Zeile 0:
2 (22); weitere Kombinationen: 1 (15) - 0 (8)
Zeilen 0-1:
2, 1 (39);
weitere gültige Kombis:
2, 0 (22+3=25)
0, 1 (8+17=25)
1, 2 (15+9=24)
1, 0 (15+3=18)
0, 2 (8+9=17)

8, 15, 22,
3, 17, 9,
12, 3, 21

Nu kommt die Validierung dazu:[list=1][*]Die Kombination 2,1,2 (22+17+21 = 60) ist ungültig.[*]Also gehen wir zu vorigen Zeile zurück und suchen uns die nächst niedrigere gültige Kombination bis zu der Zeile: 2,0 (22+3=25)
Die Differenz zur höchsten Kombination 2,1(39) ist 14.[*]Bevor die jetzt verwurstet wird, schauen wir erst einmal nach, ob wir nicht einen Wert in der dritten Zeile finden, bei dem die Differenz geringer (oder gleich) ist; alles was >=21-14 ist passt also.
Die nächst niedrigere Zahl in der Zeile steht (wie uns die Index-Matrix sagt) an Position 0, es ist die 12. Das ist >=7[*]also schauen wir mal ob (2,1,1) gültig ist ... zwei Werte aus einer Spalte, also nicht.[*]nächste gültige zweizeilige Kombi + höchste aus Zeile 2: 2,0,2 (22+3+21 = 46) - passt aber auch nicht[*]nächste gültige zweizeilige Kombi ist die 0,1(8+17=25);
die Differenz zur vorigen Kombi ist 0. Also passt uns entweder die höchste aus der dritten Zeile oder alle gleichwerigen (die es nicht gibt)
0,1,2 passt aber schon; Wert: 8+17+21 = 46.[*]Wir haben eine Zahl aus der letzten Zeile hinzugefügt, damit ist die gültige Kombination mit der höchsten Summe gefunden.[/list=1]

Übrigens findet der brute-force-Algorithmus bei diesem Beispiel die gleiche Kombination, was aber nicht unbedingt sein muss.
Hier ist das etwa nicht der Fall:
matrix = new Array(
1,2,3,
1,2,3,
1,2,3
);
m=n=3; k=1;

brute force findet 0,1,2 mit Summe 6;
der andere Algorithmus wirft 2,1,0 mit der gleichen Summe aus.

---------------------------------------------------------------------------------

Zugegeben, der Algorithmus ist nicht ganz einfach zu implementieren; aber wenn du erst ein paar Monate JavaScript geübt hast und dann ein paar Tage Gehirnschmalz reinsteckst, kannst du hier ja mal das Ergebnis präsentieren.

Für den Anfang bau dir erstmal ein Skript, das die Index-Matrix erstellt.

Im bruteforce-Skript habe ich auch noch ein paar Möglichkeiten zur Beschleunigung gelassen; die wirst du allerdings erst mit viel Übung oder durch ausgiebiges Nachdenken über die Möglichkeiten der Sprache entdecken. (Die gleichen Möglichkeiten bieten sich aufgrund der Ähnlichkeit der Sprachen auch in C und Konsorten sowie PHP und natürlich Java.)

Auf jeden Fall empfehle ich Dir die ausgiebige Lektüre des JavaScript-Bereiches im selfHTML; da steht so ziemlich alles, was man über JavaScript wissen muss.
Ist auch prima als Nachschlagewerk geeignet; aber ich würd´s mir runterladen, die neue Werbeschaltung ist ein wenig lästig.

Ich hab mich bei Punkt 4. geirrt; natürlich muss hier die Kombi 2,1,0 überprüft werden (in 3 bin ich noch richtig mit der 0). Das ist eine gültige Kombination und liefert die Summe 51.

Das kommt davon wenn man sich so früh morgens an den Rechner setzt.

Danke für deine ausführliche Antwort. Ich werde gleich mal versuchen deine Ratschläge umzusetzen, obwohl dass noch etwas tieferes Programmierverständnis erfordern wird, als ich im Moment habe.

Ich glaube du hast dich in noch einem Punkt geirrt, denn meiner Meinung nach sind es 8^20 Möglichkeiten, was Jahre dauern würde.

Hast recht, 8^20 = 2^23 = 1 152 921 504 606 846 976
bei 10 Mio cycles/sec ca. 3656 Jahre

Aber kannst ja mal mit nem einfachen Backtracking anfangen. Das such zwar nach kürzesten Wegen; aber mit einer einfachen Umformung der Matrix ist das schnell erledigt:

M2[x,y] = 1+max(M1)-M1[x,y]

Und die Laufzeit bei deinen Dimensionen ist halbwegs akzeptabel,
aolange du nur eine Rekursion startest, wenn die neue Kombination gültig ist.

Sprich:
1. zur aktuellen Kombi suchst du die Spaltennummern, die noch nicht ausgereizt sind, bevor du diese an die Kombi anhängst und damit in die Rekursion gehst.
2. Noch mehr Zeit sparst du, wenn du die bisherige Summe als zweiten Parameter mitschickst.