Forum • Rocket Beans TV

Brauche Hilfe einen Algorithmus zu bestimmen

Ich arbeite aktuell an einem kleinen Projekt und bräuchte Hilfe.

Stellt euch folgenden Datensatz vor
grafik

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
grafik

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“.

Vielleicht fällt hier ja jemandem was ein.

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.

Leider ist die binäre lineare Programmierung NP-Vollständig. Möglich wäre aber zum Beispiele eine Solver-Bibilothek zu benutzen

1 Like

Sowas in der Art hat mir inzwischen auch ein Kumpel erklärt. Gibt scheinbar keinen perfekten Weg aber man kann das ganze optimieren bzw annähern.

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