8 - 1
Teil 8 Rucksackproblem, Dynamische Programmierung, Branch&Bound
================================================================
Rucksackproblem:
Gegeben m Päckchen mit Gewichten g1,g2,...,gm und ein Rucksack
mit Kapazität K (alles natürliche Zahlen).
Gesucht ist eine Teilmenge der Päckchen, die den Rucksack möglichst gut ausfüllt, ohne die Kapazitätgrenze zu überschreiten.
Beispiel
Päckchen
Gewicht
(1) (2) (3) (4)
7
6
4
4
Kapazität
K = 16
Was ist die Optimallösung für diesen Datensatz?
Wir beginnen mit zwei naheliegenden Lösungsansätzen für das
Rucksackproblem:
Vollständige Enumeration: Wir probieren alle Teilmengen aus und
nehme von denen, die in den Rucksack hineinpassen, die beste.
Was sind Argumente für oder gegen die Praktikabilität dieser
Strategie?
Greedy-Heuristik: Wir fangen mit den großen Päckchen an, wählen
stets das nächst kleinere und packen es in den Rucksack, sofern
es hineingeht. - Die Motivation dieser Heuristik ist, daß die zum
Schluß eingepackten kleineren Päckchen die Ecken besser ausfüllen.
Hinweis: Die Greedy-Heuristik die größten Päckchen zuerst ist
nicht immer optimal. Immerhin ist es eine Tatsache, daß man auf
diese Weise mindestens 50% des maximal möglichen Gewichtes
bekommt, man weise dies nach!
An Beispielen demonstriere man, daß mehr als 50% von der GreedyHeuristik nicht garantiert werden können.
Zwei Anwendungen des Rucksackproblems:
Verschnittproblem
Gegeben ist ein Rohprodukt bekannter Größe. Aus dem möchte man
Fertigprodukte ausschneiden, die in ihrer Größe ebenfalls bekannt
sind. Je nachdem für welche Fertigprodukte man sich entscheidet,
wird das Rohprodukt mehr oder weniger gut ausgenutzt.
Frage: Welche Fertigprodukte soll man auswählen, um möglichst
wenig Rest (Verschnitt) zu haben?
Offensichtlich ist dieses Verschnittproblem nichts anderes als
eine Umformulierung des Rucksackproblems.
Verschnittprobleme gibt es in der Praxis in vielerlei Varianten
und auch in viel komplexerer Gestalt als der eben genannten.
8 - 2
Reihenfolgeproblem
Man hat zwei gleichartige Maschinen. Man hat ferner Jobs, von
denen jeder auf einer der Maschinen (gleichgültig auf welcher) zu
bearbeiten ist. Ebenfalls bekannt sind die Bearbeitungszeiten der
Jobs.
Frage: Wie soll man die Jobs auf die beiden Maschinen verteilen,
um möglichst früh mit allen Jobs fertig zu sein?
[ Man kann an Kopierjobs denken und an zwei gleichartige Kopierer, die für die Jobs zur Verfügung stehen.
]
Bearbeitungszeit
J1
5
J2
5
J3
5
J4
7
J5
8
Eine Möglichkeit ist
m1
m2
|********* J5 **********|****** J2 ****|
0--+--+--+--+--5--+--+--+--+-10--+--+--+--+-15--+--+
|******** J4 ********|**** J1 ******|***** J3 *****|
mit Gesamtdauer 17. Aber offensichtlich geht es auch mit
Gesamtdauer 15, wenn man nämlich die Jobs J1,J2,J3 von der einen
Maschine bearbeiten läßt, J4 und J5 von der anderen.
Auch das Reihenfolgeproblem kann als Rucksackproblem interpretiert werden, wie?
------------------------------------------------------------Da unsere ersten beide Ansätze zur Lösung des Rucksackproblems
nicht überzeugen (vollständiger Enumeration dauert zu lange, die
Greedy-Heuristik ist nicht gut genug), suchen wir nach Besserem:
Dynamische Programmierung zur Lösung des Rucksackproblems
Die Idee ist rekursives Vorgehen. Wir reduzieren den Datensatz:
Statt aller m Päckchen lassen wir nur die ersten i Päckchen zur
Konkurrenz zu, i≤m, und statt der vollen Kapazität K lassen wir
an Kapazität nur k zu, k≤K. Den Optimalwert des so eingeschränkten Rucksackproblems bezeichnen wir mit
fik , i=1,...,m;
k=0,...,K
8 - 3
Gesucht ist letztlich die einzige Zahl fmK , d.h. der Optimalwert
des Rucksackproblems mit voller Kapazität K und Auswahlmöglichkeit zwischen allen Päckchen.
Die fik lassen sich folgendermaßen rekursiv berechnen:
Bellmannsche Rekursiongleichung
Für den Optimalwert fik des (wie oben erläutert) eingeschränkten
Rucksackproblems gilt (warum?) die Rekursionsformel:
-----------------------------------| fik = max { fi-1,k , gi + fi-1,k-gi } |
------------------------------------
i=1,...,m
k=0,...,K
wobei f0k = 0 für alle k und fi0 = 0 für alle i .
Für unser obiges Beispiel erhalten wir die folgende Tabelle:
i g\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16=K
--------------------------------------------------------------1 7 | 0 0 0 0 0 0 0 7 7 7
7
7
7
7
7
7
7
|
2 6 | 0 0 0 0 0 0 6 7 7 7
7
7
7 13 13 13 13
|
3 4 | 0 0 0 0 4 4 6 7 7 7 10 11 11 13 13 13 13
|
4 4 | 0 0 0 0 4 4 6 7 8 8 10 11 11 13 14 15 15
(4=m)
Mit Dynamischer Optimierung findet man die Optimallösung für das
Rucksackproblem. - Ist die Methode aber auch effizient?
Dazu klären wir den Rechenaufwand: Das Tableau hat m Zeilen und K
Spalten. Pro Eintrag ist eine Addition und ein Vergleich auszuführen. Der Rechenaufwand ist also proportional zum Produkt von
m und K
O(m*K),
und es sieht so aus, als hätten wir den gesuchten schnellen
Algorithmus.
Aber das ist leider ein Trugschluß: Angenommen, die Kapazität ist
106 und wir haben nur vier Päckchen mit Gewichten wie
7 , 321 , 123477 , 523313 .
8 - 4
Machen wir für diesen Datensatz Dynamische Programmierung wie
beschrieben, so haben wir ein Tableau mit einer Million Spalten
auszufüllen!
Dies ist eine offensichtliche Absurdität. Wir werden später versuchen, den Ansatz der dynamischen Programmierung effizienter zu
gestalten, aber zunächst probieren wir etwas anderes.
Branch&Bound zur Lösung des Rucksackproblems
Wir unterteilen die Lösung in Stufen, und auf jeder Stufe
entscheiden wir über ein weiteres Päckchen.
Genauer: Auf Stufe i entscheiden wir über das i-te Päckchen
(Päckchen i dabei/nicht dabei). Die beiden resultierenden
Möglichkeiten werden auf Stufe i+1 einzeln weiterverfolgt.
Bei unserem Beispiel mit 4 Päckchen (m=4)
Päckchen
Gewicht
(1) (2) (3) (4)
7
6
4
4
Kapazität K=16
entsteht der folgende Suchbaum:
START
1
(7)
¬1
(0)
2
¬2
2
¬2
(13)
(7)
(6)
(0)
/
\
/
\
/
\
/
\
3
¬3
3
¬3
3
¬3
3
¬3
(17)
(13)
(11)
(7)
(10)
(6)
(4)
(0)
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 ¬4
4 ¬4
4 ¬4
4 ¬4
4 ¬4
4 ¬4 4
¬4 4 ¬4
(21)(17) (17)(13)(15)(11) (11)(7) (14)(10)(10)(6)(8) (4) (4)(0)
Die beste zulässige Lösung hat Gewicht 15 und findet sich auf dem
Pfad (1,¬2,3,4).
Dieser Suchbaum hat die Tendenz, für wachsende Päckchenzahl
gigantische Ausmaße anzunehmen, aber in vielen Fällen kann man
ihn (manchmal sogar dramatisch) verkleinern durch Ausnutzen von
Bounds:
8 - 5
Bound: Man braucht unterhalb der aktuellen Ecke nicht weiterzusuchen, wenn man dort mit Sicherheit nicht mehr bekommen kann als
man ohnehin schon hat.
Suche in die Tiefe: Wendet man diesen Bound bei unserem Beispiel
an, so erhalten wir den folgenden, stark verkleinerten Suchbaum.
Dabei navigieren wir über den Suchbaum nach dem Prinzip Suche in
die Tiefe, d.h. wir gehen immer links runter sofern möglich.
START
1
(7)
2
¬2
(13)
(7)
/
\
/
3
¬3
3
(17)
(13)
(11)
/ \
/
4 ¬4
4
(17)(13) (15)
|
|
1.Lösung
2.Lösung
Restgewicht:
¬1
(0)
|
|
|
|
|
|
|
|
|
[14]
[8]
[4]
Wir wollen den Rechenaufwand dieses Branch&Bound-Verfahrens
bestimmen (zunächst in der reinen Form ohne Bounds). Und das ist
sehr einfach: Bei jeder Stufe des Suchbaumes verdoppelt sich die
Anzahl der Ecken des Baumes. Bei m zur Auswahl stehenden Päckchen hat allein das unterste Baumniveau 2m (exponentiell viele)
Ecken.
Mit anderen Worten: Das Verzweigungsverfahren, wie beschrieben in
reiner Form angewandt, ist bei größeren Päckchenzahlen m wegen
des großen Rechenaufwandes völlig untauglich.
Die Frage ist, ob gute Bounds die Situation entscheidend verbessern. Nehmen wir an, wir haben 100 Päckchen (m=100), nehmen wir
außerdem (sehr optimistisch) an, daß wir einen extrem guten Bound
haben, der die Größe des Suchbaumes auf ein Tausendstel verringert. Dann verringert der Bound den Rechenaufwand von 2100 auf
2100/1000 ≈ 2100/210 = 290
8 - 6
und das ist immer noch eine astronomisch große Zahl.
Letztlich sind unsere beiden Lösungsansätze (Dynamische Programmierung und Branch&Bound) unbefriedigend geblieben, sodaß wir die
Suche nach schnellen, optimalen Algorithmen aufgeben (aber weiteres zu diesem Thema siehe Teil 10) und uns für den Moment mit
Näherungslösungen zufrieden geben.
---------------------------------------------------------------Approximationsschemata beim Rucksackproblem
Wir wissen: Die simple Heuristik Die größten Päckchen zuerst
garantiert (nur) 50% des maximal möglichen Gewichtes.
Die Frage ist naheliegend, ob es nicht ein Verfahren gibt, das
ebenfalls schnell arbeitet, das aber eine wesentlich bessere
Gütegarantie gibt als 50%. In der Tat gibt es so etwas für das
Rucksackproblem. Die Methode, die wir vorstellen wollen, beruht
auch auf Dynamischer Programmierung, aber angewandt auf einen
variierten Datensatz.
Das Unangenehme bei dynamischer Programmierung ist, daß sie mit
großen Zahlen (für Kapazität und Gewichte) schlecht fertig wird.
Die Idee ist, Kapazität und Gewichte auf einen hinreichend kleinen Bereich proportional abzubilden und erst dann dynamische
Programmierung anzuwenden.
Dabei bekommen wir allerdings das Problem, daß die Ganzzahligkeit
der Daten verloren gehen kann. Nehmen wir etwa die Daten
g : 7 , 321 , 123477 , 523313
mit
K = 106
so kommen wir praktikable Zahlen, wenn wir durch 1000 dividieren.
Aber dann gehen bis zu drei Dezimalstellen verloren, und die
mittels dynamischer Programmierung gefundene Lösung ist vermutlich nicht mehr die Optimallösung des Ausgangsproblems.
Unsere Hoffnung ist: Die Optimallösung des variierten Datensatzes
ist (bezüglich der Original-Gewichte) nicht allzu schlecht, d.h.
nur wenig schlechter als die Optimallösung des originalen Datensatzes.
Diese Hoffnung ist in der Tat berechtigt, und wir werden im folgenden die Güte der Näherungslösung genauer quantifizieren.
Sei gegeben ein Datensatz für das Rucksackproblem:
--------------------------| I : g1 , g2 ,..., gm ; K |
---------------------------
8 - 7
Den Optimalwert von I bezeichnen wir mit OPT(I). Ohne Einschränkung der Allgemeinheit können wir
OPT(I) ≥ K/2
annehmen (im Falle OPT(I) < K/2 haben alle Päckchen, die einzeln
in den Rucksack hineinpassen, zusammen weniger als K/2 Gewicht).
Wir wählen nun eine natürliche Zahl n und multiplizieren alle
Zahlen im Datensatz I mit
m*n/K
(Motivation siehe unten) wobei wir nach oben aufrunden, falls die
Division durch K nicht aufgeht (warum Aufrunden nach oben?):
gi' = ⌈gi*m*n/K⌉
,
K' = ⌈ K*m*n/K ⌉ = m*n
Auf diese Weise erhalten wir den variierten Datensatz I':
-------------------------------| I' : g1' , g2' ,..., gm' ; K' |
-------------------------------Die hinter diesen Manipulationen stehende Idee ist folgende:
Multiplikation mit m/K ändert die Kapazität auf den Wert m, das
Tableau bei dynamischer Programmierung wäre dann quadratisch mxm.
Nochmalige Multiplikation mit n ändert die Kapazität auf m*n, und
das Tableau bekommt das Format (m,mxn). Der Faktor n ermöglicht
es uns also, die Spaltenzahl des Tableaus und damit den Rechenaufwand flexibel zu steuern.
Den Datensatz I' lösen wir nun mit dynamischer Programmierung.
Der Rechenaufwand bei dynamischer Programmierung hat die Größenordnung Zeilenzahl*Spaltenzahl. Das zu I' gehörende Tableau verursacht also Rechenaufwand
O(m²*n) .
Ferner erkennt man, daß die für I' optimale Päckchenauswahl
jedenfalls zulässig für das Ausgangsproblem I ist.
[ Warum? Wichtig ist dabei, daß die Zahlen nach oben gerundet
wurden und nicht etwa nach unten.
]
Bleibt die Frage, wie gut die Optimallösung von I' bezüglich der
Original-Daten (also bezüglich der gegebenen gi) ist.
Wir führen eine Bezeichnung ein: Sei An(I) der Originalwert der
mittels I' gefundenen Lösung (also die Summe der originalen
8 - 8
Päckchengewichte der für I' gefundenen Lösung).
Die Frage ist, wie weit An(I) vom Optimalwert OPT(I) des Problems
abweichen kann, wie groß also OPT(I)-An(I) maximal werden kann.
Die Antwort ist:
OPT(I) - An(I) ≤ K/n
Dies ist die entscheidende Ungleichung, deren Gültigkeit wir an
einem kleinen Beispiel demonstrieren wollen:
(I)
g: 40
==
10
==
21
11
;
K=50
(1)
Die Optimallösung ist unterstrichen und hat Wert 50. Hätten wir
etwa 1/10 als Multiplikationsfaktor, so bekämen wir
4
1
2.1
1.1
;
4
1
3
=
2
=
;
5
(2)
und dann
(I') g':
K'=5
(3)
Eine Optimallösung mit Wert 5 ist unterstrichen. Bezüglich der
Originaldaten hat diese Lösung nur den Wert 21+11=32 (statt 50).
Wir analysieren allgemein: Von (2) nach (3) ist die maximal mögliche Werteinbuße 1 pro Päckchen (2.1 statt 3 und 1.1 statt 2).
Dieser Wertverlust findet schlimmstenfalls bei allen Päckchen
statt, also ist der Verlust zwischen (2) und (3) höchstens m.
Zwischen (1) und (2) wird mittels Faktor m*n/K proportional
reduziert, also ist der insgesamt mögliche Wertverlust höchstens
m*K/(m*n) = K/n.
Im Zahlenbeispiel wären das 4*10 = 40. Der tatsächlich eingetretene Verlust war nur 50-32=18.
Die Güte der mittels I' gefundenen Näherungslösung kann nun
einfach ausgerechnet werden. Wir berechnen das Verhältnis von
Näherungswert zu Optimalwert:
An(I)
OPT(I) - K/n
K/n
------ ≥ ------------ = 1 - -----OPT(I)
OPT(I)
OPT(I)
(*)
≥ 1 -
K/n
--- =
K/2
1-2/n
Bei der Ungleichung (*) erinnern wir uns an die oben gemachte
Annahme OPT(I)≥K/2. Insgesamt haben wir folgendes Ergebnis:
8 - 9
Polynomiales Approximationsschema
Lösen wir wie oben beschrieben das Rucksackproblem durch Skalieren mit Parameter n und anschließender Dynamischer Programmierung
angewandt auf den skalierten Datensatz, so gilt für den relativen
Abstand zwischen gefundenem Wert An(I) und theoretischem Wert
OPT(I) die Abschätzung
---------------------| An(I)
|
| ------ ≥ 1 - 2/n |
| OPT(I)
|
---------------------Der Rechenaufwand O(m²*n) ist dabei polynomial in Päckchenzahl m
und Gütemaß n.
Beispiel
Wir wollen dieses Verfahren an unserem Beispiel
(I):
g1
7
g2
6
g3
4
g4
4
;
K
16
demonstrieren. Der Optimalwert ist von I ist 15, wie wir wissen.
Wir wählen n=3. Der Garantiewert ist dann
1 - 2/n
=
1-2/3
= 1/3
wir haben also mindestens Wert 15/3=5 in der folgenden Näherung
zu erwarten (was wenig ist im Vergleich zu 15, aber wir haben ein
kleines n gewählt).
Wir skalieren den Datensatz und berechnen zunächst den Skalierungsfaktor:
m*n/K = 4*3/16 = 3/4
Wir müssen die Daten in I also mit 3/4 malnehmen und nach oben
runden. Das liefert
(I'):
g1'
6
g2' g3'
5
3
g4' ;
3
K'
12
Den Datensatz I' lösen wir mittels gewöhnlicher dynamischer
Programmierung:
8 - 10
i g'\k 0
1
2
3
4
5
6
7
8
9 10 11 12=K'
--------------------------------------------------------1 6 | 0
0
0
0
0
0
6
6
6
6
6
6
6
|
2 5 | 0
0
0
0
0
5
6
6
6
6
6 11 11
|
3 3 | 0
0
0
3
3
5
6
6
8
9
9 11 11
|
4 3 | 0
0
0
3
3
5
6
6
8
9
9 11 12
(=m)
Der Optimalwert (im skalierten Problem!) ist 12 und zwar realisiert durch die Päckchen 1,3 und 4. Bezüglich der Originaldaten
haben diese Päckchen das Gewicht 7+4+4=15, und das ist der Optimalwert für I!
Unsere Skalierungsmethode hat also in diesem Falle sogar den
Optimalwert gefunden, und der Garantiewert (5 statt 15) erwies
sich als sehr konservativ.
-----------------------------------------------------------Verallgemeinertes Rucksackproblem (mit Gewichten und Werten)
Gegeben sind n Päckchentypen, von jedem Typ unbeschränkt viele
Exemplare. Ein Päckchen vom Typ i hat Gewicht gi und Wert wi.
Gesucht ist die Rucksackfüllung, deren Gewicht die Kapazität K
nicht überschreitet und die maximalen Gesamtwert hat.
Daten:
P'typen
Wert
Gewicht
(1)(2)(3)(4)
1 3 5 9
2 3 4 7
Kapazität
K = 10
Greedy-Heuristik: Als nächstes Päckchen wähle man stets das
spezifisch wertvollste, also das Päckchen, das den Quotienten
wi/gi maximiert und das zusammen mit den schon eingefüllten
Päckchen die Kapazitätsgrenze K nicht überschreitet.
Diese Heuristik ist aber nicht immer optimal, Gegenbeispiel?
Wie lautet die Bellmansche Rekursionsgleichung dieser Problemvariante?
Man löse das Beispiel per Branch&Bound. Aus der oben angegebenen
Regel kann in naheliegender Weise ein Bound abgeleitet werden.
© Copyright 2024 ExpyDoc
