Einzelnen Beitrag anzeigen
  #5 (permalink)  
Alt 22-09-2003, 10:55
Titus
 PHP Master
Links : Onlinestatus : Titus ist offline
Registriert seit: Jan 2001
Ort: im Rodgau
Beiträge: 4.292
Titus ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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.
__________________
mein Sport: mein Frühstück: meine Arbeit:

Sämtliche Code-Schnipsel sind im Allgemeinen nicht getestet und werden ohne Gewähr auf Fehlerfreiheit und Korrektheit gepostet.
Mit Zitat antworten