| 

.NET C# Java Javascript Exception

6
Hallo Zusammen,
ich versuche gerade einen Algorithmus zu finden mit dem man schnell alle möglichen Kombinationen für eine Prozentuale Verteilung ermitteln kann. Zudem müssen Restriktionen berücksichtigt werden. Zur Veranschaulichung hier mal ein kurzes Codebeispiel:
public class Instrument
{
public string Name { get; set; }
public decimal Min { get; set; }
public decimal Max { get; set; }
public Group InstrumentGroup { get; set; }
}

public class Group
{
public string Name { get; set; }
public decimal Min { get; set; }
public decimal Max { get; set; }
}

static void Test()
{
Group loGroup1 = new Group() { Name = "Group1", Min = 10, Max = 70 };
Group loGroup2 = new Group() { Name = "Group2", Min = 20, Max = 80 };

List<Instrument> loInstrumentList = new List<Instrument>();
loInstrumentList.Add(new Instrument() { Name = "Inst1", InstrumentGroup = loGroup1, Min = 0m, Max = 1m });
loInstrumentList.Add(new Instrument() { Name = "Inst2", InstrumentGroup = loGroup1, Min = 20m, Max = 50m });
loInstrumentList.Add(new Instrument() { Name = "Inst3", InstrumentGroup = loGroup2, Min = 0m, Max = 1m });
loInstrumentList.Add(new Instrument() { Name = "Inst4", InstrumentGroup = null, Min = 0m, Max = 1m });
...

Ein Instrument hat eine Minimale bzw. Maximal zulässige Verteilung. Zudem kann ein Instrument einer Gruppe zugordnet sein die auch eine min./max. Verteilung hat. Man kann eine Schrittweite angeben und es müssen immer 100% verteilt werden. Bisher suche ich alle Kombinationen und werfe die Reihen weg die nicht nötig sind. Allerding dauert das ganze sehr lange wenn man z.B. 24 Instrumente mit einer Schrittweite von 1% einstellt. Da hier sehr viele Kombinationen gesucht werden die durch die Restriktionen gar nicht nötig sind. Hier die Ausgabe für das obige Codebeispiel bei einer Schrittweite von 2%:
0,0, 0,0, 0,0, 1,0 <- fällt raus wegen Inst2 Min
0,0, 0,0, 0,2, 0,8 <- fällt raus wegen Inst2 Min
...
0,2, 0,4, 0,0, 0,4 <- fällt raus wegen Group2 Min
0,2, 0,4, 0,2, 0,2 <- ok
0,2, 0,4, 0,4, 0,0 <- ok
0,2, 0,6, 0,0, 0,2 <- fällt raus wegen Group1 Max
...

Kann mir jemand auf die Sprünge helfen wie ich das Problem mit einem effizienten Algorithmus lösen kann?
News:
08.11.2011
PinBack 687 1 8
2 Antworten
2
Keine komplette Lösung, aber mal ein paar theoretische Überlegungen.

Die Definitionen Deiner n Instrumente liefern Dir 2n Ungleichungen der Form
-x_i <= min_i
x_i <= max_i
(mit i aus 1..n)

Die m Gruppen ergeben nochmal 2m Ungleichungen der Form
-x_g1 - x_g2 .. - x_gk <= min_g
x_g1 + x_g2 .. + x_gk <= max_g
(wobei g1..gk die Indizes der Instrumente der Gruppe g sind, g aus 1..m)

Damit ist ein n-dimensionales konvexes Polytop als Schnittmenge von 2(n+m) n-dimensionalen Halbräumen definiert. Durch die Zusatzbedingung
x1 + x2 +.. + xn = 1
wird dieses n-dimensionale Polytop mit einer (n-1)-dimensionalen Hyperebene geschnitten, das Ergebnis ist (wenn ich mich nicht irre) ein (n-1)-dimensionales konvexes Polytop.

Soweit zur Theorie. Die Stichworte, nach denen Du googlen solltest, sind also konvexe Polytope, lineare Optimierung, Lösen von linearen Ungleichungssystemen.

Ich empfehle Dir, dass Problem im n-1-dimensionalen Raum zu lösen, da die 100%-Verteilung den Wert für das letzte Instrument festlegt, wenn die anderen gegeben sind. Wenn Du x1 + x2 +.. + xn = 1 in die Ungleichungen für x_n einsetzt, bekommst Du
-x1 - x2 .. - x_n-1 <= max_n - 1
+x1 + x2 .. + x_n-1 <= 1 - min_n

Damit hast Du ein Ungleichungssystem in n-1 Variablen.

Einen konkreten Lösungsalgorithmus hab ich leider nicht parat, aber ich würde zwei Ansätze versuchen:

Entweder den umschließenden Würfel des Lösungspolytops bestimmen (also die Koordinaten aller Ecken, und dann in jeder Dimension das Minimum und Maximum) und diesen durchlaufen, oder einen inneren Punkt des Polytops ermitteln und von da ausgehend alle Nachbarpunkte ermitteln und auf Enthaltensein testen und für die positiven Treffer wieder die Nachbarpunkte und so fort.

Hoffe, das hilft Dir ein wenig. Wie Du siehst und wohl auch schon selbst gemerkt hast, ist das Problem nicht ganz trivial...

Update
Nach etwas drüber Schlafen kann ich Dir doch noch einen Algorithmus anbieten, oder sogar zwei. Der erste ist etwas gröber, aber einfacher, weil er für jedes Instrument vorab feste Intervalle bestimmt, die dann durchlaufen werden:

Bestimme für alle Instrumente, außer das n-te, folgende Werte:

  • das Minimum des Instruments selbst
  • für die Gruppe des Instruments das Gruppenminimum minus die Maxima aller anderen Gruppenmitglieder
  • 100 minus die Maxima aller anderen Instrumente

Davon das Maximum, aufgerundet auf die nächste Schrittweite - das ist die untere Grenze des Intervalls.
Analog

  • das Maximum des Instruments selbst
  • für die Gruppe des Instruments das Gruppenmaximum minus die Minima aller anderen Gruppenmitglieder
  • 100 minus die Minima aller anderen Instrumente

Davon das Minimum, abgerundet auf die nächste Schrittweite - das ist die obere Grenze.
Für das n-te Instrument nimmst Du immer 100 minus die anderen Werte.
Damit kommst Du in Deinem Beispiel auf
x1: [0,30]
x2: [20,50]
x3: [20,80]

Der zweite Algorithmus ist eine Variante davon. Die Intervallgrenzen werden hier erst während des Durchlaufens bestimmt, indem in der Vorschrift des ersten Algorithmus für alle Instrumente, deren Werte im jeweiligen Durchlauf schon bekannt sind, diese anstelle der Minima/Maxima eingesetzt werden.

Ganz ohne unnötige Durchläufe kommst Du damit auch noch nicht aus, aber es sollten doch sehr viel weniger sein. In Deinem Beispiel reduzierst Du mit dem ersten Algorithmus die Zahl der Durchläufe um den Faktor 1388, wenn ich mich nicht verrechnet habe.

Die Schwäche des zweiten Algorithmus ist, dass er nicht die Restriktionen berücksichtigt, die sich aus den Gruppenmitgliedschaften der "weiter innen" liegenden Instrumente ergeben. Er "sieht" z.B. bei der Bestimmung des Intervalls von x2 nicht, dass x3 durch seine Gruppe auf [20,80] beschränkt ist. Das kannst Du bei Bedarf noch dadurch angehen, dass Du zum einen die Daten vorher etwas aufbereitest, indem Du die Minima und Maxima einelementiger Gruppen auf das jeweilige Instrument überträgst, zum anderen kannst Du die Instrumente nach der Weite ihrer Gruppe sortieren und mit denen aus der "engsten" Gruppe anfangen. Dadurch steigerst Du die Wahrscheinlichkeit, dass tatsächlich aktive Gruppengrenzen bei der Bestimmung der Intervalle berücksichtigt werden.
08.11.2011
Matthias Hlawatsch 13,2k 4 9
Hossa.
Das muss ich mir jetzt mal alles genau ansehen.
Danke schon mal für die Mühe. Hab selbst noch einen Ansatz den ich jetzt mal teste.
PinBack 09.11.2011
1
Um Durchläufe bereits vorher auszusortieren, solltest du die Instrumente hinsichtlich des für sie gültigen Bereichs untersuchen und sortieren.

Wenn du dann die einzelnen Optionen durchgehst (das dürften ja geschachtelte Schleifen sein) durchläufst du die Instrumente in deren Reihenfolge von der kleinste Range zur größten.

So solltest du überhaupt keinen unnötigen Durchlauf haben.

Grüße
Huckepick
08.11.2011
huckepick 887 2 8
Das macht den Algorithmus sicher etwas effizienter (vorausgesetzt, für das letzte Instrument wird nicht mehr der Range durchlaufen, sondern nur noch der zu 1 fehlende Wert berechnet und geprüft, ob er in der Range liegt) - aber unnötige Durchläufe werden dadurch noch lange nicht vermieden. Zum einen werden die zusätzlichen Restriktionen durch die Gruppen nicht berücksichtigt. Aber selbst ohne Gruppen kann es leicht sein, dass die Aufgabe gar keine Lösung hat, wenn nämlich zum Beispiel bei n Instrumenten das größte Maximum kleiner als 1/n ist oder das kleinste Minimum größer als 1/n.
Matthias Hlawatsch 08.11.2011

Stelle deine .net-Frage jetzt!
TOP TECHNOLOGIES CONSULTING GmbH