Das Rucksackproblem. Ein Optimierungsproblem der Informatik

Inhaltsverzeichnis

1. EinleitungError! Bookmark not defined.

2. AllgemeinesError! Bookmark not defined.

2.1 Erläuterung der ProblematikError! Bookmark not defined.
2.2 Historischer Hintergrund und Bezug zu anderen ProblemenError! Bookmark not defined.

3. Greedy-AlgorithmusError! Bookmark not defined.

4. Algorithmus von Nemhauser und UllmannError! Bookmark not defined.

5. Dynamische ProgrammierungError! Bookmark not defined.

6. BacktrackingError! Bookmark not defined.

7. ZusammenfassungError! Bookmark not defined.

8. Tabellen- und AbbildungsverzeichnisError! Bookmark not defined.

9. QuellenverzeichnisError! Bookmark not defined.

1.Einleitung

In der diskreten Mathematik gibt es einige noch ungelöste Probleme, welche allgemein als Optimierungsprobleme der Kombinatorik bezeichnet werden. Es geht hierbei jeweils darum, aus einer Menge an Elementen eine Reihenfolge festzulegen, welche die geforderten Bedingungen möglichst genau erfüllen. Hierbei gibt es meist nur bis zu einem gewissen Punkt genaue und exakte Lösungen, da man hierfür alle Kombinationen (Möglichkeiten der Anordnung) durchgehen muss. Somit lässt sich meist nur eine Annäherung an die tatsächliche Lösung bestimmen.

Eines dieser kombinatorischen Optimierungsprobleme ist das Rucksackproblem. Dabei muss ein Rucksack mit Gegenständen gefüllt werden. Jeder Gegenstand besitzt einen bestimmten Wert und ein Volumen bzw. ein Gewicht. Ziel ist es den Rucksack so zu füllen, dass der Inhalt einen maximalen (optimalen) Wert ergibt, ohne das Gesamtvolumen bzw. Gesamtgewicht des Rucksacks zu überschreiten. Für eine überschaubare Anzahl an Gegenständen, lässt sich das Problem recht einfach lösen. Nehmen diese jedoch zu, so steigen die Möglichkeiten exponentiell an, wodurch das genaue Ergebnis selbst mit den schnellen Computern der heutigen Zeit nicht bestimmt werden kann, da dies zu große Zeitspannen in Anspruch nehmen würde.

Man geht davon aus, dass das Lösen einer der Probleme der kombinatorischen Optimierung ausreicht, um andere Aufgaben dieser Gattung wie das Traveling Salesman Problem (TSP) oder das Behälterproblem (Bin-Packing) zu klären. Dies zeigt zum Einen die hohe Komplexität des Themas, macht es andererseits aber auch interessant und spannend.

Zu Beginn möchte ich die allgemeine Formulierung weitergehend erläutern und mit Beispielen veranschaulichen, um die Thematik deutlich zu machen. Der historische Hintergrund und der Bezug zu den anderen Problemen der kombinatorischen Optimierung sollen in weiteren Abschnitten aufgezeigt werden. Der Schwerpunkt der Arbeit soll aber auf den Lösungsansätzen und Algorithmen liegen. Zunächst soll der Greedy-Algorithmus, welcher auch als Profitabilitätsindex bezeichnet wird, erläutert werden. Darauffolgend möchte ich weitere Approximationsalgorithmen zur Lösung des Problems wie den Nemhauser Algorithmus, den Backtrackingalgorithmus und die dynamische Programmierung vorstellen, ausführlich beschreiben und mit Beispielen (Auszüge aus der Programmierung) untermalen. Anhand dessen soll auch aufgezeigt werden, warum es nicht immer möglich ist, eine genaue Lösung zu finden und es sich meist um Näherungslösungen handelt. Das Fazit zu den beschriebenen Algorithmen soll den Abschluss der Seminararbeit bilden.

Ziel der Arbeit soll sein, dem Leser einen Einblick in die kombinatorische Optimierung und im Speziellen in das Rucksackproblem zu geben, um ein Verständnis der Thematik zu ermöglichen. Zudem sollen weitergehend verschiedene Lösungsansätze erläutert werden.

2. Allgemeines

2.1 Erläuterung der Problematik

Das Rucksackproblem ist ein spezielles Optimierungsproblem der Kombinatorik. Vorgegeben sind hierfür eine Menge n an Gegenständen, welche an einen Wert sowie ein Gewicht gebunden sind. Des Weiteren ist eine maximale Traglast des Rucksack vorgegeben. Der Rucksack soll nun so gefüllt werden, dass die maximale Traglast nicht überschritten wird und der Gesamtwert der Gegenstände möglichst maximal ist. Dabei ergibt sich eine Folge aus 0 und 1, wobei eine 1 für das Einpacken und eine 0 dementsprechend für nicht Einpacken steht.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Beispiel 1

Im Folgenden möchte ich die Thematik anhand eines Beispiel mit den Werten aus der obigen Tabelle verdeutlichen. Hierfür gehen wir von einem Maximalgewicht des Rucksacks von 5kg aus. Ziel ist es, zu entscheiden, welche der drei Gegenstände eingepackt werden sollen und welche nicht. Es fällt auf, dass Gegenstand Nr.2 ein so hohes Gewicht besitzt, wodurch es nicht möglich ist, einen weiteren Gegenstand einzupacken. Aufgrund dessen ist der Gesamtwert dieser Möglichkeit mit dem Wert des dazugehörigen Gegenstandes identisch. Die gewinnbringendste und damit für unseren Fall die bestmögliche Kombination ist, den ersten und dritten Gegenstand einzupacken. Dadurch wir das Gesamtvolumen nicht überschritten und der Gesamtwert maximal. Dementsprechend ergibt sich die folgende Lösung: 1-0-1.

Für diese geringe Menge an Gegenständen fällt es leicht, eine Lösung zu bilden. Jedoch wird es mit einer größeren Anzahl an Gegenständen schwieriger, die exakte Lösung zu finden und aufgrund dessen werden Algorithmen verwendet. Jedoch lässt sich selbst hiermit bei einer großen Menge die genaue Lösung nicht mehr exakt bestimmen. Für diesen Fall versucht man ein Ergebnis zu finden, welches der tatsächlich genauen Lösung sehr nahe ist. Durch Approximationsalgorithmen kann diese Näherungslösung errechnet werden. Um eine optimale Lösung zu erhalten, müsste man alle Kombinationen einzeln durchgehen und würde dabei diese finden. Man nennt dieses Vorgehen auch kombinatorische Optimierung (vgl. Atrops, D.-I. S.). Für eine große Menge an Objekten ist dies nicht möglich, da die Möglichkeiten exponentiell (Abbildung in dieser Leseprobe nicht enthalten) steigen. Dabei steht die Zwei für die beiden Wahlmöglichkeiten, die bei jedem Gegenstand zur Verfügung stehen. Nämlich einmal den Gegenstand einzupacken und einmal eben nicht. Das n steht, wie oben bereits erwähnt, für die Anzahl der Gegenstände zwischen denen eine Entscheidung getroffen werden muss. Mit Zunahme von n nehmen die Lösungsmöglichkeiten so hohe Bereiche an, dass man auch mit heutigen Computern keine exakte Lösung in angemessener Zeit erhält. Somit kann auf die verschiedenen Approximationsalgorithmen nicht verzichtet werden.

Das Rucksackproblem lässt sich auf mehrere alltagsbezogene Beispiele übertragen. So kann man sich zum Beispiel die Situation eines LKW-Besitzers vorstellen, welcher verschiedene Güter mit bestimmten Preisen besitzt. Sein LKW hat aber, ebenso wie der Rucksack, ein Maximalgewicht, welches nicht überschritten werden darf. Es liegt selbstverständlich im Interesse des Fahrers, den Laster so zu beladen, dass der Gewinn maximal ausfällt.

2.2 Historischer Hintergrund und Bezug zu anderen Problemen

Das Rucksackproblem gehört zu einer Reihe von 21 Problemen, welche als NP-vollständige Probleme bezeichnet werden. Als NP-vollständig gelten Probleme in der Mathematik und Informatik, welche zu den schwierigsten Problemen der NP gehören und nicht effizient lösbar sind. NP (nichtdeterministisch polynomielle Zeit) bezeichnet dabei verschiedenste Entscheidungsprobleme. Zu dieser Liste gehören auch das Partitionsproblem, das Mengenpackungsproblem und Knotenüberdeckungsproblem sowie weitere.

Den Grundstein hierfür legte Stephen Cook 1971 mit seinen Ergebnissen und Resultaten zum Erfüllbarkeitsproblem der Aussagenlogik (kurz SAT). Er bewies, dass dieses Problem NP-vollständig ist. Im darauffolgenden Jahr beschäftigte sich Richard Manning Karp mit dieser Art von Problemen und bewies dies für 20 weitere Probleme und erstellte eine Liste mit insgesamt 21 NP-vollständigen Problemen. Jedes Problem stellt dabei eine Reduzierung der Thematik eines anderen Problems da. So entspringt zum Beispiel das Rucksackproblem dem Problem der exakten Überdeckung. Dadurch wird auch klar, weshalb man davon ausgehen kann, dass es ausreicht, eines der Probleme zu lösen, um jedes andere NP-vollständige Problem zu lösen.

Die NP-vollständigen Probleme gehören zu einem der sieben Millennium-Probleme, welche noch ungelöst sind. Das Clay Mathematics Institute (Massachusetts, USA) hat für das Lösen eines dieser Probleme ein Preisgeld von einer Millionen US-Dollar ausgerufen. Ein Algorithmus, welcher das Rucksackproblem bzw. ein anderes Informatikproblem in angemessener Zeit lösen kann, wird als polynomialer Algorithmus bezeichnet.

3. Greedy-Algorithmus

Als Greedy-Algorithmus wird ein Optimierungsverfahren bezeichnet, welches sich in einer Entscheidungssituation für die Lösung entscheidet, „die zu dem aktuellen Zeitpunkt am erfolgversprechendsten erscheint, also den in diesem Schritt höchsten Beitrag zum Zielwert besitzt“ (vgl. Siepermann). Das bedeutet, dass dieser Approximationsalgorithmus sich auf die gegenwärtige Situation konzentriert, diese bewertet und entscheidet. Dementsprechend werden die daraus resultierenden Situationen nicht berücksichtigt. Vereinfacht kann also gesagt werden, dass eine Art Bewertungssystem der Optionen erstellt wird und aufgrund dessen eine Entscheidung getroffen wird.

Für das Rucksackproblem schaut das Prinzip des Greedy-Algorithmus wie folgt aus. Zunächst werden die verschiedenen Gegenstände (Objekte) bewertet und absteigend in einer Tabelle vermerkt. Die Bewertungsfunktion ist in diesem Fall der Quotient aus Wert und Gewicht. Daher wird der Greedy-Algorithmus oft auch als Profitabilitätsindex bezeichnet. Nun wird die Tabelle von oben nach unten abgearbeitet und die jeweiligen Objekte in den Rucksack eingepackt. Zudem wird der Wert des eingepackten Objektes vom Maximalgewicht subtrahiert. Dies geschieht solange, bis das Volumen des einzupackenden Objektes das restliche Gesamtgewicht übertrifft und es somit nicht mehr eingepackt werden kann. Der Algorithmus überprüft anschließend nach absteigendem Profitabilitätsindex, ob dies bei weiter unten stehenden Objekten nicht der Fall ist, um das Ergebnis zu maximieren.

Wir erweitern unser vorrangegangenes Beispiel um zwei neue Objekte (Nr4 und 5) mit jeweiligen Wert (5 und 12) und Gewicht (7 und 10) sowie der dazugehörigen Bewertung (Profitabilitätsindex). Wir nehmen hierfür an, dass das Maximalgewicht des Rucksacks bei 16kg liegt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Beispiel 2

Nun wird nach den oben bereits beschriebenen Kriterien begonnen, Objekte hinzuzufügen. Die ersten drei Objekte nach dem Profitabilitätsindex werden somit eingepackt. Damit haben wir einen aktuellen Gesamtwert von 20 und ein Gesamtgewicht von 9. Die Differenz zum möglichen Gesamtgewicht beträgt also 7. Das Gewicht des nächsten Objektes (Nr.4 nach Profitabilitätsindex) ist damit zu hoch und überschreitet das maximal zulässige Gesamtgewicht. Das letzte Objekt hingegen kann hinzugefügt werden und erhöht unser Gesamtgewicht auf das Maximalgewicht und unseren Gesamtwert auf 25. Das Ergebnis lautet also 1-1-1-0-1.

Im Folgenden soll der Greedy-Algorithmus programmiertechnisch umgesetzt werden.

Abbildung in dieser Leseprobe nicht enthalten

(Vgl. Atrops)

Abschließend kann zum Greedy-Algorithmus gesagt werden, dass er für kleine Mengen an Objekten recht zuverlässig den optimalen Gesamtwert ermittelt. Jedoch besteht bei hohen Mengen an Gegenständen die Gefahr einer deutlichen Differenz zum bestmöglichen Gesamtwert

[...]