20
Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

Embed Size (px)

Citation preview

Page 1: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

Knapsack & Bin Packing

Sebastian StoberArbeitsgruppe 5: Wie genau ist ungefähr?Sommerakademie Görlitz 2007

Page 2: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 2

Page 3: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 3

Knapsack a.k.a. Rucksack – Problem(genauer: 0/1-Knapsack)

Gegeben: Menge S={a1,…,an} von Objekten Größen bzw. Gewichte size(ai)Z+

Nutzen profit(ai)Z+

Kapazität BZ+ des Knapsacks Gesucht:

Teilmenge von S mit Größe beschränkt durch B Maximalem Wert

Page 4: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 4

Knapsack – Komplexität / Greedy

Knapsack ist NP-vollständig Greedy Heuristik:

Sortiere Objekte nach fallendem relativem Nutzen bzgl. Ihrer Größe. (also Nutzen/Größe)

Wähle Objekte in dieser Reihenfolge, bis keines mehr hinein passt.

Kann beliebig schlecht werden. (Bsp.)

Page 5: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 5

Knapsack – Optimalitätsprinzip

Wenn Knapsack der Größe B optimal mit einer Auswahl I S gepackt ist, so gilt für jedes Objekt oI, dass ein (B - size(o))-großer Knapsack optimal mit I/{o} gepackt ist.

Rekursionsvorschrift für optimalen Wert v(i,b) beim Packen eines Knapsacks der Kapazität b ≤ B mit Objekten aus {a1,…,ai} mit i ≤ n:

Optimale Auswahl ergibt sich daraus, welcher Fall bei v(n,B) aufgetreten ist.

sonst

)size(,0

0

)),value())size(,1v(),,1max(v(

),,1v(

,0

),v( i

ii

ahi

i

aabibi

bibi

[ignorieren] [----------- hineinlegen ----------]

Page 6: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 6

Knapsack – Dyn. Programmierung

Iterative Berechnung der v(i,b) und Speicherung in einer Tabellenstruktur (Dynamische Programmierung)

Komplexität: pseudo-polynomiell

)profit(max aPSa

Page 7: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 7

Knapsack – FPTAS

Idee: Verwende nur eine feste Anzahl von Bits (abhängig von ) und ignoriere die unwichtigsten, so dass der gerundete Nutzen polynomiell in n und 1/ ist.

Algorithmus:1. Für geg. > 0 definiere K=P/n

2. Für jedes Objekt ai,definiere Nutzen

3. Finde optimale Menge S‘ unter Verwendung der gerundeten Werte

K

aa i

i

profitprofit'

Page 8: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 8

Knapsack – FPTAS

Relative Approximationsgüte: (1+)

Beweis: Sei S* die optimale Menge Für alle aS unterscheiden sich profit(a) und

Kprofit‘(a) maximal um K, daher: profit(S*) – Kprofit‘(S*) ≤ nK S‘ muss mindestens so gut sein wie S* unter den

modifizierten Profits, da Alg. optimal. Daher profit(S‘) ≥ Kprofit‘(S*) ≥ profit(S*)-nK = OPT-P und da OPT ≥ P folgt: profit(S‘) ≥ (1- )OPT

Komplexität:

n

nOK

PnO 22

Page 9: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 9

Alg. nach Neuhausen & Ullmann

Siehe Tafel…

Page 10: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 10

Alg. nach Neuhausen & Ullmann

Page 11: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

2. Bin Packing

Page 12: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 12

Bin Packing – Problem

Gegeben: n Objekte Größen a1,…,an (0,1]

Gesucht: Aufteilung der Objekte in Behälter

(Einheitsgröße 1) mit minimaler Anzahl der Behälter

Page 13: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 13

Bin Packing – Komplexität

Bin Packing ist NP-vollständig.

Es gibt kein PTAS mit relativer Güte 3/2- für > 0 (vorausgesetzt P≠NP).(Beweis durch Reduktion des Problems Partition, siehe 3. Vortrag)

Page 14: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 14

Bin Packing – First Fit

Lege a1 in Behälter B1

Für jedes weitere Objekt ai, 1<i≤n:

Lege ai in Bi

Relative Güte: 1,7

Modifikation: Decreasing First Fit Sortiere die Objekte nach absteigender

Größe Relative Güte: 11/9

Page 15: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 15

Asymptotisches PTAS (1)

Vereinfachtes Problem: Feste minimale Größe > 0 Feste Anzahl verschiedener Größen KZ+

Kann in P gelöst werden Maximal M=1/ Objekte pro Behälter, daher Typen von Behälter (nach Füllstand)

mögliche Verteilungen

Polynom in n

M

KMR

R

RnP

Page 16: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 16

Asymptotisches PTAS (2.1)

Vereinfachung: Feste minimale Größe > 0 PTAS mit relativer Güte (1+)

Sortiere Objekte nach steigender Größe Bilde K=1/² Gruppen mit max. Q=n²

Objekten Konstruiere J durch Aufrunden:

J hat maximal K verschiedene Objektgrößen

Wende vorigen Alg. an

Page 17: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 17

Asymptotisches PTAS (2.2)

Warum benötigt J max. (1+)OPT Behälter? Konstruiere J‘ durch Abrunden:

J‘ braucht maximal OPT Behälter Verteilung für J‘ funktioniert auf für alle

außer die Q größten Objekte aus J, daherOPT(J) ≤ OPT(J‘)+Q ≤ OPT+Q

OPT ≥ n (da minimale Objektgröße nach Vorraussetzung)

Daher Q = n² ≤ OPT Und daher: OPT(J) ≤ (1+)OPT

Page 18: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 18

Asymptotisches PTAS (3)

gegeben: Probleminstanz I

1. Entferne Objekte der Größe modifizierte Probleminstanz I‘

2. Aufrunden, um konstante Anzahl der Objektgrößen zu erhalten

3. Optimale Verteilung berechnen4. Verteilung für ursprüngliche Objekte

verwendenmaximal (1+ )OPT(I‘) Behälter

5. Objekte, die kleiner als sind, mit First Fit verteilen

Page 19: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 19

Asymptotisches PTAS (4)

a) Es werden keine weiteren Behälter benötigt.

b) M sei tatsächliche Anzahle der benötigten Behälter

Alle außer der letzte Behälter sind mindestens zu 1- gefüllt

(M-1)(1-) ≤ Masse aller Objekte ≤ OPT daher:

und mit 0 < ≤ 1/2 : M ≤ (1+2)OPT+1

1)1(

OPT

M

Page 20: Knapsack & Bin Packing Sebastian Stober Arbeitsgruppe 5: Wie genau ist ungefähr? Sommerakademie Görlitz 2007

10.9.2007 Sebastian Stober - Knapsack & Bin Packing 20

Bin Packing - Zusammenfassung

Bin Packing ist NP-vollständig. Es gibt kein PTAS mit relativer Güte

3/2- für > 0 (vorausgesetzt P≠NP). First Fit: 1,7 OPT Decreasing First Fit: 11/9 OPT Asymptotisches PTAS für 0 < ≤ 1/2

mit (1+2)OPT+1