5.4 Das Rucksackproblem - Startseite TU Ilmenau · Das Rucksackproblem 0-1-Variante Korrektheit des ermittelten Wertes m[n,b] ergibt sich aus den Bellman’schen Optimalit atsgleichungen

Das Rucksackproblem

5.4 Das RucksackproblemProblemstellung:

Eingabe: Ganzzahlige Volumina a1, . . . , an > 0, Nutzenwertec1, . . . , cn > 0, ganzzahlige Volumenschranke b.

Aufgabe: Packe die Objekte in einen Rucksack von Volumen b, so dassder Gesamtnutzen maximiert wird. (Wird gleich noch formalisiert.)

Wir betrachten zwei Problemvarianten:

1 Rucksackproblem mit Wiederholungen. (Von jedem Objekt sindbeliebig viele Kopien vorhanden.)

2 0-1-Rucksackproblem. (Jedes Objekt ist genau einmal vorhanden.)

Im Gegensatz zum fraktionalen Rucksackproblem (Kap. 3.1) ist es hiernicht erlaubt, Objekte zu teilen.Der Losungsvektor (x1, . . . , xn) muss also ganzzahlig sein.

FG KTuEA, TU Ilmenau Effiziente Algorithmen – Sommersemester 2012 44

Das Rucksackproblem Mit Wiederholungen

Das Rucksackproblem mit Wiederholungen


Aufgabe: Wahle x1, . . . , xn ∈ N mit∑1≤i≤n

xiai ≤ b,

∑1≤i≤n

xici moglichst groß.



Ansatz: Dynamische Programmierung.

Identifizierung von nutzlichen Teilproblemen:

Fur d = 0, . . . , b sei w(d) := maximaler erreichbarer Nutzenwert furVolumen a1, . . . , an, Nutzenwerte c1, . . . , cn, und Rucksackgroße d .

Klar: w(0) = 0.

Bellman’sche Optimalitatsgleichungen:

w(d) =

{0, d = 0

max ({ci + w(d − ai ) | 1 ≤ i ≤ n, ai ≤ d} ∪ {0}) , sonst.

Laufzeit: O(n · b). (Fur jedes d , 1 ≤ d ≤ b, muss ein Maximumuber ≤ n + 1 Werte gebildet werden.)



Interessant: Wie berechnet man den Losungsvektor x1, . . . , xn?

Dafur legen wir ein Array I [0..b] an.

I [d ] gibt ein i ∈ {1, . . . , n} an, welches ci + w(d − ai ) maximiert. (Wennkein solches Objekt existiert, setzen wir I [d ]← 0.)

Wir nutzen den folgenden Algorithmus zur Berechnung desLosungsvektors:

1 Initialisiere ein Array X [1..n] mit 0’en

2 d := b

3 while d > 0 do

4 X [I [d ]]++

5 d := d − aI [d ]

Ausgabe: X [1..n].



Beispiel:

b = 10:i 1 2 3 4ai 6 3 4 2ci 30 14 16 9

d 0 1 2 3 4 5 6 7 8 9 10w(d) 0 0 9 14 18 23 30 32 39 44 48I [d ] 0 0 4 2 4 2 1 2 1 1 4

Rekonstruierte Bepackung: x1 = 1, x2 = 0, x3 = 0, x4 = 2.



Resultat

Satz 5.4.1

Das Rucksackproblem mit Wiederholungen (mit Ausgabe einer optimalenLosung) ist in Zeit O(n · b) und Platz O(b) losbar.


Das Rucksackproblem 0-1-Variante

Das 0-1-Rucksackproblem


Ausgabe: I ⊆ {1, . . . , n} derart, dass∑

i∈I ai ≤ b und∑

i∈I ci moglichstgroß.



Ansatz: Dynamische Programmierung.

Identifizierung von nutzlichen Teilproblemen:

Fur 1 ≤ k ≤ n und 0 ≤ v ≤ b definieren wir

m(k , v) := max{∑

i∈Ici | I ⊆ {1, . . . , k} ∧

∑i∈I

ai ≤ v}.

Das Teilproblem P(k, v) besteht darin, ein I ⊆ {1, . . . , k} mit∑

i∈I ai ≤ vzu finden, das

∑i∈I ci maximiert.

Wir suchen also nach einer Auswahl, die nur Objekte Nummer 1, . . . , kbenutzt, eine modifizierte Gewichtsschranke v einhalt, und den Nutzenmaximiert.

Trivial: m(0, v) = 0 fur alle v .

P(n, b) ist das Gesamtproblem.



Eigenschaft”

Optimale Substruktur“:

Sei I optimale Losung fur P(k , v), d. h.:

m(k , v) =∑

i∈I ci , I ⊆ {1, . . . , k},∑

i∈I ai ≤ v .

Dann tritt einer der folgenden Falle ein.

1. Fall: k ∈ I . – Dann ist I − {k} optimale Losung furP(k − 1, v − ak), d. h.:

m(k , v)− ck =∑

i∈I−{k}

ci = m(k − 1, v − ak).

2. Fall: k 6∈ I . – Dann ist I optimale Losung fur P(k − 1, v),d. h.:

m(k , v) = m(k − 1, v).



Beweis: Indirekt.

1. Fall: k ∈ I . – Annahme: I − {k} nicht optimal fur P(k − 1, v − ak).Dann gabe es eine bessere Teilmenge J ⊆ {1, . . . , k − 1} mit∑

i∈J ai ≤ v − ak und∑

i∈J ci >∑

i∈I−{k} ci .Dann ware aber J ∪ {k} eine bessere Losung fur P(k , v) als I ,Widerspruch.

2. Fall: k 6∈ I . – Annahme: I nicht optimal fur P(k − 1, v).Dann gabe es eine bessere Teilmenge J ⊆ {1, . . . , k − 1}. Dann ware aberJ auch besser als I fur P(k , v), Widerspruch.



Die optimale Losung fur P(k , v) enthalt also eine optimale Losung furP(k − 1, v ′) fur ein v ′ ≤ v .

Eigenschaft”

Optimale Substruktur“!

Bellman’sche Optimalitatsgleichungen:

m(k , v) =

m(k − 1, v − ak) + ck , falls v ≥ ak und diese Summe

großer als m(k − 1, v) ist;∗

m(k − 1, v), sonst.

fur 1 ≤ k ≤ n, 0 ≤ v ≤ b;

m(0, v) = 0, fur 0 ≤ v ≤ b.

∗ In diesem Fall ist k Element jeder optimalen Losung von P(k, v).

Wir berechnen alle m(k, v) mittels einer iterativen Prozedur.



5.4.2 Algorithmus DP-Zero-One-Knapsack(a1, . . . , an, c1, . . . , cn, b)Eingabe: a1, . . . , an: Volumina; c1, . . . , cn: Nutzenwerte; b: SchrankeAusgabe: I ⊆ {1, . . . , n}: Optimale legale Auswahl.Datenstrukturen: m[0..n,0..b]: integer;(1) for v from 0 to b do m[0,v] ← 0;(2) for k from 1 to n do(3) for v from 0 to b do(4) if v − ak ≥ 0(5) then s ← m[k−1,v−ak] + ck else s ← 0;(6) if s > m[k−1,v](7) then m[k,v] ← s;(8) else m[k,v] ← m[k−1,v];

(∗ Konstruktion der optimalen Menge: ∗)(9) I ← ∅; r ← m[n,b];(10) for k from n downto 1 do(11) if m[k−1,r−ak] + ck > m[k−1,r](12) then r ← r− ak; I ← I ∪ {k};(13) return I.



Korrektheit des ermittelten Wertes m[n,b] ergibt sich aus denBellman’schen Optimalitatsgleichungen durch Induktion uber k .

Korrektheit der ausgegebenen Menge I folgt aus der obigen Uberlegung,dass die Bedingung

m(k − 1, v − ak) + ck > m(k − 1, v)

entscheidend ist fur die Frage, ob k in der optimalen Losung von P(k, v)enthalten ist oder nicht, und mit Induktion.

Laufzeit des Algorithmus: O(n · b).



Beispiel:

b = 6:i 1 2 3 4

ai 3 4 2 1

ci 4 6 2 5

m[k , v ]:v : 0 1 2 3 4 5 6

k = 0 0 0 0 0 0 0 0

1 0 0 0 4 4 4 4

2 0 0 0 4 6 6 6

3 0 0 2 4 6 6 8

4 0 5 5 7 9 11 11



Ablesen von I aus dem Array m[0..n,0..b]:

Benutze m(k − 1, v − ak) + ck > m[k − 1, v ] als Kriterium.

(Eingerahmte Eintrage der Tabelle.)

m[4, 6] = 11 > 8 = m[3, 6],also I := {4}, v := 6 - 1 = 5

m[3, 5] = 6 6> 6 = m[2, 5],m[2, 5] = 6 > 4 = m[1, 5],

also I := I ∪ {2}, v := 5 - 4 = 1

m[1, 1] = 0 6> 0 = m[0, 1].

Resultat: Optimale Menge ist I = {2, 4}.



Man kann auf die Speicherung des gesamten Arrays m verzichten.

Man halt immer nur die letzte Zeile, und aktualisiert die Eintrage vonrechts nach links.(Rechts vom Arbeitspunkt v : Eintrage m(k, v ′), links davon: Eintragem(k − 1, v ′).)

Eine Bitmatrix b[1..n,0..b] fuhrt mit, ob Objekt k fur eine optimaleBepackung notwendig ist oder nicht.



5.4.3 Algorithmus DP-Zero-One-Knapsack(a1, . . . , an, c1, . . . , cn, b)Eingabe: a1, . . . , an: Volumina; c1, . . . , cn: Nutzenwerte; b: SchrankeAusgabe: I ⊆ {1, . . . , n}: Optimale legale Auswahl.Datenstrukturen: m[0..b]: integer; b[1..n,0..b]: Boolean;(1) for v from 0 to b do m[v] ← 0;(2) for k from 1 to n do(3) for v from b downto 0 do(4) if v − ak ≥ 0 then s ← m[v−ak] + ck else s ← 0;(5) if s > m[v]

(6) then m[v] ← s; b[k,v] ← 1;(7) else b[k,v] ← 0;

(∗ Konstruktion der optimalen Menge: ∗)(8) I ← ∅; r ← m[b];(9) for k from n downto 1 do(10) if b[k,r] = 1 then(11) r ← r−ak; I ← I ∪ {k};(12) return I.



Resultat

Satz 5.4.4

Das 0-1-Rucksackproblem (mit Ausgabe der optimalen Losung) ist in ZeitO(nb) losbar.



Wie gut sind diese beiden Algorithmen?

Die Große, nicht die Bitlange der Gewichtsschranke b geht in dieLaufzeit ein.

Wir nennen Algorithmen mit einer Laufzeit O(p(n,B)), wo n die(strukturelle) Große der Eingabe und B eine obere Schranke fur einigeoder alle Zahlenkomponenten der Eingabe, und p ein Polynom in zweiVariablen ist, pseudopolynomiell.

Die Existenz eines pseudopolynomiellen Algorithmus fur dasRucksackproblem widerspricht nicht der Tatsache, dass das0-1-Rucksackproblem wahrscheinlich keinen Polynomialzeitalgorithmus hat(nachstes Semester: NP-Vollstandigkeit!): Die naturliche Eingabegroßeberucksichtigt log b und nicht b.


TSP

5.5. Traveling Salesperson1

Eingabe: Vollstandiger, gerichteter Graph mit Kantengewichten ai ,j ≥ 0.(Also eine Matrix ((ai ,j))1≤i ,j≤n.)

Gesucht: Eine gunstigste”Rundreise“, bei der jede Stadt (also jeder

Knoten) genau einmal besucht wird und zum Startpunkt zuruckgekehrtwird.

Formal: Gesucht ist eine Permutation π von {1, . . . , n}, so dass

c(π) =∑

2≤i≤naπ(i−1),π(i) + aπ(n),π(1)

minimal unter allen moglichen Permutationen.

1Das Problem, was ihr beim Sommerfest 2012 losen solltet!


TSP

Ein Beispiel

A B

C D

E

2

2

1

4

32

3

2

24

Kurzeste Tour: (A,B,E ,C ,D,A) mit Lange 10.


TSP

Klar: Wir konnen den Anfangspunkt fest wahlen. (Hier: Tour startet imKnoten 1.)

Naiver Ansatz: Probiere alle (n − 1)! mogliche Rundtouren aus.

Wir entwickeln einen sehr viel besseren Algorithmus, basierend auf

”Dynamischer Programmierung“.


TSP

Zentrale Frage: Wie sehen sinnvolle Teilprobleme aus?

Wir betrachten P(S , `) mit S ⊆ {1, . . . , n}, 1 ≤ ` ≤ n, wobei 1, ` ∈ S .

P(S , `) fragt nach dem kurzesten, einfachen Weg von 1 durch alleKnoten in S mit Ende `.

Basisfalle: P({1}, 1) = 0,P(S , 1) =∞ fur |S | > 1.

Am Ende: Lange einer kurzesten Rundtour:

min(P({1, . . . , n}, `) + a`,1 | 1 ≤ ` ≤ n).


TSP

Fur |S | > 1 gilt:

P(S , j) = min(P(S − {j}, i) + ai ,j | i ∈ S − {j}).

Iterativ programmiert sieht der Algorithmus wie folgt aus:

1 P({1}, 1)← 0

2 for s ← 2 to n do

3 foreach S ⊆ {1, 2, . . . , n} with |S | = s and 1 ∈ S do

4 P(S , 1)←∞5 foreach j ∈ S , j 6= 1 do

6 P(S , j)← min(P(S − {j}, i) + ai ,j | i ∈ S − {j}).

7 return min(P({1, . . . , n}, `) + a`,1 | 1 ≤ ` ≤ n)


TSP

ResultatSatz 5.5.1

Das Problem Traveling Salesperson kann mittels dynamischerProgrammierung in Zeit O(2n · n2) gelost werden.

(Dies ist eine wesentliche Verbesserung gegenuber dem naiven Ansatz mitLaufzeit O(n!).)

Beweis

Die Anzahl aller Teilmengen von {1, . . . , n} ist 2n.

Zu jeder solcher Teilmenge gibt es maximal n Teilprobleme.

Jedes Teilproblem kann in Zeit O(n) gelost werden.

Fur Zuhause: Wie konstruiert man eine optimale Rundtour (also dieKnotenfolge)?


Matrixkettenmultiplikation

Das folgende Problem wurde in der Vorlesung nicht besprochen und istdeswegen nicht prufungsrelevant. Es stellt jedoch ein weiteres schonesBeispiel fur einen auf dem Paradigma

”Dynamische Programmierung“

basierenden Algorithmus dar.



5.6 Optimale Matrizenmultiplikation

Sei A1 = (αij)1≤i≤r0,1≤j≤r1 eine r0 × r1-Matrix, A2 = (βjk)1≤j≤r1,1≤k≤r2

eine r1 × r2-Matrix.

Berechne Produkt A1 · A2 =: C = (γik)1≤i≤r0,1≤k≤r2 .

Standardmethode (nicht Strassen-Methode o.a.):

γik =∑

1≤j≤r1

αijβjk ,

fur 1 ≤ i ≤ r0, 1 ≤ k ≤ r2. – r0r1r2 Multiplikationen.

”Kosten“: c(r0, r1, r2) := r0r1r2

Gesamtzeit = Θ(r0r1r2).



Gegeben: A1,A2, . . . ,Ak , wobei Ai eine ri−1 × ri -Matrix ist.

Aufgabe

Berechne A1A2 . . .Ak , moglichst kostengunstig.

Die Matrizenmultiplikation ist assoziativ. Bei der Berechnung von A1A2A3

entstehen Kosten von

Kosten r0r1r2 + r0r2r3 bei der Reihenfolge (A1A2)A3 undKosten r0r1r3 + r1r2r3 bei der Reihenfolge A1(A2A3).

Beispiel: (r0, r1, r2, r3) = (5, 10, 3, 10):Kosten 300 bei der ersten Reihenfolge, 800 bei der zweiten.



Problem:

Eingabe: Dimensionen r0 × r1, r1 × r2, . . ., rk−1 × rk von MatrizenA1, . . . ,Ak .Ausgabe: Eine (

”optimale“) Klammerung, die bei der Berechnung von

A1 · · ·Ak die Gesamtkosten (Anzahl aller Multiplikationen von Zahlen)minimiert.

Seien c(r0, . . . , rk) die Kosten bei optimaler Klammerung, wobei k ≥ 2und r0, r1, . . . , rk ≥ 1 beliebige ganze Zahlen sind.

Fur k = 1 setzen wir c(r0, r1) := 0 fur alle r0, r1.

Klar: c(r0, r1, r2) = r0r1r2.



Die optimale Losung des Klammerungsproblems hat die Form

(A1 · · ·A`)︸︷︷︸irgendwie

geklammert

(A`+1 · · ·Ak)︸︷︷︸irgendwie

geklammert

fur ein 1 ≤ ` < k (das wir nicht kennen!).

Zentrale Beobachtung (”

Optimale Substruktur“):

Die Klammerungen in den Teilen A1 · · ·A` bzw. A`+1 · · ·Ak mussenoptimale Kosten fur die Teilprobleme liefern.

Ware z. B. die Teilklammerung von A1 · · ·A` nicht optimal, dann konnteman durch Verbesserung dieses Teils die Gesamtkosten senken.



Aus dieser Beobachtung ergibt sich: Es gibt ein `, 1 ≤ ` < k mit

c(r0, . . . , rk) = c(r0, . . . , r`) + c(r`, . . . , rk) + r0r`rk︸︷︷︸außerste

Matrizenmult.

.

Das `, das die Summe auf der rechten Seite minimiert, ist das richtige.

Mussen: Optimale Klammerungen bzw. ihre Kosten fur die TeilproblemeA1 · · ·A` und A`+1 · · ·Ak berechnen.

Ansatz: Betrachte die Teilprobleme TP(i , j), das TeilproduktAi · · ·Aj , 1 ≤ i ≤ j ≤ n, mit minimalen Kosten zu berechnen.

Parameter zu TP(i , j): ri−1, . . . , rj .



Beobachtung (”

Optimale Substruktur“), angewendet auf dasTeilproblem, liefert:

Rekursionsformel

Basisfall: c(ri−1, ri ) = 0, fur 1 ≤ i ≤ k .

Schrittfall:

c(ri−1, . . . , rj) = mini≤`<j

{c(ri−1, . . . , r`) + c(r`, . . . , rj) + ri−1r`rj},

fur 1 ≤ i < j ≤ k .

”Bellman’sche Optimalitatsgleichungen.“

(Checke diese Gleichung fur j = i + 1!)

Iterative Auflosung der Rekursionsformel!



MatrixOptimal((r0, . . . , rk))Eingabe: Dimensionsvektor (r0, . . . , rk)Ausgabe: Kosten c(r0, . . . , rk) bei der optimalen Klammerung

l[1..k,1..k]: Plan zur Ermittlung der optimalen Unterteilung;Datenstruktur: Matrizen C[1..k,1..k], l[1..k,1..k](1) for i from 1 to k do(2) C[i,i] ← 0;(3) for i from 1 to k − 1 do(4) C[i,i+1] ← ri−1 · ri · ri+1;(5) for d from 2 to k − 1 do(6) for i from 1 to k − d do(7) bestimme das `, i ≤ ` < i+d,(8) das C = C[i,`] + C[`+ 1,i+d] + ri−1 · r` · ri+d minimiert;(9) l[i,i+d] ← dieses `;(10) C[i,i+d] ← das minimale C ;(11) Ausgabe: C[1..k,1..k] und l[1..k,1..k].



Korrektheit: Man beweist durch Induktion uber d = 0, 1, . . . , k − 1 mitHilfe der Bellman’schen Optimalitatsgleichung, dass C[i,i + d] die Zahlc(ri−1, . . . , ri+d) enthalt.

Ubung: Man zeige, dass mit Hilfe der l[i,j]-Werte die optimaleKlammerung in Linearzeit ermittelt werden kann.

Laufzeit: Die Minimumssuche in Zeile (8) kostet Zeit O(k); (6)–(10) und(5)–(10) ergibt sich eine Laufzeit von Θ(k3).



Beispiel:

(r0, . . . , r4) = (3, 2, 2, 5, 6)

C: l:i 1 2 3 4

1 0 12 42 1082 0 20 803 0 604 0

1 2 3 4

1 * * 2 22 * * 33 * *4 *

Optimale Klammerung: (M1M2)(M3M4).

Kosten: 108 Multiplikationen.


Documents

5.4 Das Rucksackproblem - Startseite TU Ilmenau · Das Rucksackproblem 0-1-Variante Korrektheit des ermittelten Wertes m[n,b] ergibt sich aus den Bellman’schen Optimalit atsgleichungen