Systematische Suche WS13-14
Inhaltsverzeichnis |
Rucksackprobleme
Aus einer Menge von Gegenständen die einen Wert w und ein Gewicht g besitzen, gilt es einen Rucksack zu füllen bei dem der Gesamtwert der eingepackten Gegenstände maximal ist, ohne die Kapizitätsgrenze K des Rucksacks zu überschreiten.
Allgemein beschreiben Rucksackprobleme: Beladungsprobleme, Verschnittprobleme oder Probleme der Budgetkontrolle.
Beispiel
Thomas will sein Geld anlegen und versucht ein Investment-Portfolio zu erstellen, aus dem er sich maximalen Gewinn erhofft. Er hat 10000€ (K) zur Verfügung und will diese in unterschiedliche Aktien verteilen, welche eine Bewertung (w) und einen festen zu investierenden Wert (g) besitzen. Nun geht es darum ein Portfolio zusammenzustellen (Rucksack), in welchem die Gesamtbewertung aller gekauften Aktien maximal ist, dabei darf sein Budget nicht überzogen werden.
Zur Verfügung stehende Aktien:
| Aktie | Wert (in €) | Bewertung (0-10, höher ist besser) |
| Mapple | 2500 | 8 |
| Minisoft | 3000 | 4 |
| Le-Nogo | 5000 | 5 |
| Wogitech | 6000 | 3 |
| Joogle | 4000 | 7 |
Varianten
Es gibt viele unterschiedliche Formen des Rucksackproblems:
- 0/1 Rucksackproblem:
Hier wird ein Gegenstand entweder vollständig (1) oder gar nicht (0) eingepackt. Außerdem darf der selbe Gegenstand nur einmal eingepackt werden. - Bruchteil-Rucksackproblem:
Man kann einen beliebigen Teil t, mit 0\% \le t \le 100\%, eines Gegenstandes einpacken. - Unbeschränktes Rucksackproblem:
Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. K = \infty. - Teilmengen-Summen-Problem (subset-sum problem):
In diesem speziellen Fall geht es darum die Gewichtskapazität des Rucksacks optimal auszunutzen, da der Wert mit dem Gewicht übereinstimmt, d.h. g_i = w_i für alle i.
In diesem Artikel wird ausschließlich das 0/1 Rucksackproblem betrachtet. Bruchteil-Rucksackprobleme werden im Artikel der Greedy-Algorithmen behandelt.
Lösungsverfahren
Intuitives Verfahren
Ohne viel zu denken könnte man den Rucksack zufällig mit Gegenständen füllen, bis die Kapazitätsgrenze erreicht ist. Durch Austausch von jeweils 2 Objekten kann man den Gesamtwert nachträglich erhöhen. Ein im Rucksack befindlicher Gegenstand wird herausgenommen und durch einen höherwertigen, zuerst nicht eingepackten ersetzt, jedoch ohne die Kapazitätsgrenze zu überschreiten.
Dieses Verfahren hat aber mehrere Probleme. Erstens kann man bei diesem nicht systematischen Verfahren nie sicher sein das Wertmaximum zu erreichen. Ein weiteres Problem tritt auf, wenn wir das obige Beispiel betrachten. Wenn man noch nachträglich die Aktien tauscht um eine bessere Bewertung des Portfolios zu erreichen, bezahlt man Gebühren für jede Transaktion und vernichtet sich somit vielleicht den Vorteil der besseren Bewertung.
Es wäre also von Vorteil, Verfahren zu finden, die im Voraus die beste Lösung finden.
Tiefensuche
Das Tiefe-zuerst-Suchverfahren (engl. depth first search) oder kurz: die Tiefensuche stellt ein Lösungsverfahren für das oben benannte Rucksackproblem dar.
Voraussetzung:
Vorgehensweise: