Permutationsproblem als Matrix abbilden

19/05/2014 - 12:49 von Ralf Jonas | Report spam
Guten Tag,

ich bin Programmierer und stehe mit einem langjàhrigen Problem vor einer
Optimierungsaufgabe, bei welcher es darum geht, aus einer Menge von
Datensàtzen die richtigen heraus zu finden, was derzeit noch per
BruteForce gemacht wird. Da die Anzahl der Sàtze in Zukunft aber eher
noch steigt (schneller als die Rechenleistung unserer Großrechner),
dachte ich da an ein eher eleganteres Verfahren, wo mir aber noch so der
letzte Kniff fehlt.

Der Kunde, ein Verlagshaus, möchte Werbungen schalten, und zwar in jedem
seiner Magazine. In jeder Ausgabe eines jeden Magazin, soll die Werbung
genau einmal erscheinen. Die Anzahl der Magazine und die Anzahl der
Ausgaben ist gegeben, ich nenne das Produkt mal W, die Anzahl der Werbungen.

Jede Werbung kann ich unterschiedlichen Formaten erscheinen, also
halbseitig, ganzseitig, viertel links oben, dreifarbig, vierfarbig, usw.
Je nach Motiv sind aber nur bestimmte Kombinationen möglich, sodass für
jede einzelne Werbung W eine unterschiedliche Anzahl von Kombinationen
möglich ist. Eine Kombination ist definiert durch ihre Merkmale, d. h.
eine Kombination hat mindestens ein Merkmal, maximal aber derzeit neun.
Es sind auch nicht alle Kombinationen möglich (bedingt durch das
Layout), andere können maschinell nicht hergestellt werden, wieder
andere làsst der Kunde nicht zu.

Es gibt also Werbungen W, von denen jede in einer anderen Kombination
auftreten kann, aber nicht muss.

Nun wird es aber kompliziert: Der Kunde gibt als Vorgabe die Anzahl der
Merkmale vor, die in Summe erreicht werden sollen. Er möchte also
47 x Merkmal 1
68 x Merkmal 2
15 x Merkmal 3
5 x Merkmal 4
usw.

Das ganze tüftelt er sich mit der Budgetabteilung aus, um eine
definierte, maximale Werbewirksamkeit zu erreichen und gleichzeitig
möglichst wenig zu investieren.

Unser bisheriges Vorgehen ist tatsàchlich, dass wir von allen W, alle
Kombinationen Wk in zwei ineinander stehenden Schleifen durch iterieren
und das Ganze aufsummieren, bis wir die passende Auswahl gefunden haben.

Mein Ansatz ist nun ein gànzlich anderer:

Ich stelle mir eine Matrix vor, die so viele Spalten hat, wie es
Merkmale gibt. Mein Ergebnisvektor ist daher die Vorgabe des Kunden.
Zeilenweise schreibe ich nun die Wk in die Matrix hinein, bin mir dessen
aber bewusst, dass ich da nun alle möglichen Wk drin habe, wohl wissend,
dass von jedem W immer nur ein Wk in der Lösung enthalten sein kann. Für
ein anderes Projekt habe ich schon einmal eine riesige Matrix im
Speicher gelöst (Gauss'sches Eliminationsverfahren) und damit die
Rechenzeit von etlichen Stunden auf knapp 2 Sekunden reduziert. Und nun
kam mir so der Gedanke, dass das auch hierbei irgendwie möglich sein müsste.

Ich bin leider nicht so der Mathe-Guru, aber vielleicht kann mir ja hier
einer der Cracks mit einem Ansatz behilflich sein?

Ralf
 

Lesen sie die antworten

#1 karl
19/05/2014 - 14:41 | Warnen spam
Ich bin leider nicht so der Mathe-Guru, aber vielleicht kann mir ja hier
einer der Cracks mit einem Ansatz behilflich sein?

Ralf



Aber natürlich umsonschd, gell?

Ähnliche fragen