Optimierungsproblem (Tabellen mit Baumstruktur)

[Zacherl]

Hallo zusammen,

ich habe eine Menge von Objekten, welche alle die Eigenschaft A besitzen. Zudem kann jedes Objekt optional noch die Eigenschaften B, C, D und E definieren. Alle diese Eigenschaften geben den Index in einer dazugehörigen Filter-Tabelle an.

Die Filter-Tabellen haben unterschiedliche Kapazitäten:

Code:

A = 256
B =    3
C =    5
D =    5
E =    4

Aus diesen Filter Tabellen baue ich mir nun einen Baum. Kleines Beispiel:

Code:

OBJ1 = {A =   4, B = /, C = 5, D = 3, E = /}
OBJ2 = {A =  54, B = 2  C = 3, D = /, E = /}
OBJ3 = {A =  54, B = 1, C = 1, D = /, E = /}

FilterA
   | - 001
   | - 002
   | - 003
   | - 0004 = FilterC
   |             | - 1
   |             | - 2
   |             | - 3
   |             | - 4
   |             | - 5 = FilterD
   |                        | - 1
   |                        | - 2
   |                        | - 4 = OBJ1
   |                        | - 3
   |                        | ...
   | - 005
   | ...
   | - 053
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            |          | ...
   |            |          | - 5
   |            | - 2 = FilterC
   |            |          | - 1
   |            |          | - 2
   |            |          | - 3 = OBJ2
   |            |          | - 4
   |            |          | - 5
   |            | - 3
   | - 055
   | ...

Und hier sieht man bereits das Problem. Bisher ist die Reihenfolge der Filter Tabellen statisch von A nach E festgelegt. Im Falle von OBJ2 und OBJ3 benötige ich deshalb 1x FilterB (Kapazität 3) und 2x FilterC (Kapazität 5), womit ich auf eine Gesamtkapazität von 13 komme. Hätte ich die Tabellen aber anders angeordnet; sprich zuerst C und dann B, würde ich für diesen Ast 1x FilterC (Kapazität 5) und 2x FilterB (Kapazität 3) benötigen, was eine Gesamtkapazität von 11 zur Folge hätte.

Wie würdet ihr an dieses Problem rangehen, um für jeden Einzel-Ast (und somit letztlich auch für den kompletten Baum) die jeweils optimale Konfiguration zu ermitteln?
Gibt es eventuell schon effiziente Alogrithmen, die ich für meine Zwecke umbauen könnte (generell wird es wohl auf Bruteforce/Backtracking hinauslaufen, nehme ich an)?

Viele Grüße
Zacherl

[Namenloser]

Bin mir nicht sicher, ob ich es ganz richtig verstanden habe, aber ich versuche es mal in eigenen Worten wiederzugeben:

Code:

FilterA
   | - 0004 = FilterC
   |            | - 5 = FilterD
   |                       | - 4 = OBJ1
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            | - 2 = FilterC
   |            |          | - 3 = OBJ2

Das Problem bei der gezeigten Anordnung ist, dass da einmal FilterC direkt unter /FilterA auftaucht und einmal unter /FilterA/FilterB, was unnötig kompliziert ist, weil man es auch so gliedern könnte:

Code:

FilterA
   | - 0004- FilterC
   |            | - 1 = FilterB
   |                       | - 1 = OBJ 3
   |                       | - 2 = OBJ 2
   |            | - 5 = FilterD
   |                       | - 4 = OBJ1

Verstehe ich das richtig?

Also um noch mal zum ersten Baum zurückzukommen, eigentlich steht da ja implizit:

Code:

FilterA
   | - nicht Filter B
   |            | - 0004 = FilterC
   |            |            | - 5 = FilterD
   |            |                       | - 4 = OBJ1
   | - 054 = FilterB
   |            | - 1 = FilterC
   |            |          | - 1 = OBJ3
   |            | - 2 = FilterC
   |            |          | - 3 = OBJ2

Du hast bloß das "nicht Filter B" gleich weggelassen. Aber wenn ich mir das so hingeschrieben mal ansehe und die Kapazitäten mal ignoriere, dann erinnert mich das stark an das Problem der Minimierung von Schaltungen. Dieses "(Filter B) oder (nicht Filter B)" wäre genau so ein Block, denn man z.B. im KV-Diagramm finden und wegoptimieren würde. Für die algorithmische Umsetzung eignen sich natürlich andere Verfahren wie Quine-McCluskey besser. Dein Problem ist leider wohl NP-vollständig.

[Zacherl]

Dein zweiter Baum ist nicht ganz korrekt, da OBJ1 ja einen anderen Wert für A hat, als OBJ2 und OBJ3. OBJ1 kannst du in der Betrachtung aber auch vorerst mal ausblenden, da das Problem in meinem Beispiel vorerst nur den Ast A = 54 betrifft.

Der dritte Baum ist prinzipiell korrekt (da ist nur die 004 etwas verrutscht ). Tatsächlich hat jeder Filter in meiner Implementation ein 0-Element, worin ich dann die Objekte einordne, für die der Filter nicht zutrifft. Das Problem ist allerdings nicht, die "unnötigen" Filter loszuwerden (das macht mein Algorithmus schon beim Einfügen neuer Objekte), sondern es geht konkret um die Reihenfolge der notwendigen Filter pro Ast.

Ziel soll sein, die Gesamtkapazität des Baumes zu minimieren.

Hierbei ist zu beachten, dass z.b. ein Filter C, bei dem nur ein Element gesetzt ist, trotzdem die volle Kapazität von 5 besitzt. In meinem Beispiel sieht man im 054er Ast ja ganz schön, dass beim naiven Einfügen (erst FilterA, dann FilterB wenn vorhanden, dann FilterC wenn vorhanden, ..) 1x FilterB und 2x FilterC benötigt werden. Man könnte die Objekte aber genauso gut einordnen, indem man erst 1x FilterC und danach 2x FilterB verwendet. Dadurch, dass FilterB aber eine kleinere Kapazität hat, als FilterC, spart man sich am Ende 2 unnötige leere Plätze.

[Namenloser]

Ok, sorry, dann verstehe ich nicht, was du vorhast. Vielleicht solltest du mal erklären, was du mit "Kapazität" überhaupt meinst und was die Zahlen im Baum bedeuten. Was macht ein Filter überhaupt und wie wird bestimmt wie oft man einen bestimmten Filter braucht? Was sind da die Rahmenbedingungen?

Mit den gegebenen Informationen würde ich sagen, die Gesamtkapazität des Baumes zu minimieren ist einfach: Einfach keinen Filter verwenden

[Zacherl]

Das mit den Kapazitäten hatte ich im ersten Post erwähnt, aber vielleicht nicht gut genug beschrieben. Denk mal kurz nicht an den Baum, sondern nimm die Filter als 1-dimensionale Tabellen (das sind sie in der Implementierung tatsächlich). Attribut A beispielsweise ist ein Byte. Der dazugehörige FilterA ist ein statisches Array mit 256 Elementen. Attribut B ist ein Enum mit 3 Werten. FilterB ist demnach ein statisches Array mit ebenfalls 3 Elementen, und so weiter ..

Als Kapazität bezeichne ich die maximale Anzahl an Elementen pro Filter. Also sozusagen Lenght(FilterArray) .

Die Zahlen im Baum repräsentieren den Index des Elements (weiterer Filter oder Objekt) im jeweiligen Filter Array.

Leider habe ich keinen Einfluss darauf, ob ein Objekt einen bestimmten Filter benötigt, da mein Datensatz vorgegeben ist. Zur Häufigkeit habe ich bisher auch keine Analyse gemacht, aber im Grunde genommen ist die Verteilung auch nicht wirklich relevant, wie ich das sehe.

[BUG]

Mir stellt sich ein bisschen die Frage, warum du (nicht dicht besetzte) Arrays als Filterstufe nehmen willst. Spricht etwas dagegen ein Tupel aus allen Eigenschaften zu hashen oder einen normalen Suchbaum zu verwenden?

Benutzt du für alle Teilbäume die gleiche Filterreihenfolge? Dann sucht du ja quasi eine Permutation der Filter, so das du für deine Objekte einen möglichst kleinen Baum bekommst. Mein Lieblingsansatzfür große Suchräume ist Branch-and-Bound: mit einer Heuristik findest du einen ersten Vorschlag und verfolgst nur Pfade weiter, die noch ein besseres Ergebnis liefern könnten.

Vom Bauchgefühl wäre es gut, für die ersten Stufen große Filter zu nehmen, die möglichst viele Objekte trennen. Dagegen sollten Filter vermieden werden, die Objekte mit gleichen Eigenschaften aber dort unterschiedlichen Werten trennen, insbesondere wenn deren Filter groß sind.