Laden...

Kombinatorik Problem

Erstellt von bbb vor 5 Jahren Letzter Beitrag vor 5 Jahren 2.183 Views
B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren
Kombinatorik Problem

Hallo zusammen,

ich weiß nicht recht wohin dieses Thema passt, daher habe ich es erstmal unter offtopic erstellt. Es geht hier um eine Art Kombinatorik Problem und ich weiß nicht so recht nach was ich googlen muss, um hier in die richtige Richtung zu kommen. Vielleicht habt ihr ein paar Hinweise, wie man so ein Problem angeht.

Ich habe ein Intervall in dem ich eine Gesamtzahl an Messwerten bekomme. Das kann (vereinfacht) so aussehen:

T1: 1000 T2: 1051

Ich habe zwischen den beiden Zeitpunkten also eine Differenz von 51

Nun bekomme ich im Intervall von T1 - T2 weitere Einzelmesswerte in absoluter Form. Ich weiß also nicht, ob sie positiv oder negativ sind:

Einzelmesswerte im Zeitraum T1 - T2:

10, 15, 20, 10, 11, 5

Ich weiß also das die Differenz von T1 zu T2 51 ist. Nun möchte ich die passenden Werte finden, die dieses Ergebnis bilden.

Alle Einzelwerte auf addiert passt nicht:

10 + 15 + 20 + 10 + 11 + 5 = 71

Wohingegen eine solche Kombination passen würde:

10 + 15 + 20 - 10 + 11 + 5 = 51

Das die Werte zwischen T1 und T2 negativ sein können, ist auch möglich. Zb so:

T1: 1000 T2 950

Einzelmesswerte im Zeitraum T1 - T2:

20, 30

Einzige mögliche Kombination

-20 -30

Ich denke, dass Problem ist klar. Wie ließe sich sowas lösen? Gibt es dafür mathematische Ansätze oder Algorithmen - außer stumpfen ausprobieren?

T
2.219 Beiträge seit 2008
vor 5 Jahren

Wenn ich dich richtig verstehe, willst du die ursprünglichen Werte der Differenz von T1 und T2 ermitteln.
Da es aber auch negative Werte geben kann, könntest du also passende Kombinationen bekommen aber nicht sicher sein ob diese den ursprünglichen Werten entsprechen.
Entsprechend würdest du nur versuchen die Differenzwerte mathematisch zu erraten.

Wäre es nicht sinnvoller zu schauen ob es eine andere Möglichkeit gibt, an die richtigen Werte zu kommen anstelle von errechneten Kombinationen, die auch falsch sein können, zu arbeiten?
Wenn du bestimmte Operationen wie Überwachung von Grenzwerten damit fahren willst, kannst du dich auf jede Menge Fehlalarme mit deinem Vorhaben einstellen.

Wenn du die original Werte nicht bekommst, solltest du vielleicht überdenken ob dein Vorhaben in dieser Form sinnvoll ist.

Es wäre auch für Helfende hilfreich, wenn du erklären würdest was du genau vorhast.
Deine aktuelle Erklärung liest sich nur wie ein Teil deines Problems, eben nur den Part wo du die Differenzen ermitteln willst.
Es fehlt aber der eigentliche Zwecke, den du damit erreichen willst.
Je nach dem was du vorhast, könnte es auch andere/bessere Lösungen geben!

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren

Hi T-Virus,

ja, es ist mir durchaus bewusst, dass es hier zu mehreren Kombinationen kommen kann, die passen würde. Diese Abweichung ließe sich in Kauf nehmen.

Bzgl. des Rahmens der Anwendung: Nein, ich habe keinerlei Möglichkeiten herauszufinden, ob die Einzelwerte positiv oder negativ sind.
Es handelt sich hier um Börsenwerte. Die Hauptwerte, die ich als T1 und T2 beschrieben sind Interest Rates, die ca. alle 5 Sek veröffentlicht werden. Zwischen diesen Zeitpunkten finden etliche Trades statt. Ganz einfach gesprochen sieht es so aus:

T1: 1000 T2 1050

Hier zwischen gab es genau einen Trade: 50. Die Gesamt Interest Rate ist angestiegen, also kann man draus schließen es war eine Open-Order. Wäre die Gesamt Interest Rate gefallen, also zu T2 kleiner als zu T1, dann wäre es eine Close-Order gewesen. Soviel zum Anwendungsrahmen.

W
955 Beiträge seit 2010
vor 5 Jahren

Eine Möglichkeit wäre eine heuristische Suche, z.B. A*-Algorithmus. Die einzelnen Werte sind die Knoten, die noch verbleibende Differenz zum Zielwert der Schätzwert.
BTW, warum willst du das nicht mit brute force lsen? Dauert es zu lange?

3.003 Beiträge seit 2006
vor 5 Jahren

Nun sind die möglichen Lösungen für das Problem nicht eindeutig. Wie willst du damit umgehen?


1 + 5 + 2 - 6 - 3 = -1 + 5 - 2 - 6 + 3

Will sagen: die Aussagekraft der möglichen Lösung ist sehr schwach. Zusammen mit der Anzahl der möglichen Lösungen wird sie etwas stärker (man weiß, wie sehr man ihr trauen kann), aber in deinem Szenario glaube ich nicht, dass ein "könnte so gewesen sein, aber auch so" irgendeinen Mehrwert für dich hat.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren

@witte
Brute force könnte auch ne Möglichkeit sein. Ich dachte es gibt schlauere und dadurch vielleicht auch effizientere Möglichkeiten. Die Idee mit dem A* finde ich gar nicht mal so schlecht.

@Latino
Diese Abweichung muss ich hinnehmen, selbst wenn die Lösung dadurch ggf. schwach ist.

Zusammen mit der Anzahl der möglichen Lösungen wird sie etwas stärker

Und müsste es nicht genau umgekehrt sein? Mit zunehmender Anzahl der möglichen Lösungen wird die Aussagekraft weniger?

3.003 Beiträge seit 2006
vor 5 Jahren

Nein, was ich sagte war, dass die Aussage stärker wird, wenn man weiß, wieviele Lösungen es gab.

Wird dir nur eine Lösung gesagt, kannst du sie genauso gut wegwerfen.
Wird dir eine Lösung gesagt UND, dass es 2 Lösungen gab, weißt du, dass es eine 50:50-Chance gibt, dass sie auch stimmt.

Zweiteres ist eine stärkere Aussage als erstes.

Der eigentliche Algorithmus ist sehr einfach. Sei S1 die Differenz des Wertes zwischen T2 und T1. Sei S2 die Summe der Elemente der Menge der absoluten Messwerte M zwischen T1 und T2.

S2 < S1 => unmöglich
S2 - S1 %2 ==1 => keine Lösung
Lösungen:
finde alle Kombinationen aus M, deren Summe (S1-S2)/2 ist. (Stack Overflow hilft). Sei K1..Kn jede Kombination, die das erfüllt, dann ist die Lösung:

Kx -> -Kx { p => -p } + M\Kx

LaTino
EDIT: ist auch bloss brute force. Man kann intelligenter suchen, aber es bleibt ausprobieren.

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren

Sehr cool. Vielen Dank fürs Klarstellen. Ich werde es mal auf diese Weise versuchen. Besten Dank!

3.003 Beiträge seit 2006
vor 5 Jahren

Wie gesagt, in dem Szenario wäre mir als Anwender die Angabe "auf die Natur der Trades können leider keine Rückschlüsse gezogen werden" lieber als etwas anzuzeigen, das im Zweifel falsch ist und den Anwender in die Irre führt. Ich würde da nur ein Ergebnis bringen, wenn es eindeutig ist. Aus einfachen Ergebnissen kann man nicht die Schritte deduzieren, die zu ihnen geführt haben. (Das ist etwas, das Wirtschaftswissenschaftler und Kreationisten nie kapieren 😉.

LaTino

"Furlow, is it always about money?"
"Is there anything else? I mean, how much sex can you have?"
"Don't know. I haven't maxed out yet."
(Furlow & Crichton, Farscape)

B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren

Da hast du schon recht, da es sich hier aber um hochfrequente Daten handelt, ist das Ganze auch eher als Approximation zu verstehen.

49.485 Beiträge seit 2005
vor 5 Jahren

Hallo bbb,

wenn ich dich richtig verstehe, dann muss es a) immer (mindestens) eine Lösung geben und außerdem verwendet b) jede korrekte Lösung immer alle Werte. Im Grunde willst du nur wissen, welche Werte negiert werden müssen und welche nicht. Richtig soweit?

Außerdem interessierst du dich nicht für verschiedene Lösungen, sondern eine reicht dir. Auch richtig?

Ich denke, dann kann man die Sache sehr vereinfachen bzw. beschleunigen.

Nehmen wir an, du hast n Werte. Du beginnst mit einer Liste, die nur einen Eintrag enthält, nämlich eine Null. Jetzt machst du in jedem Schritt das gleiche: Du nimmst den jeweils nächsten Wert wi und die aktuelle Liste. Jetzt erstellst du eine neue Liste, die alle Werte enthält, die entstehen, indem du auf jeden Wert der aktuellen Liste den Wert wi sowohl einmal addierst und einmal subtrahierst. Außerdem merkst du dir zu jedem Wert in der Liste, ob er im aktuellen Schritt durch Addition oder Subtraktion entstanden ist. Wenn dabei mehrmals das gleiche Ergebnis entsteht, dann wird es trotzdem nur einmal in der neuen Liste gespeichert, aber mit dem Hinweis, dass es durch Addition und Subtraktion entstehen kann. So steht in jeder neuen Liste, welche Summen/Differenzen sich aus den bisherigen Werten überhaupt bilden lassen.

In der letzten Liste interessiert dann nur der Eintrag mit der gewünschten Summe. Von dem aus kann man jetzt in den Listen rückwärts gehen, um die Kombination(en) zu ermitteln, die diesen Wert ergeben. Man weiß ja, bei jedem Schritt, ob Addition oder Subtraktion oder beides möglich ist. Wenn man sich nur für eine Lösung interessiert, dann wählt man nach belieben eine der beiden Rechenmöglichkeiten aus.

Es gibt dabei noch einige Optimierungsmöglichkeiten. Zum Beispiel kannst du die Werte (für die Verarbeitung) nach Größe absteigend sortieren. Außerdem summierst du am Anfang einmal alle (absoluten) Werte auf. Bei jedem Schritt ziehst du von dieser Summe den aktuellen (Absolut-)wert ab. Der entstandene Wert zeigt an, um wie viel die aktuelle Zwischensumme maximal noch steigen bzw. maximal noch sinken kann. Eintragen in die Liste, braucht man nur die Werte, mit denen sich der Zielwert überhaupt noch erreichen lässt, die also in dem genannten Intervall liegen. Durch das absteigenden Sortieren ist dieses Intervall jeweils so klein wie möglich. Gleichzeitig werden durch die anfänglich hohen Werte, schnell große Ausschläge erreicht, die dann gleich ignoriert werden können. Man scheidet also möglichst früh, möglichst viele nicht zielführende Kombinationen aus.

Aber auch ohne die Optimierung im letzten Absatz vermeidet man durch die Verwendung der Zwischensummen/-differenzen die kombinatorische Explosion. Wenn man nur eine Lösung will, sogar vollständig. Wenn man alle Lösungen will, vermeidet man sie in der Suchphase und hat sie nur in Bezug auf die (möglicherweise sehr vielen) gültigen(!) Lösungen.

herbivore

B
bbb Themenstarter:in
72 Beiträge seit 2009
vor 5 Jahren

Das ist mal ein verdammt simpler & smarter Lösungsansatz. Vielen Dank, herbivore!