Ich arbeite aktuell an einem kleinen Projekt und bräuchte Hilfe.
Stellt euch folgenden Datensatz vor
Die Zahlenwerte sind immer aufsteigend sortiert. Außerdem gibt es immer genau so viele Zahlenwerte wie Spalten.
Alle Spalten (A-E) müssen einem Wert zugeordnet werden. A kann also z.B. die Werte 20, 90, 100, 120 oder 130 haben. Allerdings ist nach einer Zuordnung diese Zeile gesperrt.
Beispiel: A bekommt den Wert 90
A kann nur einen Wert bekommen (hier im Beispiel die 90) und die Zeile wo die 90 steht ist für die anderen Spalten dann gesperrt (B dürfte also zB keine 22 mehr bekommen).
Jetzt soll das so optimiert werden, dass die zugeordneten Werte von A-E in ihrer Summe so gering wie möglich sind. In diesem Beispiel wäre die Lösung: A=20, B=22, C=40, D=80, E=78 (Summe=240).
Mein Problem: In diesem Beispiel gibt es 120 (Fakultät von 5) mögliche Kombinationen. Das ist mit einem Programm schnell berechnet und kein Problem. Hätten wir jetzt aber z.B. A-J mit jeweils 10 möglichen Werten gibt es schon ungefähr 3,6 Mio (Fakultät von 10) Möglichkeiten. Dann wirds also schwer das in akzeptabel Zeit zu berechnen.
Ich brüte jetzt schon einige Tage über dem Problem. Gibt es einen Algorithmus, um das effizient auszurechnen oder bleibt wirklich nur das „Durchprobieren“.
Das dürfte unter binäre lineare Programmierung fallen.
Sei zA1 die binäre Entscheidungsvariable, ob A1 ein gewählter Wert ist (entsprechend definierst du dir zA2, etc)
Dann ist deine Zielfunktion zA1 A1+zB1 B1+…+zE5 E5 (addiere den Wert einer Zelle, wenn die entsprechende z-Variable eins ist).
Deine Nebenbedingungen der Spalten sind dann
zA1+zA2+zA3+… = 1
zB1 +zB2 + … = 1
Deine Nebenbedingungen der Zeilen sind
zA1+zB1+zC1+… = 1
zA2+zB2+zC2 +… = 1
Dann hast du eine Zielfunktion und 2(Anzahl Spalten) Nebenbedingungen.
Bin mir nicht sicher, ob ich das Problem korrekt verstanden habe. Du wählst aus einer n*n Tabelle n Werte aus, so dass einer aus jeder Spalte und jeder Zeile kommt?
Das wäre ein Matching Problem. Du hast die Knoten A, B, C, … für die Spalten und die Knoten 1, 2, 3, … für die Zeilen. Daraus baust du einen vollständigen bipartiten Graphen. Die Kante (A,1) hätte dann Gewicht 20 und so weiter. Ein maximales/minimales Matching zu finden geht flott, in dem Fall ist das Problem aber noch einfacher. Schau mal hier rein
Also vielen Dank an @kelgrim durch deinen Tipp mit dem Zuordnugnsproblem habe ich die Lösung gefunden.
Mein Problem ist ein sogenannter (vollständiger) Bipartiter Graph. Also einen Graph der die Beziehung zweier Gruppen zueinander dastellt. Jedes Element aus Gruppe A ist mit jedem Element aus Gruppe B verbunden. Die Verbindungen sind dann gewichtet mit meinen Werten aus der Tabelle von oben. Da muss man dann das Minimum (Summer der Verbindungen) finden.
Darüber bin ich dann auf die ungarische Methode gestoßen die das ganze mit O(n³) Aufwand löst. Ist sicher nicht perfekt aber trotzdem viel schneller als meine Lösung (einfach alle Kombinationen ausrechnen und die mit der geringsten Summe bestimmen).
Vielleicht stolpert ja irgendwann mal wer über das Thema und sucht eine ähnliche Lösoung:
Gestern habe ich das mal eingebaut. Bei einem Array von 10x10 braucht mein „Durchprobieren“ ca. 50 Sekunden. Mit der ungarischen Methode ist es ca. 1 Sekunde. Geiler Scheiß!
