Algorithmus gesucht

[bushbarack]

Hallo miteinander,
ich bringe mir hobbymäßig ein wenig Python frei, und würde gerne wissen, ob es für das folgende Problem einen Lösungsalgorithmus gibt, da mir selbst nicht wirklich einfällt, wie ich es sinnvoll (und effizient!) lösen könnte.
Es geht darum, dass ich eine gewisse Menge an Gegenständen habe, jeder mit einem Gewicht und einem Nutzwert. Nun würde ich gerne diese Gegenstände auf zwei Taschen aufteilen, und zwar so, dass die Gewichtsdifferenz minimal ist und der Unterschied im Nutzwert möglichst unter einem bestimmten Wert bleibt.
Das erinnert mich zwar ein wenig an das bekannte Rucksackproblem, aber hier geht es ja nicht darum, Gegenstände auszuwählen, sondern darum, diese möglichst gleichmäßig zu verteilen.
Kennt da jemand etwas, was mich weiterbringen könnte?
Ich bedanke mich herzlich im Voraus

[EyDu]

Du suchst das "Partitionsproblem".

[bushbarack]

Du suchst das "Partitionsproblem".

Hey, danke, das ist genau, was ich gesucht habe. Jetzt muss ich nur noch eine vernünftige Seite, die den Algorithmus erläutert, finden.

[EyDu]

Auf Wikipedia stehen mehrere Lösungen für das Problem und zusätzlich noch Approximationen.

[bushbarack]

Hmm, jetzt habe ich als Approximation den Greedy-Algorithmus von der besagten Wikipedia-Seite implementiert, verstehe aber jetzt noch nicht ganz, wie ich die Nutzwert-Differenz kontrollieren kann...

[EyDu]

Hallo.

Was meinst du denn mit "kontrollieren"? Willst du wissen, wie gut deine Lösung am Optimum liegt? Da wird lediglich eine 4/3*OPT-Schranke gegeben. Wie weit du von der Korrekten lösung weg bis lässt sich nur sagen, wenn du das Optimum aus ausrechnest.

[bushbarack]

Hallo.

Was meinst du denn mit "kontrollieren"? Willst du wissen, wie gut deine Lösung am Optimum liegt? Da wird lediglich eine 4/3*OPT-Schranke gegeben. Wie weit du von der Korrekten lösung weg bis lässt sich nur sagen, wenn du das Optimum aus ausrechnest.

Naja, als Bedingung meines Ausgangsproblems war halt gegeben, das die Differenz der Nutzwerte zwischen den beiden Taschen nicht größer als ein bestimmter Schwellenwert sein, darf.

[EyDu]

Dann bleibt dir wohl nichts anderes übrig, als die Implementierung für die optimale Lösung zu schreiben. Prinzipiell ist die ja schnell runterprogrammiert. Ein Problem könnte dann natürlich die Laufzeit werden, aber dass hängt natürlich stark von der Anzahl der Elemente ab.

Da ich dein konkretes Szenarion nicht kenne, könntest du zunächst auch die Lösung approximieren und schauen ob alle Nebenbedingungen erfüllt werden. Erst wenn das nicht der Fall ist, steigst du auf das Optimum um.

[bushbarack]

Dann bleibt dir wohl nichts anderes übrig, als die Implementierung für die optimale Lösung zu schreiben. Prinzipiell ist die ja schnell runterprogrammiert. Ein Problem könnte dann natürlich die Laufzeit werden, aber dass hängt natürlich stark von der Anzahl der Elemente ab.

Da ich dein konkretes Szenario nicht kenne, könntest du zunächst auch die Lösung approximieren und schauen ob alle Nebenbedingungen erfüllt werden. Erst wenn das nicht der Fall ist, steigst du auf das Optimum um.

Ja, das Optimum, sprich Brute-Force habe ich schon geschrieben, aber bei 40 Elementen habe ich mir ne Laufzeit von nem knappen Jahr ausgerechnet ^^ Trotzdem danke für deine Hilfe, hast mich auf jeden Fall weitergebracht.

[darktrym]

Gibts denn keine brauchbaren Approximationsalg. dafür wenn es schon in npc ist?

[EyDu]

Durch Pruning kann man noch, abhängig von den Daten, jede Menge rausholen. Wenn man das Backtracking von Listen auf Bits umstellt, dann wird das ganze ebenfalls noch einmal ein Stückchen schneller. Pypy oder eine Lösung direkt in C++ schaffen auch noch ganz gut etwas. Wobei der Unterschied bei mir zwischen C++ und Pypy im Prinzip nicht messbar ist. Mit etwas Optimierung, oder gleich auf Assemblerebene, ist vielleicht noch ein wenig drin. Ich hatte jetzt aber keine Lust mich durch den Maschinencode zu wühlen. Damit du es nicht selber Programmieren musst:

Python
C++

Schafft natürlich keine Sprünge in der Komplexität, aber ein paar mehr Elemente kann man noch hinzunehmen.

Edit: Ok, wenn man natürlich die Sortierung in C++ vernünftig für das Pruning umsetzt, dann wird es auch schneller und nicht maximal langsam ^^:
C++

Edit 2: Zum dem Jahr Berechnung mit 40 Elementen:

Code: Alles auswählen

g++ partitioning.cpp -o partitioning -O3
./partitioning 40 100

duration = 233                                                                                                             
diff = 1                                                                                                                   
elements = 86 65 10 65 60 34 33 95 24 65 70 42 68 34 77 52 80 7 52 5 64 32 28 71 62 52 67 80 60 49 4 46 15 14 63 27 49 96 75 73                                                                                                                       
left = 65 65 64 63 62 60 60 52 52 52 49 49 46 42 34 34 33 32 28                                                            
right = 96 95 86 80 80 77 75 73 71 70 68 67 65 27 24 15 14 10 7 5 4

Das Jahr ging in unter vier Minuten aber schnell rum ^^

[bushbarack]

Okay, das sieht doch schon mal sehr vielversprechend aus, ich werde mich wohl jetzt erst einmal durch den ganzen Code arbeiten müssen. Ich habe leider leider viel zu wenig Ahnung von sowas, bin ja auch nur Schüler

[EyDu]

Ich fasse die wichtigsten Dinge mal kurz zusammen, dann musst du nicht rätseln:

- Die zu kombinierenden Elemente werden zunächst in umgekehrter Reihenfolge sortiert. Damit wird sichergestellt, dass unsinnige Kombinationen möglichst schnell verworfen werden. Anders ausgedrückt: es wird erst grob aufgeteilt, erst am Ende folgt, fall möglich, eine Feinaufteilung.

- Ein Suchast wird dann abgebrochen, wenn a) keine Elemente mehr zur Verteilung übrig sind oder b) wenn die Summe der verbleibenden Elemente und des kleineren Stapels kleiner sind als der große Stapel. Im letzten Fall werden alle Elemente dem kleineren Stapel zugewiesen, da alle anderen Kombinationen keinen Sinn mehr machen.

- Statt ständig Listen von Elementen zu speichern wird für den "linken" Stapel in Integer angelegt. Ist bei dem Integer das i-te Bit gesetzt, so befindet sich das i-te Element der sortierten Elemente auf der linken Seite, sonst auf der rechten. Das spart jede Menge Listenoperationen, welche ganz schön auf die Performance drücken. Bei der C++-Lösung ist so die Anzahl der Elemente begrenzt, auf den meisten Maschinen sollten das aber mittlerweile 64 mögliche Elemente (Bits) sein. So viele Kombinationen will man eh nicht ausprobieren ^^

Was ich nicht implementiert habe, aber eine richtige Beschleunigung bringen sollte, ist die Aufteilung einer Anfrage mit vielen Elemente in mehrere Anfragen mit weniger Elementen. Wenn du 128 Elemente aufteilen musst, dann böten sich zum Beispiel vier Suchen mit 32 Elementen an. Abschließen dann man dann noch eine Aufteilung der 4 Ergebnisse vornehmen, also nur noch eine Aufteilung auf vier Elementen.

Das sollte, wenn die Daten in etwas gleichverteil sind, eine sehr gute (allerdings ohne eine Qualitätsgarantie) Näherung geben. Das funktioniert, da es bei genügend vielen Elementen fast immer eine gute Aufteilung gibt, bei der die Differenz sehr klein ist. Da hilft aber nur, es auf den eigenen Daten zu testen.