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 Kapazitä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 zerschneiden, 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 Originalprofit. Aus jeder zulässigen Lösung der Originalinstanz wird durch Zerschneiden der Items eine Lösung der zerschnittenen Instanz; da wir also die Lösungsmenge vergrößert haben
7, ist das Optimum
P2 der zerschnittenen Instanz höchstens größer als das Optimum
P1 der Originalinstanz.
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 verschiedenen Original-Items hin- und herspringen. Führen wir dann unseren Greedy-Algorithmus aus, wählen wir also zuerst die einzelnen Stücke ganzer Items; das letzte Item passt dann möglicherweise 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ätseinheit optimal ausgenutzt ist, ist sein Gesamtprofit das Optimum
P2 der zerschnittenen Instanz.
Leider ist die erzeugte Lösung nicht zulässig für die Originalinstanz, weil das letzte Item
j ja zerschnitten wurde. Die ausgewählten nicht zerschnittenen Items passen zusammen in den Rucksack; nehmen wir Item
j komplett dazu, haben wir eine Menge von Items, die zwar zusammen nicht mehr in den Rucksack passt, deren Gesamtprofit aber insgesamt mindestens das Optimum der Originalinstanz ist!
Wir vergleichen nun den Profit von Item
j und den Gesamtprofit der ausgewählten nicht zerschnittenen Items und nehmen die bessere der beiden Lösungen. Da die Summe dieser Profite mindestens das Optimum der Originalinstanz ist, haben wir somit durch einen effizienten Algorithmus beweisbar mindestens die Hälfte des optimalen Profits gesichert.
Die Gütegarantie von Algorithmen wird üblicherweise so angegeben, dass sie nicht kleiner als 1 ist (ggf. wird zum Kehrwert übergegangen). Unser modifizierter Greedy-Algorithmus ist somit ein Approximationsalgorithmus mit Gütegarantie 2.
Es ist weiter eine naheliegende Frage, ob der oben vorgestellte Approximationsalgorithmus nicht eine bessere Gütegarantie 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 parametrisierten 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 2
k durch Auswahl von Item 2 und Item 3. Der Approximationsalgorithmus 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 algorithmisch generierten Profits am optimalen Profit immer mindestens (2+
k)/(2
k)=1/
k+1/2. Da sich dieser Quotient für größer werdende Werte von
k an 1/2 annähert, ist die Gütegarantie von 2 für unseren Algorithmus exakt.
AUSBLICK
Obwohl das Rucksackproblem selbst relativ einfach zu verstehen ist, gibt es erstaunlich umfangreiche Literatur
8, in der für die oben vorgestellte Version und andere Formulierungen Ergebnisse aus verschiedenen Bereichen (exakte Algorithmen, Approximationsalgorithmen, Heuristiken) vorgestellt werden. Natürlich sind die hier vorgestellten Inhalte ebenfalls dort zu finden.
Karriere & Jobs:
Du bist Student*in oder Absolvent*in und interessierst dich für logistische Problemstellungen oder für die Softwareentwicklung? Dann warten bei FLS spannende Aufgaben auf dich. Schau dich auf unserem Karriereportal nach aktuellen Stellenangeboten um oder bewirb dich einfach initiativ: