Systematische Suche SS11
Inhaltsverzeichnis |
Rucksackprobleme
Bei den Rucksackproblemen handelt es sich um Optimierungsprobleme. Betrachtet werden dabei nicht-leere Mengen von n Objekten.
Jedes Objekt besitzt dabei zwei Kernattribute:
- einen Wert w
- ein Gewicht g
Als Begrenzung dient ein fest definierter Wert, die Kapazitätsbeschränkung K.
Gesucht ist die Menge derjenigen Objekte, die in der Summe einen maximalen Wert bei bestmöglicher Ausnutzung der Kapazität haben.
Beispiel
Ein LKW einer Spedition ist bis 50t belastbar. Es müssen einige Container transportiert werden:
- Container 1: Gewicht 10, Wert 60
- Container 2: Gewicht 20, Wert 100
- Container 3: Gewicht 30, Wert 120
Die Objektmenge besteht nun aus den folgenden Wertpaaren:
M = \left \{ \left ( 10, 60 \right ), \left ( 20,100 \right ), \left ( 30,120 \right )\right \}Die Kapazitätsbeschränkung K ist hier 50
K = 50Unterarten
- 0/1-Rucksackproblem (0-1 knapsack problem)
- Ein Objekt wird immer komplett oder gar nicht in die Ergebnismenge übernommen
- Bruchteil-Rucksack-Problem
- Ein beliebiger Teil t (0% ≤ t ≤ 100%) jedes Gegenstands darf übernommen werden
Auf dieser Seite beschränken wir uns auf das 0/1-Rucksackproblem. Bruchteil-Rucksack-Probleme werden bei den Greedy-Algorithmen besprochen.
Ziel
In mathematischer Schreibweise sieht die oben genannte Zielstellung folgendermaßen aus:
\sum_{i=1}^{n} x_{i}w_{i} \rightarrow maxWobei folgendes gelten muss:
\sum_{i=1}^{n} x_{i}g_{i} \leq K, mit x_{i} \in {0, 1}
Teilmengen-Summen-Problem (subset-sum-problem)
Versuch einer Lösung
Für das obige Beispielproblem gilt es nun eine Lösung zu finden. Man könnte annehmen, dass mit einer „gierigen“ Herangehensweise (Greedy-Strategie) ein optimales Ergebnis erreicht werden kann. Dabei geht immer der noch verbleibende Container mit dem höchsten Wert pro Gewicht in die Ergebnismenge ein, solange die obere Grenze K nicht erreicht wird. Unter dieser Annahme müsste Container 1 ein Teil der Ergebnismenge sein, da er den größten Quotienten aus Wert und Gewicht besitzt.
Aufzeigen der richtigen Lösung durch Probieren:
Die optimale Ergebnismenge enthält Container 2 und 3. Alle Ergebnisse mit Container 1 führen zu einen nicht optimalen Ergebnis, obwohl Container 1 das bessere Verhältnis aus Wert und Gewicht aufweist.
Es wird deutlich, dass die Greedy-Strategie bei 0/1-Rucksackproblemen zu keinem optimalen Ergebnis führt.