Vereinigungsmengenoptimierung |
| 05.01.2016, 11:28 | Logiker | Auf diesen Beitrag antworten » |
Vereinigungsmengenoptimierung
An einem Problem an dem ich gerade knabber merke ich, dass mein Denken nicht so strukturiert ist, wie es vielleicht sein könnte. Es hapert v.a. am konkreten mathematischen Ausdruck, so dass man beim Nachdenken später selbst noch versteht, was man mal genau gedacht hat. Verzeiht mir also, wenn das nicht die gewohnte Form hat, mein LK-Mathe ist schon 18 Jahre her. Regt mich gern an, wie ich es klarer schreiben kann, dann editiere ich es. Nun zu meinem Problem. Ich habe Mengen U1,..,Un, die Elemente x1,..,xn enthalten. Ein Element kann nur 1x je Menge U vorkommen. Für U gibt es eine Obergrenze a an Elementen. Diese Mengen U möchte ich nun in Vereinigungsmengen V zusammenführen, wobei es eine neue Obergrenze b an Elementen gibt. Es sollen am Ende so wenig Vereinigungsmengen wie möglich entstehen. Ich versuche es mal anhand eines Beispiels zu klarifizieren: U1: x1 U2: x1 U3: x2,x3 U4: x1,x4 U5: x5,x6,x7,x8,x9 U6:x2,x5,x6 U7:x10,x11,x12 U8:x13 Ich habe mir nun überlegt wie ich die Vereinigungsmengen am besten ermitteln kann und kam zu einer Tabelle ungefähr dieser Form: [attach]40342[/attach] Mein Ansatz wäre jetzt von einer Menge U wo die Summe xi maximal ist ausgehend die Menge U zu betrachten, die auch die Elemente xi enthalten. Hier würde ich also von U5 ausgehen und U6 treffen. Da U6 noch ein weiteres Element hat, welches nicht in U5 ist müsste ich prüfen wo das wieder enthalten ist und auch diese Menge in Betracht ziehen (U3), solange die Anzahl b nicht überschritten ist. Nun zu meinen Problemen. 1. Wie schon oben geschrieben würde ich das gern schöner, mathematischer ausdrücken. 2. Ausgehend von U5 könnte es ja eine weitere Menge Ui geben, die Elemente von U5 enthält - entsprechend würden hier schon komplexe Bäume entstehen - wie handhabt man das dann am besten? Letztlich will ich ja Summe Vi minimieren. Da müsste man sich ja eigentlich alle Optionen merken, also sowas wie U5, U5+U6, U5+U6+U3, weil es für das Gesamtproblem ja sinnvoll sein könnte U5 vielleicht doch nicht mit U6(+U3) zusammen zu legen. Wie würdet ihr das lösen? Es irgendwie gewichten? 3. Oder gibt es noch einen anderen, sinnvolleren und/oder leichteren Ansatz? Mir fiele jetzt nur noch ein das selbe ausgehend von xi zu machen, aber ob das wirklich besser ist wage ich zu bezweifeln. |
||
| 05.01.2016, 13:10 | HAL 9000 | Auf diesen Beitrag antworten » |
Einige grundlegende Vereinfachungen sind zunächst offensichtlich: a) Alle "echten" Teilmengen , d.h. wo ein mit existiert, kannst du sofort als obsolet streichen. In deinem Beispiel betrifft das , die ja beide in enthalten sind. b) Sind mehrere der gleich, so kann man alle bis auf eins dieser Exemplare streichen. Nach Anwendung von a) (s.o.) gibt es hier bei deinem Beispiel allerdings keine Anwendung mehr dafür. Ansonsten sieht mir das stark nach einem NP-vollständigen Problem aus. 
|
||
| 05.01.2016, 13:39 | Logiker | Auf diesen Beitrag antworten » |
Hi, Danke für den Hinweis mit den Teilmengen - das kann ich in der Tat vereinfachen. Dass es NP-vollständig ist kann ich mir gut vorstellen, daher dachte ich daran eine Gewichtung, ähnlich wie bei Schach, nur möglichst simpler zu verwenden. Man würde dann wohl nicht mehr die optimale Lösung erhalten aber die wahrscheinlich beste. Könnte ich auch mit leben. |
||
|
|