Blog / Research · RUCKSACKPROBLEM

Es ist einsichtig, dass man eine optimale Lösung erhalten kann, indem man alle Auswahl­möglich­keiten erzeugt, auf Zuläs­sigkeit überprüft und die Gesamt­profite aller zuläs­sigen Lösungen vergleicht. Da allerdings für n Items die Anzahl der Teilmengen 2ⁿ ist, wächst die Anzahl der zu betrach­tenden potenziel­len Lösungen stark in der Anzahl der Items an; dieses Vorgehen ist als nicht praktikabel³ anzusehen. Da das Rucksackproblem gleich­zeitig NP-schwer⁴ ist, ist die Existenz eines wesentlich besseren exakten Lösungs­algorithmus eher unwahr­scheinlich.

In jedem Fall kann aber die Instanz ausge­schöpft werden, d.h. wir modifi­zieren die Eingabe so, dass relativ uninte­ressante Randfälle ausge­schlossen werden, das Optimum jedoch nicht verändert wird. Wenn ein Item größeres Gewicht hat als die Kapazi­tät des Rucksacks, kann es in keiner Lösung vorkommen und wird entfernt. Weiter kann geprüft werden, ob alle Items zusammen in den Rucksack passen; falls ja, ist ebenfalls eine optimale Lösung gefunden⁵.

EIN GREEDY-ANSATZ

Eine naheliegende Idee ist, die Items nach ihrer Effizienz zu bewerten und auszu­wählen; intuitiv soll dadurch die zur Verfü­gung stehende Kapazität möglichst gut ausge­nutzt werden. Für jedes Item wird also seine Effizienz (das ist der Quotient aus Profit und Gewicht) berechnet. Dann werden die Items in abstei­gender⁶ Reihenfolge ihrer Effi­zienz in den Rucksack gepackt, bis kein Item mehr passt.

Diese Heuristik wird als greedy („gierig“) bezeichnet, da sie versucht, jeweils best­mögliche Einzel­schritte auszu­wählen, aber getrof­fene Entschei­dungen nicht revidieren kann.

Dieser Algorithmus ist wesentlich schneller als die Bewertung aller potenziel­len Lösungen; allerdings erzeugt sie nicht nur nicht immer eine optimale Lösung, sondern sie kann verglichen mit dem jewei­ligen Optimum sogar beliebig schlecht sein! Dies kann man über­raschender­weise an einer an k parame­trisierten Menge von Instanzen mit nur 2 Items erkennen.

Instanz:

• Item 1: Gewicht 1, Profit 1 („schlechtes Item“)
• Item 2: Gewicht k, Profit k-1 („gutes Item“)
• Rucksack mit Kapazität k

Da die Kapazität k ist, die Summe der Gewichte aber k+1, passen nicht beide Items in den Rucksack. Da beide Items alleine aber in den Rucksack passen, kommen nur 2 Lösungen in Frage.

Weil Item 2 einen größeren Profit hat als Item 1, ist Item 2 die optimale Wahl. Allerdings hat Item 1 eine Effizienz von (k-1)/k, was kleiner als 1 ist; da Item 1 die Effizienz 1/1=1 hat, würde durch die oben erwähnte Heuristik die Wahl auf Item 1 fallen. Weil dies nicht optimal ist, wir aber den optimalen Profit kennen, können wir ausrechnen, welchen Anteil am Optimum unsere Heuristik sicher­gestellt hätte - nämlich den Quotienten aus dem Profit von Item 1 und Item 2. Da dieser 1/(k-1) ist, können wir durch eine geeig­nete Wahl von k die Lösung unserer Heuristik (verglichen mit dem jeweiligen Optimum) beliebig schlecht werden lassen.

EIN APPROXIMATIONSALGORITHMUS

Hat unsere Intuition uns etwa getäuscht? Das Auswählen der Items nach Effizienz kann doch nicht völlig falsch sein.

Nun, das ist es auch nicht. Der Greedy-Ansatz würde optimale Lösungen berechnen, wenn alle Items die gleiche Größe (z. B. 1) hätten, weil dann jede zur Verfügung stehende Einheit der Kapa­zität optimal ausgenutzt wäre; Entweder ist der Rucksack dann immer komplett gefüllt oder die restliche Kapazität kann auch durch gar kein Item genutzt werden.

Wir stellen uns vor, dass wir unsere Items in Stücke der Größe 1 zer­schneiden, deren Profit jeweils anteilig aus dem Original-Item hervorgeht; somit haben alle diese kleinen Items die gleiche Effizienz wie das Item, aus dem sie entstanden sind und in der Summe auch den Original­profit. Aus jeder zulässigen Lösung der Original­instanz wird durch Zerschneiden der Items eine Lösung der zerschnit­tenen Instanz; da wir also die Lösungs­menge vergrößert haben⁷, ist das Optimum P₂ der zerschnit­tenen Instanz höchstens größer als das Optimum P₁ der Original­instanz.

Weitere Artikel:
➡ TOPOLOGISCHE SORTIERUNG
➡ TRAVELING SALESPERSON PROBLEM
➡ DYNAMISCHE PROGRAMMIERUNG
➡ GANTT CHARTS IN DER TOURENPLANUNG

In der Sortierung unterstellen wir, dass wir bei der Auswahl der kleinen Stücke nicht zwischen verschie­denen Original-Items hin- und herspringen. Führen wir dann unseren Greedy-Algorith­mus aus, wählen wir also zuerst die einzelnen Stücke ganzer Items; das letzte Item passt dann möglicher­weise nicht mehr komplett in den Rucksack. Den Rest dieses Items (nennen wir seinen Index j) heben wir auf. Da unser Rucksack keine freie Kapazität mehr hat und jede Kapazitäts­einheit optimal ausgenutzt ist, ist sein Gesamt­profit das Optimum P₂ der zer­schnittenen Instanz.

Leider ist die erzeugte Lösung nicht zulässig für die Original­instanz, weil das letzte Item j ja zer­schnitten wurde. Die ausge­wählten nicht zerschnit­tenen Items passen zusammen in den Rucksack; nehmen wir Item j komplett dazu, haben wir eine Menge von Items, die zwar zusam­men nicht mehr in den Rucksack passt, deren Gesamt­profit aber insgesamt mindestens das Optimum der Original­instanz ist!

Wir vergleichen nun den Profit von Item j und den Gesamt­profit der ausge­wählten nicht zer­schnittenen Items und nehmen die bessere der beiden Lösungen. Da die Summe dieser Profite mindestens das Optimum der Original­instanz ist, haben wir somit durch einen effizienten Algo­rithmus beweisbar mindestens die Hälfte des optimalen Profits gesichert.

Die Gütegarantie von Algorith­men wird üblicher­weise so angegeben, dass sie nicht kleiner als 1 ist (ggf. wird zum Kehrwert überge­gangen). Unser modifizierter Greedy-Algo­rithmus ist somit ein Approxi­mations­algorithmus mit Güte­garantie 2.

Es ist weiter eine nahelie­gende Frage, ob der oben vorge­stellte Approxima­tionsalgo­rithmus nicht eine bessere Güte­garantie als 2 hat; vielleicht haben wir ja nur dafür keine passenden Argumente gefunden? Leider ist das aber nicht der Fall, wie man an der folgenden, an k parametri­sierten Menge von Instanzen mit jeweils 3 Items sieht.

Instanz:

• Item 1: Gewicht 1, Profit 2
• Item 2: Gewicht k, Profit k
• Item 3: Gewicht k, Profit k
• Rucksack mit Kapazität 2k

Der optimale Profit ist 2k durch Auswahl von Item 2 und Item 3. Der Approxi­mations­algorithmus erreicht durch die Auswahl von Item 1 und Item 2 (oder 3) allerdings nur einen Profit von 2+k. Somit ist also für diese Menge von Instanzen der Anteil des algo­rithmisch gene­rierten Profits am optimalen Profit immer mindestens (2+k)/(2k)=1/k+1/2. Da sich dieser Quotient für größer werdende Werte von k an 1/2 annähert, ist die Güte­garantie von 2 für unseren Algo­rithmus exakt.

AUSBLICK

Obwohl das Rucksackproblem selbst relativ einfach zu verstehen ist, gibt es erstaun­lich umfang­reiche Literatur⁸, in der für die oben vorgestellte Version und andere Formu­lierungen Ergebnisse aus verschie­denen Bereichen (exakte Algorith­men, Approxi­mations­algorithmen, Heuristiken) vorge­stellt werden. Natürlich sind die hier vorge­stellten Inhalte ebenfalls dort zu finden.


Karriere & Jobs:

Du bist Student:in oder Absol­vent:in und interes­sierst dich für logistische Problem­stellungen oder für die Software­ent­wicklung? Dann warten bei FLS und in der Solvares Group spannende Aufgaben auf dich. Schau dich auf unserem Karriere­portal nach aktuellen Stellen­angeboten um oder bewirb dich einfach ini­tiativ: