1 Einleitung Algorithmik - tcs.uni-luebeck.de · AndreasJakoby UniversitätzuL übeck AlgorithmikWS07/08 1. Vorlesung,24.10.2006 Scheinvergabe: UmeinenScheinfürdieseVorlesungzuerhalten,istdieerfolgreiche

Andreas Jakoby

Universitat zu Lubeck

Algorithmik WS 07/08

1. Vorlesung, 24.10.2006

Algorithmik

Andreas Jakoby

[email protected]: Mittwochs 15:00-17:00

WS 07/08

1

Andreas Jakoby



1. Vorlesung, 24.10.2006

1 Einleitung

Motivation

Eine wesentliche Aufgabe der Informatik ist die Analyse vonProblemen mit der Zielsetzung eine effiziente algorithmische Losungfur diese Probleme zu entwickeln.

Die erreichbare Effizienz einer algorithmischen Losung hangt oft vomTyp des Problems ab. Fur manche Probleme konnen wir nichterwarten eine effiziente Losung zu finden.

Manche Probleme erlauben es uns auf einige Entwurfsmethoden furAlgorithmen zuruckzugreifen.

2

Andreas Jakoby



1. Vorlesung, 24.10.2006

Entwurfsmethoden fur Algorithmen

In der Informatik wurden eine Reihe von Entwurfsmethoden furAlgorithmen entwickelt. Auf einige dieser Methoden werden wir indieser Vorlesung eingehen.

Divide and Conquer Dynamisches Programmieren Greedy-Algorithmen Backtracking Lineares Programmieren Transformationen

3

Andreas Jakoby



1. Vorlesung, 24.10.2006

Ziele der Vorlesung:

zentrale Entwurfsmethoden fur Algorithmen

Analysemethoden fur Algorithmen und fur algorithmischeProblemstellungen

wichtige Optimierungsalgorithmen

4

Andreas Jakoby



1. Vorlesung, 24.10.2006

Scheinvergabe:

Um einen Schein fur diese Vorlesung zu erhalten, ist die erfolgreicheTeilnahme an der abschließenden Prufung erforderlich.

Um zur Prufung zugelassen zu werden, ist eine erfolgreicheTeilnahme an den Ubungen erforderlich. Die Kriterien fur eineerfolgreiche Ubungsteilnahme sind:

1. alle bis auf maximal zwei Ubungsblatter wurden erfolgreichbearbeitet — ein Ubungsblatt gilt als erfolgreich bearbeitet,wenn auf diesem Blatt mindestens 50% der Punkte erreichtwurden und diese Losungen auch von dem Studierendenvorgetragen werden konnen —

2. und die Programmieraufgabe wurde erfolgreich bearbeitet.

5

Andreas Jakoby



1. Vorlesung, 24.10.2006

2 Divide and ConquerBeispiele fur Divide and Conquer Algorithmen:

Sortierverfahren wie Merge-Sort, Quicksort

Turme von Hanoi

Matrizenmultiplikation, Multiplikation großer Zahlen

Geometrische Probleme: Closest Pair,Liniensegment-Schnittproblem, Voronoi-Diagramme

6

Andreas Jakoby



1. Vorlesung, 24.10.2006

2.1 Das Divide and Conquer Prinzip

Problemunabhangige Formulierung des Divide and Conquer Verfahrenszur Losung eines Problems der Große n:

1. Divide: Teile das Problem in k Teilprobleme, wenn n > c ist; sonstlose das Problem der Große ≤ c direkt.

2. Conquer: Lose die Teilproblem (rekursiv) auf dieselbe Art.

3. Merge: Fuge die Teillosungen zur Gesamtlosung zusammen.

7

Andreas Jakoby



1. Vorlesung, 24.10.2006

Anmerkungen:

c ist oft eine kleine Konstante, z.B. c = 1 oder c = 2.

Die Teilprobleme ist oft disjunkt. Dieses muss jedoch nicht immergelten.

Oft bleiben beim Divide and Conquer kleine Restprobleme ubrig, dienicht vom Typ des ursprunglichen Problems sind. Diese werden imMerge-Schritt direkt gelost.

8

Andreas Jakoby



1. Vorlesung, 24.10.2006

Laufzeit des Divide and Conquer Verfahrens ist

T (n) =

a fur n ≤ c

T (n1) + . . . + T (nk) + tmerge(n1, . . . , nk) sonst,

wobei n1, . . . , nk die Großen der Teilprobleme sind.In vielen Fallen teilen wir ein Problem in zwei Teilprobleme der Große n

2und der Merge-Schritt hat oft eine lineare Laufzeit, dann gilt

T (n) =

1 fur n ≤ 12T (n/2) + O(n) fur n ≥ 2 .

Diese Rekursionsformel hat die Losung

T (n) = O(n log n)1 .

1Im Allgemeinen bezeichnen wir mit log den Logarithmus zur Basis 2

9

Andreas Jakoby



1. Vorlesung, 24.10.2006

2.2 Beispiel: Voronoi-Diagramme

Definition 1: Gegeben ist eine Menge von Punkten S in der Ebene. EinVoronoi-Diagramm VD(S) von S ist eine Einteilung der Ebene in konvexeRegionen, so dass

in jeder Region exakt ein Punkt aus S liegt und

die zu p ∈ S gehorige Region alle Punkte umfaßt, die naher an p alsan jedem anderen Punkt von S liegen.

10

Andreas Jakoby



1. Vorlesung, 24.10.2006

Algorithmus Voronoi-Diagramme(S)Eingabe: Punktmenge S in der EbeneErgebnis: Voronoi-Diagramm von S

1: if |S | = 1 then2: VD(S) besteht aus einer Region, die die ganze Ebene umfaßt3: else4: Teile S anhand der x-Koordinate in zwei Halften Sl und Sr

5: VD(Sl) := Voronoi-Diagramme(Sl)6: VD(Sr ) := Voronoi-Diagramme(Sr )7: VD(S) := VD-Merge(VD(Sl),VD(Sr ))8: end if9: Return(VD(S))

11

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 1:Eingabe: 10 Punkten S in der Ebene.

12

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 1:Divide: Teile S in Sl und Sr .

12

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 1:Conquer: Bestimme das Voronoi-Diagramme fur Sl .

12

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 1:Conquer: Bestimme das Voronoi-Diagramme fur Sr .

12

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 1:Merge: Vereine die beiden Teillosungen.

12

Andreas Jakoby



1. Vorlesung, 24.10.2006

Anmerkungen:

Sortieren wir zunachst die initiale Eingabemenge bezuglich derKoordinaten (x , y), so konnen wir einen Aufteilung von S in jedemRekursionsschritt bezuglich einer (fast) vertikalen Linie in ZeitO(|S |) finden.

Wir betrachten hier nicht den konkreten Algorithmus und diekonkrete Datenstruktur. Die Aufteilung und das Vereinigen istjedoch in linearer Zeit moglich.

Ein Voronoi-Diagramm fur eine Menge S mit n Punkten kann somitin Zeit O(n log n) konstruiert werden.

Wir wollen nun noch auf die Idee fur ein Merge-Verfahren eingehen.

13

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Seien pl ∈ Sl und pr ∈ Sr die beiden Punkte mit maximaler y -Koordinate.

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Von y = +∞ bis zum ersten Schnittpunkt mit einer Grenzlinie aus VD(Sl)oder aus VD(Sr ) folge der Mittelsenkrechten der Verbindungslinie von pl

und pr .

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Ist die Schnittpunkt mit einer Grenzlinie von VD(Sl) so ersetzte pl durchden Punkt aus Sl , der unterhalb der geschnittenen Grenzlinie liegt.

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Ist die Schnittpunkt mit einer Grenzlinie von VD(Sr ) so ersetzte pr durchden Punkt aus Sr , der unterhalb der geschnittenen Grenzlinie liegt.

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Von dem letzten Schnittpunkt bis zum ersten Schnittpunkt mit einer Grenz-linie aus VD(Sl) oder aus VD(Sr ) folge der Mittelsenkrechten der Verbin-dungslinie von pl und pr .

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Von dem letzten Schnittpunkt bis zum ersten Schnittpunkt mit einer Grenz-linie aus VD(Sl) oder aus VD(Sr ) folge der Mittelsenkrechten der Verbin-dungslinie von pl und pr .

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:und so weiter und so weiter

14

Andreas Jakoby



1. Vorlesung, 24.10.2006


14

Andreas Jakoby



1. Vorlesung, 24.10.2006


14

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel Teil 2:Im Bereich der oberen neuen Grenzlinie kann es zu Fehlern kommen, dahersollten wir fur diesen Bereich das Verfahren noch einmal von unten nachoben durchlaufen.

14

Andreas Jakoby



1. Vorlesung, 24.10.2006

3 Dynamisches Programmieren Beim Dynamischen Programmieren handelt es sich um einen

rekursiven Ansatz, bei dem wir versuchen ahnlich wie beim Divideund Conquer ein Problem mit Hilfe kleinerer Probleminstanzen zulosen.

Da verschiedene kleinere Probleminstanzen mehrere male auftretenkonnen speichern wir die entsprechenden Losungen so lange bis sienicht mehr benotigt wird.

Fur viele Anwendungen ist es nicht moglich eine einfache Aufteilungeines Problems in kleinere (disjunkte) Teilprobleme zu finden. Beimdynamischen Programmieren, betrachten wir daher eine Folge vonmoglichen Aufteilungen und optimieren uber diese Moglichkeiten.

15

Andreas Jakoby



1. Vorlesung, 24.10.2006

3.1 Die Schritte des Dynamischen Programmierens

Problemunabhangig konnen wir die folgenden Schritte fur das dynamischeProgrammieren zur Losung eines Problems der Große n formulieren:

1. DPR 1: Beschreibe das Problem rekursiv.

2. DPR 2: Bestimme die Menge R der kleineren Probleme, auf die beider Losung eines Problems P direkt oder indirekt rekurriert wird.

3. DPR 3: Bestimme eine Aufrufreihenfolge P1, . . . ,Pr der Probleme inR, so dass bei der Losung eines Problems Pi nur Probleme Pj mitj < i benutzt werden.

4. DPR 4: Berechne und Speichere die sukzessive die Losungen furP1, . . . ,Pr in dieser Reihenfolge, wobei einmal berechnete Losungenmindestens solange gespeichert werden, wie bei spater zuberechnenden Problemen noch direkt auf sie zuruckgegriffen werdenmuss.

16

Andreas Jakoby



1. Vorlesung, 24.10.2006

3.2 Beispiele

Beispiel 1: Fibonacci-Zahlen

DPR 1:

fib(n) =

1 fur n ∈ 1, 2fib(n − 1) + fib(n − 2) fur n > 2 .

DPR 2:R = fib(1), fib(2), . . . , fib(n − 1) .

DPR 3:fib(1), fib(2), . . . , fib(n − 1) .

DPR 4: Berechne fib(1), fib(2), . . . , fib(n) nach der Formel unterDPR 1 und speichere fib(i) bis fib(i + 2) berechnet wurde.

17

Andreas Jakoby



1. Vorlesung, 24.10.2006

Algorithmus Fibonacci(n)Eingabe: n ∈ N

Ergebnis: fib(n)

1: for i = 1 to n by +1 do2: if n = 1 then3: alt:= 0; neu:= 14: else5: tmp:=alt+neu6: alt:=neu; neu:=tmp7: end if8: end for9: Return(neu)

18

Andreas Jakoby



1. Vorlesung, 24.10.2006

Beispiel 2: Editierdistanz

Definition 2: Sei x = x [1]x [2] . . . x [k] = x [1..k] ∈ Σk eine Zeichenketteder Lange k und a ∈ Σ, wir definieren die Operationen

del(x , i) := x [1] . . . x [i − 1]x [i + 1] . . . x [k]

add(x , i , a) := x [1] . . . x [i ]ax [i + 1] . . . x [k]

change(x , i , a) := x [1] . . . x [i − 1]ax [i + 1] . . . x [k]

Die Editierdistanz EdDist(x , y) von x , y ∈ Σ∗ ist die minimale Anzahl derobigen Operationen, die notig sind, um aus der Zeichenkette x in dieZeichenkette y zu uberfuhren.

19

Andreas Jakoby



1. Vorlesung, 24.10.2006

Fur DPR 1 unterscheiden wir die folgenden Falle:

Fall 1 EdDist(x [1..k], y [1..m]) =EdDist(x [1..k], y [1..m − 1]) + 1

Fall 2 EdDist(x [1..k], y [1..m]) =EdDist(x [1..k − 1], y [1..m]) + 1

Fall 3a EdDist(x [1..k], y [1..m]) =EdDist(x [1..k−1], y [1..m−1])+1wenn x [k] 6= y [m] ist

Fall 3b EdDist(x [1..k], y [1..m]) =EdDist(x [1..k − 1], y [1..m − 1])wenn x [k] = y [m] ist

Ferner gilt:

Fall 4 EdDist(x [1..k], λ) = k

Fall 5 EdDist(λ, y [1..m]) = m

Fall 6 EdDist(λ, λ) = 0

20

Andreas Jakoby



1. Vorlesung, 24.10.2006

DPR 2

R = EdDist(x [1..i ], y [1..j ]) | i ≤ k und j ≤ m und i+j 6= k+m DPR 3

EdDist(x [1..0], y [1..0]), . . . ,EdDist(x [1..k], y [1..0]), . . . ,EdDist(x [1..0], y [1..m]), . . . ,EdDist(x [1..k], y [1..m])

DPR 4fur x [k] = y [m]

EdDist(x [1..k], y [1..m]) = minEdDist(x [1..k], y [1..m − 1]) + 1,EdDist(x [1..k − 1], y [1..m]) + 1,EdDist(x [1..k − 1], y [1..m − 1])

und fur x [k] 6= y [m]

EdDist(x [1..k], y [1..m]) = 1 + minEdDist(x [1..k], y [1..m − 1]),EdDist(x [1..k − 1], y [1..m]),

EdDist(x [1..k − 1], y [1..m − 1]) .

21

Andreas Jakoby



1. Vorlesung, 24.10.2006

Algorithmus Editierdistanz(x , y)Eingabe: x = x [1] . . . x [k], y = y [1] . . . y [m] ∈ Σ∗

Ergebnis: Editierdistanz EdDist(x , y) ∈ N

1: for i = 0 to k by +1 do2: for j = 0 to m by +1 do3: if i = 0 then4: EdDist(x [1..i ], y [1..j ]) := j

5: else if j = 0 then6: EdDist(x [1..i ], y [1..j ]) := i

7: else8: A:= 1 + minEdDist(x [1..i ], y [1..j − 1]),EdDist(x [1..j − 1], y [1..i ])9: B:= EdDist(x [1..i − 1], y [1..j − 1])10: if x [i ] 6= y [j ] then B := B + 1 end if11: EdDist(x [1..i ], y [1..j ]) := minA, B12: end if13: end for14: end for15: Return(EdDist(x , y))

22

Andreas Jakoby



1. Vorlesung, 24.10.2006

λ n na nat natu natur naturaλ 0 1 2 3 4 5 6p 1 1 2 3 4 5 6pl 2 2 2 3 4 5 6pla 3 3 2 3 4 5 5plas 4 4 3 3 4 5 6plast 5 5 4 3 4 5 6plasti 6 6 5 4 4 5 6plastik 7 7 6 5 5 5 6

23

Andreas Jakoby



2. Vorlesung, 31.10.2007

4 Greedy-Algorithmen (gierige Algorithmen) Greedy-Algorithmen werden oft fur die exakte oder approximative

Losung von Optimierungsproblemen verwendet.

Typischerweise konstruiert ein Greedy-Algorithmus eine LosungKomponente fur Komponente, wobei der Wert einer einmalgesetzten Komponente nie zuruckgenommen wird.

Beispiele: die Algorithmus von Kruskal, die Konstruktion einesHuffman-Codes und der Approximationsalgorithmus fur dasBinpacking Problem Best-Fit.

24

Andreas Jakoby



2. Vorlesung, 31.10.2007

Philosophie von Greedy-Verfahren

Iterative Konstruktion einer Losung unter Verwendung lokalerOptimalitatskriterien.

Hoffnung: Lokale Optimalitat fuhrt auch zur globalen Optimalitat —oder zumindest zu einer guten Approximation.

Verschiedene lokale Kriterien fuhren zu verschiedenen Algorithmen.

Analysemethoden fur Greedy-Verfahren

Um zu zeigen, dass ein Greedy-Verfahren eine optimale Losung findet,werden im wesentlichen zwei Analysemethoden eingesetzt:

1. the greedy algorithm stays ahead: In jedem Schritt ist die gefundenepartielle Losung des Greedy-Verfahrens mindestens so gut wie jedeandere partielle Losung.

2. exchange argument: Jede Losung kann Schrittweise in die Losungdes Greedy-Verfahrens transformiert werden, ohne dass hierbei dieGute der Losung abnimmt.

25

Andreas Jakoby



2. Vorlesung, 31.10.2007

4.1 Minimale Spannbaume

Gegeben ist ein ungerichteter, zusammenhangender, gewichteterGraph G = (V ,E ) mit einer positiven Kostenfunktion f : E → R+.

Wir nehmen an, dass fur alle Kanten e ∈ E f (e) > 0 ist.

Wir nennen T = (V ′, E ′) einen Spannbaum von G , wenn V = V ′

und T ein Baum ist.

Gesucht ist ein Baum T = (V ,E ′) mit E ′ ⊆ E , so dass,∑

e∈E ′ f (e)minimal unter allen Spannbaumen von G ist.

Ist f (e) konstant 1, so konnen wir dieses Problem wieder mit Hilfeder Breiten- oder Tiefensuche losen.

Wir werden im Folgenden das Verfahren von Kruskal vorstellen.

26

Andreas Jakoby



2. Vorlesung, 31.10.2007

Zur effizienten Implementation benutzen wir die Datenstruktur derPriorityqueue und der Partition. Die letztere Datenstruktur ist auchunter dem Namen UNION/FIND-Datenstruktur bekannt.

Wir starten mit |V | einelementigen Mengen, von denen jede einenanderen Knoten des Graphen enthalt.

Diese Mengen werden als Baume mit jeweils einem Knoteninterpretiert.

Sukzessive verschmelzen wir diese Mengen durch Hinzunahme einerKante mit minimalen Kosten: Finde die minimale Kante, die zweiKnoten aus unterschiedlichen Mengen verbindet und vereinige diebeiden Mengen.

27

Andreas Jakoby



2. Vorlesung, 31.10.2007

Was ist eine Priorityqueue?

Wir betrachten eine Teilmenge M eines Universums U, wobei jedemElement m ∈ M eine Prioritat p(m) (oder kurz p) zugeordnet wird.

insert(m, p): fugt m ∈ U mit Prioritat p in M ein.

deletemin: gibt das Element aus M mit minimaler Prioritat zuruckund entfernt dieses aus M.

readmin: gibt das Element aus M mit minimaler Prioritat zuruckohne es zu entfernen.

decpriority(m, d): die Prioritat von m in M wird um d reduziert.

Eine Priorityqueue kann mit Hilfe eines Heaps (Heapsort) soimplementiert werden, dass die Laufzeiten der Initialisierung in O(|M|),von readmin in O(1) und der drei verbleibenden Operationen inO(log |M|) liegen.

28

Andreas Jakoby



2. Vorlesung, 31.10.2007

Was ist eine UNION/FIND-Datenstruktur bzw. eine Partition?

Partitionen stellen eine eingeschrankte Form von Mengen dar.

Der abstrakten Datentyp ist wie folgt definiert: U = 1, . . . , n sei ein Universum. P = P1, . . . , Pk sei eine Menge von disjunkten, nicht leeren

Teilmengen von U mit U =Sn

i=1 Pi . Wir nennen diese TeilmengenPartitionsblocke oder kurz Blocke.

Jedem Partitionsblock Pi wird ein Element ni ∈ Pi als Reprasentant(bzw. als Name) zugeordnet.

Auf P sind die folgenden zwei Prozeduren definiert: Sei x ∈ U undni , nj Reprasentanten zweier Partitionsblocke Pi und Pj .

find(x) liefert den Reprasentanten ni der Menge Pi mit x ∈ Pi . union(ni , nj ) vereinigt die Blocke mit den Reprasentanten ni und nj .

Diese Operation verandert die Menge P, d.h.P = (P \ Pi , Pj) ∪ Pi ∪ Pj. Der Reprasentant der neuen Mengeist entweder ni oder nj .

29

Andreas Jakoby



2. Vorlesung, 31.10.2007

Die UNION/FIND-Datenstruktur kann recht einfach so implementiertwerden, dass

die Initialisierung in Zeit O(|U|), jede union-Operation in konstanter Zeit und

jede find-Operation in Zeit O(log2 |U|)ausgefuhrt werden kann. Einige aufwendigere Implementierungenerlauben es die Laufzeit der find-Operation erheblich zu reduzieren.

30

Andreas Jakoby



2. Vorlesung, 31.10.2007

Algorithmus MST-Kruskal()Eingabe: global gegebener Graph G

Ergebnis: minimaler Spannbaum T = (V , E ′)

1: Bilde die Priorityqueue Q aller e ∈ E mit Prioritaten f (e).2: Initialisiere die Partitionen v fur alle v ∈ V .3: E ′ := ∅, k = |V |4: while k > 1 do5: v ,w := deletemin(Q); v0 := find(v); w0 := find(w);6: if v0 6= w0 then7: union(v0,w0); E ′ := E ′ ∪ v ,w; k := k − 1;8: end if9: end while10: Return(T = (V , E ′))

31

Andreas Jakoby



2. Vorlesung, 31.10.2007

Beispiel

9

3

2

6

4 16

5

7

1

13

2

3

4

6

1 5

0. Initialisierung

2

5

3

1

4

6

1. deletemin= 3, 6find(3) 6= find(6)

1

1

6

5

42

3


2

1

51

2 4

3

6

32

Andreas Jakoby



2. Vorlesung, 31.10.2007


2

1

3

51

2 4

3

6


4

3

1

2

51

2 4

3

6

5. deletemin= 2, 6find(2) = find(6)

4

3

1

2

51

2 4

3

6


4

3

1

2

51

2 4

3

6


4

3

1

2

51

2 4

3

6


4

9

3

2

1

51

2 4

3

6

33

Andreas Jakoby



2. Vorlesung, 31.10.2007

Korrektheit

Lemma 1 Sei

G = (V ,E ) ein ungerichteter Graph,

T = (V ,ET ) ein minimaler Spannbaum fur G ,

W = (V , EW ) ein Wald der in T enthalten ist, d.h. EW ⊆ ET und

S ⊆ V eine Knotenmenge, so dass keine Kante aus EW zwischenden Mengen S und V \ S verlauft.

Wir nennen eine Kante aus E kreuzend, wenn sie einen Knoten aus S

mit einem Knoten aus V \ S verbindet. Ist e ∈ E eine kreuzende Kante,die minimale Kosten unter allen kreuzenden Kanten besitzt, dann istauch W ′ := (V ,EW ∪ e) in einem minimalen Spannbaum enthalten.

34

Andreas Jakoby



2. Vorlesung, 31.10.2007

Beweis von Lemma 1:

Angenommen, T enthalt W aber nicht W ′.

e

SV \ S

Dann gilt e 6∈ ET .

T ist ein Spannbaum, somit gibt es vonjedem Knoten in V einen Weg zu jedemanderen Knoten in V .

Addieren wir e zu T , so schließen wireinen Kreis C .

C besitzt neben e noch eine kreuzendeKante e′.

Sei T ′ := (V , (ET ∪ e) \ e′). T ′ ist ein Spannbaum von G , da T ′ wieder zyklenfrei ist und |V | − 1

Kanten hat.

Da f (e) minimal unter allen kreuzenden Kanten ist, giltf (e) ≤ f (e′).

35

Andreas Jakoby



2. Vorlesung, 31.10.2007

Beweis von Lemma 1 (Teil 2)

Ist f (e) < f (e′), so gilt∑

w∈E ′T

f (w) <∑

w∈ETf (w) fur

E ′T = (ET ∪ e) \ e′. Dieses widerspricht der Annahme, dass T

ein minimaler Spannbaum ist. Wir konnen somit ausschließen, dassf (e) < f (e′) ist.

Ist f (e) = f (e′), so haben T und T ′ die gleichen Kosten. Da T einminimaler Spannbaum ist, muss auch T ′ ein minimaler Spannbaumsein. Wir haben somit gezeigt, dass W ′ in einem minimalenSpannbaum enthalten ist.

36

Andreas Jakoby



2. Vorlesung, 31.10.2007

Korrektheit vom Kruskals Algorithmus

Der MST-Algorithmus nimmt immer eine minimale kreuzende Kantein den bereits konstruierten Wald W auf.

Sei e = u, v = deletemin(Q). Uber die Abfrage find(u) = find(v) wird uberpruft, ob u und v

bereits in einer Komponente von W liegen. Beachte: Mit jedereingefugten Kante u′, v ′ vereinigen wir die entsprechendenMengen find(u′) und find(v ′). Somit reprasentiert jede Menge derPartition einen Baum des konstruierten Walds.

Ist find(u) = find(v), so verwerfen wir die Kante. Ist find(u) 6= find(v), so stellt S die Knotenmenge des Teilbaums dar,

in dem u liegt. Somit ist e eine minimale kreuzende Kante.

Aus Lemma 1 konnen wir nun schließen, dass W ′ = (V , EW ∪ e)in einem minimalen Spannbaum enthalten ist, wenn auchW = (V , EW ) in einem minimalen Spannbaum enthalten ist.

37

Andreas Jakoby



2. Vorlesung, 31.10.2007

Laufzeit von Kruskals Algorithmus

Die Initialisierung der Priorityqueue gelingt in Zeit O(|E |). Die Initialisierung der Partitionen gelingt in Zeit O(|V |). Die While-Schleife muss im Worst-Case |E | mal durchlaufen werden.

Bei jedem Durchlauf werden einmal die Operationen deletemin undzweimal die Operation find aufgerufen. Nach unseren Annahmenuber die Priorityqueue und der UNION/FIND-Datenstruktur konnenwir diese Operationen in Zeit O(|E | · log |E |) ausfuhren.

In |V | − 1 Durchlaufen der While-Schleife wird jeweils einmal eineunion-Operation aufgerufen.

Zusammen erhalten wir eine Laufzeit von O(|E | · log |E |).

38

Andreas Jakoby



2. Vorlesung, 31.10.2007

Satz 1 Sei G = (V ,E ) ein zusammenhangender, ungerichteter,gewichteter Graph. Dann berechnet Kruskals Algorithmus einenminimalen Spannbaum fur G in Zeit

O(|E | · log |E |) .

Beobachtung 1 Betrachten wir die Aussage von Lemma 1 und denKorrektheitsbeweis von Kruskals Algorithmus, so erkennen wir, dass wirhierbei ein exchange argument angewendet haben.

39

Andreas Jakoby



2. Vorlesung, 31.10.2007

4.2 Intervall-Scheduling

Definition 3 [Intervall-Scheduling Problem] Gegeben sei

eine Menge R = 1, . . . , n von n Jobs und

zwei Funktionen s, f : R → N.

Hierbei gilt fur alle Jobs i

s(i) ≤ f (i)

s(i) nennen wir die Startzeit von Job i und

f (i) nennen wir die Endzeit von Job i .

Job i steht im Konflikt mit Job j , wenn

i 6= j und

die Intervalle [s(i), f (i)[ und [s(j), f (j)[ sich uberlappen.

Mit [s(i), f (i)[ bezeichnen wir das nach rechts offene reelle Intervall.

40

Andreas Jakoby



2. Vorlesung, 31.10.2007

Definition 3 (Teil 2)

Eine Teilmenge S ⊆ R ist eine zulassige Schedule, wenn S

konfliktfrei ist, d.h. fur alle i , j ∈ S steht i nicht im Konflikt zu j .

Eine Teilmenge S ⊆ R ist eine optimale Schedule, wenn S einezulassige Schedule maximaler Kardinalitat ist, d.h. |S | ist maximal.

Aufgabe: Bestimme eine optimale Schedule!

41

Andreas Jakoby



2. Vorlesung, 31.10.2007

Wir starten mit einem Grundgerust fur einen Greedy-Algorithmus fur dasIntervall-Scheduling Problem:

Algorithmus Greedy-Intervall-Schedule(R)Eingabe: Menge R

Ergebnis: optimale Schedule S

1: S := ∅2: while R 6= ∅ do3: wahle ein eine Job i ∈ R

4: S := S ∪ i;5: entferne alle Jobs aus R, die zu i im Konflikt stehen6: R := R \ i7: end while8: Return(S)

Unsere Aufgabe besteht jetzt darin, den Auswahlmechanismus in Zeile 3naher zu beschreiben.

42

Andreas Jakoby



2. Vorlesung, 31.10.2007

Wir starten mit einer einfachen Beobachtung:

Beobachtung 2 Fur alle Auswahlmechanismen ist das Ergebnis S einezulassige Schedule.

Diese Beobachtung folgt unmittelbar daraus, dass wir in Zeile 5 alle Jobsloschen, die zu einem einmal in die Schedule aufgenommenen Job imKonflikt stehen.

43

Andreas Jakoby



2. Vorlesung, 31.10.2007

Einfache Auswahlmechanismen:

1. wahle i mit s(i) = minj∈R s(j)

2. wahle i mit f (i)− s(i) = minj∈R f (j)− s(j)

3. wahle das i , welches mit den wenigsten Jobs in R im Konflikt steht

4. wahle i mit f (i) = minj∈R f (j)

44

Andreas Jakoby



2. Vorlesung, 31.10.2007

Anhand der nachfolgenden Graphik konnen wir leicht erkennen, dassdie ersten drei Auswahlmechanismen auf Folie 44 keine optimaleSchedule liefern.

3.

2.

1.

Behauptung Benutzen wir jedoch den vierten Mechanismus in Zeile3 von Algorithmus Greedy-Intervall-Schedule, so erhalten wir eineoptimale Schedule. Dieses muss aber noch bewiesen werden!

45

Andreas Jakoby



3. Vorlesung, 7.11.2007

Benutzen wir den vierten Auswahlmechanismus, so konnen wir unserenGreedy-Algorithmus wie folgt implementieren:

Algorithmus Earliest-Finishingtime-First(R)Eingabe: Menge R

Ergebnis: optimale Schedule S

1: sortiere R nach aufsteigend Werten von f (i) und2: sei j1, . . . , jn die sortierte Folge3: S := j1; j := j14: for i := 2 to n by +1 do5: if f (j) ≤ s(ji ) then S := S ∪ ji; j := ji end if6: end for7: Return(S)

Die Laufzeit im Rumpf der For-Schleife ist konstant. Somit wird dieLaufzeit dieses Algorithmus durch das Sortieren in Zeile 1 dominiert undliegt in O(n · log2 n).

46

Andreas Jakoby



3. Vorlesung, 7.11.2007

Vergleichen wir nun S mit einer beliebigen optimalen Schedule O:

Sei O = j1, . . . , jm und S = i1, . . . , ik. Wir wollen zeigen, dass m = k ist.

O.B.d.A. gehen wir davon aus, dass die Intervalle in der Jobs in O

und S von rechts nach links sortiert sind, d.h.

∀ℓ < m : f (jℓ) ≤ s(jℓ+1) und ∀ℓ < k : f (iℓ) ≤ s(iℓ+1)

Um diese Reihenfolge zu erhalten konnen wir einfach die Elementein O bzw. in S nach den Startzeiten der Jobs sortieren.

Die Reihenfolge der Jobs andert sich nicht, wenn wir die Jobs nachderen Endzeiten sortieren.

47

Andreas Jakoby



3. Vorlesung, 7.11.2007

Wir wollen nun die zentrale Beobachtung fur unsere Greedy-Verfahren beiBenutzung der vierten Auswahlmethode beweisen:

Lemma 2 Fur alle r ≤ k gilt

f (ir ) ≤ f (jr ) .

Beweis von Lemma 2: Wir zeigen Lemma 2 mit Hilfe einer Induktionuber r .

Fur r = 1 folgt Lemma 2 aus der Beobachtung, dass der Algorithmusmit dem i1 startet, welches den minimalen Wert f (i1) besitzt.

48

Andreas Jakoby



3. Vorlesung, 7.11.2007

Beweis von Lemma 2 (Teil 2):

Fur r > 1 schließen wir wie folgt: Annahme, die Behauptung ist fur alle ℓ < r korrekt. Somit gilt f (ir−1) ≤ f (jr−1). Da O eine zulassige Schedule ist gilt f (jr−1) ≤ s(jr ). Somit ist i1, . . . , ir−1, jr eine zulassige Schedule. Da unser Algorithmus das ir mit minimalem f (ir ) wahlt, gilt

insbesondere f (ir ) ≤ f (jr ).

Somit gilt Lemma 2.

49

Andreas Jakoby



3. Vorlesung, 7.11.2007

Aus Lemma 2 konnen wir folgenden Satz schließen:

Satz 2 Earliest-Finishingtime-First berechnet eine optimale Schedule inZeit O(n · log2 n).

Beweis von Satz 2:

Ist k = m, so ist S optimal.

Ist k < m, so folgt aus Lemma 2: i1, . . . , ik , jk+1 ist eine zulassige Schedule. R ist nach dem Durchlaufen der Schedule nicht leer. S ist nicht das Ergebnis von Greedy-Intervall-Schedule bzw. von

Earliest-Finishingtime-First auf Eingabe von R — Widerspruch. Folglich ist k nicht kleiner m.

50

Andreas Jakoby



3. Vorlesung, 7.11.2007

Erweiterungen des Intervall-Scheduling Problems:

Online-Variante: Die Menge der Jobs liegt zu Beginn derBerechnung der Schedule noch nicht vor, sondern wird erst imVerlauf der Berechnung Job fur Job bekannt gegeben. DieAnfangsstucke der Schedule mussen jedoch so schnell wie moglicherstellt werden.

Gewichtetes Intervall-Scheduling Problems: Jeder Job besitztneben seinem Anfangs- und Endzeitpunkt noch ein Gewicht.Gesucht ist jetzt eine zulassige Schedule, die die Summe derGewichte maximiert.

51

Andreas Jakoby



3. Vorlesung, 7.11.2007

Beispiel fur die Online-Version: Ski-Leih Problem

Definition 4 [Ski-Leih Problem] Sie fahren zum ersten mal in Skiurlaubund betrachten die Frage, ob und nach wie vielen Saisons es sich rentiertSkier zu kaufen. Hierbei mussen Sie die folgenden Punkte betrachten:

Ein Skiausrustung kosten K Euro.

Das Leihen der Skiausrustung kostet pro Saison L Euro.

Sollten Sie die Lust am Skifahren verlieren (z.B. durch einen Unfall),so verlieren Sie die Lust am Skilauf dauerhaft. Sollten Sie sich bisdahin eigene Skier gekauft haben, so verliert die Ausrustung in dieserSaison ihren Wert.

Bei der Online-Version des Ski-Leih Problem mussen Sie zu Beginn jederSaison entscheiden, ob Sie sich eine Skiausrustung kaufen oder leihen. IhrZiel ist es die anfallenden Kosten zu minimieren.

52

Andreas Jakoby



3. Vorlesung, 7.11.2007

Satz 3 Der nachfolgende Online-Algorithmus approximiert die minimalenKosten fur das Ski-Leih Problem mit einem Faktor 2 fur L|K :

Algorithmus Online-Ski-Leih()Online Eingabe der Ereignisse e1, e2, . . .Online Ausgabe der Aktionen a1, a2, . . .

1: a1 := leihen; t := 12: while true do3: Return(at)4: t := t + 15: if at−1 = keine Lust mehr oder et−1 = Lust verloren then6: at := keine Lust mehr7: else8: if t ≤ K/t then at := leihen else at := kaufen end if9: end if10: end while

53

Andreas Jakoby



3. Vorlesung, 7.11.2007

4.3 Intervall-Partitionierungs Problem

Ein mit dem Intervall-Scheduling Problem nahe verwandtes Problem istdas Intervall-Partitionierungs Problem:

Definition 5 [Intervall-Partitionierungs Problem] Gegeben sei


zwei Funktionen s, f : R → N.

Eine Partitionierung I = I1, . . . , Id nennen wir zulassig, wenn jedeMenge Ii eine zulassige Schedule von Jobs aus R ist.

Aufgabe: Gesucht ist eine zulassige Partitionierung minimalerKardinalitat!

Eine Teilmenge C ⊆ R nennen wir Konfliktmenge, wenn jeder Job ausC mit jedem anderen Job aus C einen Konflikt hat, d.h.

∃t ∈ N ∀i ∈ C : s(i) ≤ t < f (i) .

Die Uberlappung ovl(R) einer Jobmenge R = 1, . . . , n ist diemaximale Kardinalitat einer Konfliktmenge.

54

Andreas Jakoby



3. Vorlesung, 7.11.2007

Beispiel: Gegeben ist eine Menge von VorlesungsmodulenR = 1, . . . , n mit entsprechenden Start- und Endzeitpunkten. Findeeine Aufteilung der Vorlesungen auf die Horsale, so dass nur eineminimale Anzahl an Horsale benotigt wird.

55

Andreas Jakoby



3. Vorlesung, 7.11.2007

Lemma 3 Fur jede Eingabe R, s, f hat jede zulassige Partitionierung eineKardinalitat mindestens ovl(R).

Beweis von Lemma 3: Das Lemma folgt unmittelbar aus derBeobachtung, dass alle Jobs aus einer Konfliktmenge in unterschiedlichenTeilmengen der Partition liegen mussen.

Wir wollen nun einen Algorithmus vorstellen und analysieren, der einezulassige Partitionierung der Kardinalitat ovl(R) findet.

56

Andreas Jakoby



3. Vorlesung, 7.11.2007

Algorithmus Starttime-Ordering(R)Eingabe: Menge R der JobsErgebnis: zulassige Partitionierung der Kardinalitat ovl(R)

1: sei Q eine leere Priorityqueue Q fur Jobs i mit Prioritaten f (i).2: sei r1, . . . , rn die nach den Startzeiten sortierte Folge der Jobs3: sei ℓ := 1, m(r1) := 1 und fuge r1 in Q und in I1 ein4: for i = 2 to n by +1 do5: sei rj das erste Element in Q

6: if f (rj) > s(ri ) then7: sei ℓ := ℓ + 1, m(ri ) := ℓ und fuge ri in Q und in Iℓ ein8: else9: entferne rj aus Q

10: sei m(ri ) := m(rj) und fuge ri in Q und in Im(rj ) ein11: end if12: end for13: Return(I1, . . . , Iℓ)

57

Andreas Jakoby



3. Vorlesung, 7.11.2007

Warum ist Starttime-Ordering ein Greedy-Algorithmus?

Wir mussen das lokale Entscheidungkriterium finden, welches wir injedem Schritt des Verfahrens benutzen:

In jedem Durchlauf der For-Schleife betrachten wir den noch nichtbetrachteten Job ri mit der minimalen Startzeit.

Wir fugen diesen Job in eine (beliebige) Teilmenge ein, deren Jobsnicht zum aktuell betrachtete Job im Konflikt stehen.

Alle diese Kriterien stellen lokale Entscheidungkriterien dar.

Starttime-Ordering ist somit ein Greedy-Algorithmus.

58

Andreas Jakoby



3. Vorlesung, 7.11.2007

Wir wollen nun den Algorithmus Starttime-Ordering analysieren:

Beobachtung 3 Die Ausgabe I1, . . . , Iℓ von Starttime-Ordering ist einezulassige Partition.

Beweis von Beobachtung 3: Wir betrachten zunachst die PriorityqueueQ:

Bei jedem Durchlauf der For-Schleife ist in Q fur jede nicht-leereTeilmenge Ij das zu letzt in Ij eingefugte Element gespeichert.

ri wird nur in eine Teilmenge Im(rj ) eingefugt wird, wenns(ri ) ≥ f (rj) ist.

Per Induktion uber i folgt nun, dass ein Job ri nie in eine Teilmengeeingefugt wird, welche einen Job rk enthalt, welches zu ri imKonflikt steht.

59

Andreas Jakoby



3. Vorlesung, 7.11.2007

Lemma 4 Fur die Ausgabe I1, . . . , Iℓ von Starttime-Ordering giltℓ = ovl(R).Beweis von Lemma 4: Fur die Priorityqueue Q gilt:

In jedem Schleifendurchlauf gilt, dass die Endzeit des erstenElements in Q minimal unter allen Elementen in Q ist.

In dem Schleifendurchlauf fur einen Job ri wir nur dann eine neueTeilmenge Ik generiert, wenn ri im Konflikt mit dem ersten Elementin Q und somit zu allen Elementen in Q steht.

Wird in einem Schleifendurchlauf fur einen Job ri eine neueTeilmenge Ik generiert, so gilt fur alle Jobs rk in Q

aufgrund der Sortierung in Zeile 2: s(rk) ≤ s(ri ) und aufgrund der Eigenschaften der Priorityqueue: f (rk) > s(ri ).

60

Andreas Jakoby



3. Vorlesung, 7.11.2007


Werden also mehr als ovl(R) viele Teilmengen Ik generiert, so gibt esein ri , so dass es in R zumindest ovl(R) + 1 viele Jobsh1, . . . , hovl(R)+1 mit

s(hj) ≤ s(ri ) < f (hj) .

Diese Jobs bilden somit eine Konfliktmenge der Kardinalitatovl(R) + 1.

Dieses ist ein Widerspruch zur Definition von ovl(R).

61

Andreas Jakoby



3. Vorlesung, 7.11.2007

Beobachtung 4 Die Laufzeit von Starttime-Ordering ist in O(n · log n).

Beweis von Beobachtung 4:

Um die n Jobs zu sortieren benotigen wir O(n log n) Schritte.

Fur jeden Job ri mit i ≥ 2 mussen wir einmal den Rumpf derFor-Schleife durchlaufen. Um den Rumpf einmal zu durchlaufenmussen wir

einmal auf das erste Element von Q zugreifen (O(1)), ein Element in Q einfugen (O(log ℓ)) und unter Umstanden das erste Element aus Q entfernen (O(log n)).

Diese Laufzeiten folgen aus unserer Annahme von Folie 28.

Da die Anzahl der Teilmengen durch die Anzahl der Elementebeschrankt ist, erhalten wir eine Laufzeit von

O(n · log n + n · log ℓ) = O(n · log n)

62

Andreas Jakoby



3. Vorlesung, 7.11.2007

Fassen wir unsere Beobachtungen von den Folien 56 bis 62 zusammen, soerhalten wir:

Satz 4 Es gibt ein Greedy-Algorithmus, dar das Intervall-PartitionierungsProblem in Zeit O(n · log n) lost.

Wie konnen wir den Beweis der Optimalitat von Starttime-Ordering mitHilfe unserer beiden Schemata von Folie 25 interpretieren?

Fur jeden Zeitpunkt t mit

mini∈R

s(i) ≤ t < maxi∈R

f (i)

gilt:

Fur alle Jobs i ∈ R mit s(i) ≤ t generiert

Starttime-Ordering maximal so viele Teilmengen, wie ein

optimaler Algorithmus generieren wurde.

63

Andreas Jakoby



4. Vorlesung, 14.11.2007

4.4 Intervall-Scheduling mit Deadline

Definition 6 [Intervall-Scheduling mit Deadline] Gegeben sei


zwei Funktionen δ, τ : R → N.

Mit τ(i) bezeichnen wir die Laufzeit von Job i und mit δ(i) dieDeadline von i :

Starten wir Job i zum Zeitpunkt t, so endet die Berechnung von i

zum Zeitpunkt t + τ(i).

Eine Schedule S fur R weist jedem Job i einen Startzeitpunkt S(i) zu.Eine Schedule S nennen wir zulassig, wenn fur alle Paare i , j ∈ R miti 6= j gilt:

die Intervalle [S(i), S(i) + τ(i)[ und [S(j), S(j) + τ(j)[ uberlappensich nicht.

64

Andreas Jakoby



4. Vorlesung, 14.11.2007

Definition 6 (Teil 2) Wir sagen, dass sich ein Job i in einer Scheduleum den Wert

v(i) := max0, S(i) + τ(i)− δ(i)verspatet. Wir definieren die Verspatung einer Schedule S als

L(S) := maxi∈R

v(i) .

Eine Schedule S nennen wir optimal, wenn

S zulassig ist und fur alle

anderen zulassige Schedules S ′ fur R gilt

L(S) ≤ L(S ′) .

Aufgabe: Finde eine optimale Schedule!

65

Andreas Jakoby



4. Vorlesung, 14.11.2007

Algorithmus Earliest-Deadline-First(R)Eingabe: Menge R der Jobs mit Laufzeiten τ(i) und Deadlines δ(i)Ergebnis: eine optimale Schedule S

1: sei r1, . . . , rn die nach der Deadlines sortierte Folge der Jobs2: sei t := 03: for i := 1 to n by +1 do4: schedule ri fur den Zeitpunkt t, d.h. S(ri ) := t

5: setze t := t + τ(ri )6: end for7: Return(S)

66

Andreas Jakoby



4. Vorlesung, 14.11.2007

Um die Optimalitat des Resultats von Earliest-Deadline-First zu zeigen,werden wir folgende Punkte analysieren:

Eine Schedule S besitzt Leerzeiten, wenn fur einen Zeitpunkt

t ∈ [0, maxi∈RS(i) + τ(i)[

keinen Job i ∈ R mit

S(i) ≤ t < S(i) + τ(i)

existiert.

Fur eine Schedule S nennen wir ein Paar (i , j) nennen wir Inversion,wenn

S(i) < S(j) und δ(i) > δ(j)

ist.

67

Andreas Jakoby



4. Vorlesung, 14.11.2007

Beobachtung 5 Es gibt eine optimale Schedule ohne Leerzeiten.

Lemma 5 Alle Schedules ohne Inversion und ohne Leerzeiten besitzen diegleiche maximale Verspatung.

Beweis von Lemma 5:

Seien S und S ′ zwei unterschiedliche Schedules ohne Inversion undohne Leerzeiten.

S und S ′ unterscheiden sich nur in der Startreihenfolge der Jobs mitgleicher Deadline.

68

Andreas Jakoby



4. Vorlesung, 14.11.2007


Sei D(i) := j ∈ R | δ(i) = δ(j) und sei d(i ,S) der Job ausD(i), der in S als letztes ausgefuhrt wird, dann gilt fur alle i ∈ R

S(d(i ,S)) + τ(d(i ,S)) =∑

j∈k∈R|δ(k)≤δ(i)

τ(j)

= S ′(d(i , S ′)) + τ(d(i ,S ′)) .

Da L(S) = maxi∈R S(d(i , S)) + τ(d(i , S))− δ(i) ist, giltL(S) = L(S ′).

69

Andreas Jakoby



4. Vorlesung, 14.11.2007

Um den folgenden Satz zu beweisen werden wir ein exchange argument

anwenden.

Satz 5 Es existiert eine optimale Schedule ohne Inversion und ohneLeerzeiten.

Beweis von Satz 5:

Nach Beobachtung 5 gibt es eine optimale Schedule O ohneLeerzeiten.

Gibt es in O eine Inversion, dann gibt es ein Paar i , j ∈ R, so dass i

unmittelbar nach j ausgefuhrt wird — d.h. S(i) = S(j) + τ(j) —und δ(j) > δ(i) ist.

70

Andreas Jakoby



4. Vorlesung, 14.11.2007

Beweis von Satz 5 (Teil 2):

Tauschen wir das Paar i und j , dann hat die neue Schedule O ′ eine Inversion weniger und die maximale Verspatung von O ′ ist kleiner gleich der maximalen

Verspatung von O.

O ′ ist somit eine optimale Schedule ohne Leerzeiten und einerInversion weniger als O.

Wir konnen somit Schritt fur Schritt alle Inversionen aus O

entfernen.

71

Andreas Jakoby



4. Vorlesung, 14.11.2007

Die vom Algorithmus Earliest-Deadline-First generierte Schedule ist:

ohne Leerzeiten aufgrund der Wahl von t in Zeile 2 und 5 und

ohne Inversion aufgrund der Sortierens der Jobs bezuglich ihrerDeadlines in Zeile 1.

Aus Lemma 5 und Satz 5 folgt nun unmittelbar:

Satz 6 Earliest-Deadline-First generiert eine optimale Schedule.

72

Andreas Jakoby



4. Vorlesung, 14.11.2007

4.5 Online-Scheduling — das Caching–Problem

In viele Scheduling–Anwendungen sind nicht alle zeitlichen Datenvorab bekannt.

In einem solchen Szenario mussen oft sukzessive Entscheidungenuber eine Schedule getroffen werden, bevor weitere zeitlicheInformationen bekannt werden.

Fehlende Informationen uber die Zukunft verhindern zumindest ineinem worst–case Szenario, dass die von einem Algorithmusgetroffenen sukzessiven online–Entscheidungen zu einem optimalenSchedule vervollstandigt werden konnen.

Ein Beispiel fur eine solche Aufgabe ist das Caching-Problem: Datenelemente mussen in einem lokalen Cache gehalten werden,

damit ein Prozessor schnell auf sie zugreifen kann. Die Kapazitat k (Anzahl der Speicherplatze) ist viel kleiner als die

Anzahl der Datenelemente. Soll ein Datenelement x verwendet werden, dass nicht im Cache

vorhanden ist, so spricht man von einem Cache-Miss.

73

Andreas Jakoby



4. Vorlesung, 14.11.2007

Definition 7 [Caching-Problem] Gegeben ist

eine Anfragesequenz X = x1, x2, . . . uber einem Universum U und

ein Cache C der Große k, d.h. C kann k Elemente aus U speichern.

Eine Schedule fur das Caching-Problem besteht aus einer Folge vonOperationen. Zur Verfugung stehen:

load-Operationen: load(x) legt das Datenelement x auf einem freienCacheplatz ab. Diese Operation verursacht Kosten 1.

eject-Operationen: eject(x) entfernt das Datenelement x aus demCache und hinterlaßt einen freien Cacheplatz. Diese Operationverursacht keine Kosten.

nop-Operationen: nop fuhrt zu keiner Veranderung des Caches.Diese Operation verursacht keine Kosten.

Die letzte Operation ist nicht unbedingt notigt. Sie vereinfacht jedoch dieDarstellung der Schedule.

74

Andreas Jakoby



4. Vorlesung, 14.11.2007

Definition 7 (Teil 2) Eine Schedule (oder Strategie) fur eineAnfragesequenz X = x1, x2, . . . ist eine Sequenz O = o1, o2, . . . vonCache-Operationen, die zu einer Folge von Cache-ZustandenC0,C1, C2, . . . fuhrt, wobei

Ci :=

∅ fur i = 0Ci−1 fur oi = nopCi−1 \ x fur oi = eject(x)Ci−1 ∪ x fur oi = load(x)

und die folgenden Bedingungen erfullt sein mussen:

fur alle i ist |Ci | ≤ k und

fur alle i ist xi ∈ C2i .

Die Kosten einer Schedule sind die Summe der ausgefuhrtenload-Operationen.Aufgabe: Finde eine Schedule fur die Sequenz X mit minimalenKosten, d.h. mit einer minimalen Anzahl von Cache-Misses!

75

Andreas Jakoby



4. Vorlesung, 14.11.2007

Vorbemerkungen:

Ein Algorithmus muss entscheiden: wann eine load(x)-Operation fur ein Element x ausgefuhrt werden

muss und welches Element y durch eject(y) zuvor entfernt werden muss.

Fuhrt eine Strategie erst dann load(x) aus, wenn x in derAnfragesequenz erscheint, dann nennen wir diese Strategie lazy.

Zudem verlangen wir von einer lazy Strategie, dass sie nur dann eineeject-Operation ausfuhrt, wenn Platz im Cache benotigt wird, d.h.unmittelbar vor einer notwendigen load-Operation bei vollem Cache.

76

Andreas Jakoby



4. Vorlesung, 14.11.2007

Lemma 6 Fur jede Strategie A gibt es eine lazy Strategie B, die maximalso viele Kosten als A verursacht.

Beweis von Lemma 6: Zunachst wandeln wir A in eine Strategie um,die keine uberflussigen load- und eject-Operationen beinhaltet:

Ist load(x) ∈ o2i−1, o2i, dann gibt es ein j ≥ i mit xj = x , so dassalle Operationen o2k−1, o2k mit k ∈ [i ; j ] x nicht aus dem Cacheentfernen.

Ist oi = load(x), dann gibt x 6∈ Ci−1.

Ist oi = eject(x), dann gibt x ∈ Ci−1.

Alle load- und eject-Operationen, die diese Bedingungen nicht erfullen,sind uberflussig und konnen durch nop-Operationen ersetzt werden.

77

Andreas Jakoby



4. Vorlesung, 14.11.2007


Wir alle load-Operationen auf gerade und alle eject-Operationen aufungerade Stellen der Sequenz. Hierbei verfahren wir wie folgt:

Wir gehen von vorne nach hinten durch die Sequenz der Operationen. Hierbei sammeln wir die load- und die eject-Operationen auf und

plazieren sie neu in unsere Schedule: Sei S = o1, o2, . . . die alte und S ′ = o′1, o

′2, . . . die neue Schedule.

Zum Aufsammeln der Operationen benutzen wir Multimengen L undE fur die load- und die eject-Operationen.

Betrachten wir ein Paar o2i−1, o2i von Operationen, so fugen wir dievorhandenen load-Operationen zunachst in die Mengen L und dievorhandenen eject-Operationen zunachst in die Mengen E ein.

Mit Hilfe der Mengen L und E konnen wir jetzt das Paar o′2i−1, o′2i

generieren.

78

Andreas Jakoby



4. Vorlesung, 14.11.2007


Weiter mit der Umformung: Ist xi nach den Operationen o′1, . . . , o

′2i−2 im Cache vorhanden, dann

konnen wir o′2i−1, o′2i auf nop setzen.

Fehlt xi nach den Operationen o′1, . . . , o′2i−2 im Cache, dann muss es

fur xi im Prafix o1, . . . , o2i eine load-Operation gegeben haben, diewir im Prafix o′1, . . . , o

′2i−2 noch nicht ausgefuhrt haben. Diese setzen

wir jetzt auf o′2i und entfernen diese aus L. Wird der Cache im Verlauf der Operationen o′1, . . . , o

′2i−2 vollstandig

gefullt, dann gibt es im Cache nach den Operationen o′1, . . . , o′2i−2

ein Element, welches sich nach den Operationen o1, . . . , o2i nicht imCache befindet. Da bei unserem Verfahren die load-Operationen vonvorne nach hinten wandern, muss es fur dieses Element in derSequenz o1, . . . , o2i eine eject-Operation geben, die wir ino′1, . . . , o

′2i−2 noch nicht ausgefuhrt haben. Diese fuhren wir jetzt als

o′2i−1 aus und erhalten Platz fur die benotigte load-Operation o′2i .

79

Andreas Jakoby



5. Vorlesung, 21.11.2007

Es ist einfach zu zeigen, dass im Online-Fall fur jede Strategie eineSequenz existiert, die Kosten in der Lange der Sequenz verursacht:

In den ersten k Elementen fullen wir den Cache.

Als das k + 1-te Element wahlen wir ein Element, welches nochnicht im Cache ist.

Wir wahlen xi fur i ≥ k + 2 als das Element, welches wir als letztenaus dem Cache entfernt haben.

Wenn die Sequenz x1, . . . , xn im Voraus bekannt ist, konnen wir mit Hilfedes folgenden Greedy-Algorithmus eine optimale Schedule generieren.

80

Andreas Jakoby



5. Vorlesung, 21.11.2007

Algorithmus Evict-Furtherst-In-Future(X )Eingabe: Sequenz X = x1, . . . , xn von DatenelementenErgebnis: eine optimale Schedule o1, . . . , o2n

1: C := ∅2: for i := 1 to n by +1 do3: t(xi ) := minj > i |xj = xi;4: if xi ∈ C then5: o2i−1 := nop; o2i := nop; C := C

6: else if |C | < k then7: o2i−1 := nop; o2i := load(xi ); C := C ∪ xi8: else9: wahle xj ∈ C mit t(xj) := maxx∈C t(x)10: o2i−1 := eject(xj); o2i := load(xi ); C := (C ∪ xi) \ xj11: end if12: end for13: Return(o1, . . . , o2n)

81

Andreas Jakoby



5. Vorlesung, 21.11.2007

Kommentare zum Algorithmus

Bei der Berechnung von t(xi ) in den Zeile 3 gehen wir davon aus,dass t(xi ) = +∞ ist, wenn auf das Element xi zukunftig nicht mehrzugegriffen wird.

82

Andreas Jakoby



5. Vorlesung, 21.11.2007

Satz 7 Fur jede Zugriffssequenz X konstruiert der AlgorithmusEvict-Furtherst-In-Future eine Schedule mit minimalen Kosten.

Beweis von Satz 7: Wir wollen diese Aussage uber ein exchange

argument beweisen. Sei

O eine optimale und lazy Schedule und

S eine Schedule wie sie uber den Algorithmus konstruiert wird.

Wir wollen nun O Schritt fur Schritt so verandern, dass wir S erhalten.Wir erhalten hierbei eine Sequenz von optimalen und lazy SchedulesO0 = O, O1, . . . ,On = S :

Hierbei fuhrt Oi auf den ersten i Elementen der Eingabe die gleicheneject-Operationen wie S aus.

83

Andreas Jakoby



5. Vorlesung, 21.11.2007

Beweis von Satz 7 (Teil 2): Wir zeigen die folgende Aussage:

Sei Oi eine optimale und lazy Schedule, die auf den ersten i

Elementen der Eingabe die gleichen eject-Operationen wie S

ausfuhrt, dann konnen wir eine optimale und lazy Schedule Oi+1

konstruieren, die auf den ersten i + 1 Elementen der Eingabe diegleichen eject-Operationen wie S ausfuhrt.

Wir unterscheiden die folgenden Falle:

Oi und S fuhren auf das i + 1-te Element der Eingabe die gleicheeject-Operation aus. In diesem Fall setzen wir Oi+1 = Oi .

Oi und S fuhren auf das i + 1-te Element der Eingabe verschiedeneeject-Operation aus. Sei y das Element, welches hierbei in S ausdem Cache entfernt wird und sei z das entsprechende Element in Oi .Wir ersetzen zunachst die Operation eject(z) in Oi durch eject(y)und erhalten O ′i .

84

Andreas Jakoby



5. Vorlesung, 21.11.2007

Beweis von Satz 7 (Teil 3): Bezuglich y und z unterscheiden wir diefolgenden Falle:

Bevor y in der Eingabe wieder angefragt wird, wird y auch von O ′iaus dem Cache entfernt:

Gibt es bis zu diesem Zeitpunkt keine neue Anfrage nach z , dannersetzen wir diese eject-Operation in O ′i durch eject(z), und wirerhalten einen Cache, der nach dieser Operation fur Oi und O ′iidentische ist. Sei jetzt Oi+1 := O ′i .

Vor diesem Zeitpunkt gibt es eine neue Anfrage nach z . Wirbetrachten die erste dieser Anfragen nach der i + 1-ten Anfrage. Dain O ′i das Element z nicht aus dem Cache entfernt wurde, konnenwir die entsprechende load(z)-Operation aus O ′i sowie die gefundeneeject(y)-Operation aus O ′i entfernen. Die resultierende Schedule istjetzt nicht mehr lazy. Wir konnen diese Bedingung jedoch analog zuLemma 6 wieder herstellen ohne die Operationen fur die ersteni +1-Eingabeelemente zu andern. Sei Oi+1 die resultierende Schedule.

85

Andreas Jakoby



5. Vorlesung, 21.11.2007


Es bleibt jetzt noch der Fall, dass y in O ′i nicht aus dem Cacheentfernt, bis y erneut angefragt wird. In diesem Fall verfahren wirwie folgt:

Wir starten eine Suche nach dem ersten Auftauchen von z in derEingabe nach dem i + 1-ten Eingabeelement. Da z zu diesemZeitpunkt nicht im Cache bei der Schedule Oi ist, mussen wir andieser Stelle eine load(z)-Operation ausfuhren. Bei O ′i befindet sichjedoch z noch im Cache. Daher ist diese load-Operation nicht mehrnotigt und wir konnen sie durch ein load(y) ersetzen.Die resultierende Schedule ist jetzt nicht mehr lazy. Wir konnen dieseBedingung jedoch analog zu Lemma 6 wieder herstellen ohne dieOperationen fur die ersten i + 1-Eingabeelemente zu andern. SeiOi+1 die resultierende Schedule.

86

Andreas Jakoby



5. Vorlesung, 21.11.2007

4.6 Das Shortest-Path Problem

Beim kurzesten Wegeproblem unterscheiden wir: Single Source Shortest Path Problem (SSSPP): Finde die

billigsten Wege von einer Quelle (Startknoten) zu allen anderenKnoten.

All Pairs Shortest Path Problem (APSPP): Finde die billigstenWege zwischen allen Knotenpaaren.

Als Eingabe liegt bei diesen Problemen jeweils ein gewichteter GraphG = (V , E ) mit einer Kantengewichtsfunktion f : E → R+ vor.

Beachte: Die Kantengewichtsfunktion weist jeder Kante ein positivesGewicht ungleich 0 zu.

Ist das Kantengewicht konstant 1, so konnen wir SSSPP mit Hilfeder Breitensuche losen.

87

Andreas Jakoby



5. Vorlesung, 21.11.2007

Algorithmus von Dijkstra

Der Algorithmus von Dijkstra lost das SSSPP Problem.

Ideen: Zur Vereinfachung gehen wir davon aus, dass V = [1..n] und 1 die

Quelle sind. Sei C die |V | × |V |-Kostenmatrix von G , d.h.

C [u, v ] :=

f (u, v) fur (u, v) ∈ E

∞ sonst.

In S speichern wir die Menge der Knoten v , fur die wir bereits einenkurzesten Weg von 1 aus gefunden haben. Zu Beginn ist S = 1.

Im Feld D speichern wir fur jeden Knoten v die Kosten des kurzestenbis jetzt gefundenen Pfades von 1 nach v , wobei wir auf diesem Pfadnur uber Knoten aus S laufen durfen.

Im Feld W speichern wir den Vorganger von v auf dem kurzesten bisjetzt gefundenen Pfad.

88

Andreas Jakoby



5. Vorlesung, 21.11.2007

Idee des Algorithmus von Dijkstra:

1. Setze S := 1.2. Suche den Knoten v ∈ V \ S , fur den der bis jetzt gefundene

Weg minimal ist. Setze S := S ∪ v und modifiziere die FelderD und W fur die Knoten u ∈ V \ S mit (v , u) ∈ E , falls sichdurch die Hinzunahme von v zu S ein kurzerer Pfad von 1 nachu ergibt.

3. Wiederhole den letzte Schritt bis S = V .

Wir gehen davon aus, dass G ,S , D,W global gegeben sind.

89

Andreas Jakoby



5. Vorlesung, 21.11.2007

Beispiel:

2

S :

1

2

3

4

5

6

1

4

4

2

2

1

3

1

Sei S = 1, 2, 3 und D[4] = 4, D[5] = 2, D[6] = 6,

dann ist 5 der nachste Knoten, der inS eingefugt wird.

Der Pfad P5 ist 1, 2, 5.

90

Andreas Jakoby



5. Vorlesung, 21.11.2007

Wie finden wir den nachsten in S einzufugenden Knoten?

Algorithmus next-node()Eingabe: global gegebenErgebnis: u ∈ V \ S mit minimaler Distanz zu 1

1: min:=∞2: for v ∈ V \ S do3: if D[v ] < min then4: min:= D[v ]5: u := v

6: end if7: end for8: Return(u)

91

Andreas Jakoby



5. Vorlesung, 21.11.2007

Modifikation der Felder:

Algorithmus modify(u)Eingabe: u ∈ V \ S mit minimaler Distanz zu 1Ergebnis: modifizierte Datenstruktur

1: S := S ∪ u2: for v ∈ V \ S mit (u, v) ∈ E do3: if D[u] + C [u, v ] < D[v ] then4: W [v ] := u

5: D[v ] := D[u] + C [u, v ]6: end if7: end for

92

Andreas Jakoby



5. Vorlesung, 21.11.2007

Algorithmus Dijkstra(C )Eingabe: global gegebene Kostenmatrix C , die leere Menge S

sowie Felder D,WErgebnis: Losung des SSSPP im Feld W

1: S := 12: for v ∈ V \ S do3: D[v ] := C [1, v ]; W [v ] := 14: end for5: while S 6= V do6: modify(next-node())7: end while

93

Andreas Jakoby



5. Vorlesung, 21.11.2007

Im Feld W steht fur jeden Knoten v der kurzeste Weg uber dieKnoten aus S vom Knoten 1:

Initialisiert wird W durch W [v ] := 1 und setzen D[v ] := C [1, v ]. Fur jeden Knoten v ∈ V \ S sei D[v ] der Abstand von 1 und v in

S ∪ v. Fur jeden Knoten v ∈ V \ S sei W [v ] der Vorganger von v auf dem

kurzesten Weg von 1 nach v in S ∪ v. Somit ist

Pv = v , W [v ], W [W [v ]], . . . , W [W [· · · [W [v ]] · · · ]] = 1

der inverse kurzeste Weg von 1 nach v in S ∪ v.

Bei der Implementierung mussen wir fur ∞ einen geeigneten Wertfinden, z.B.: 1 + n ·maxi,j C [i , j ].

Beachte: Dieses Verfahren generiert aus lokalen Eigenschaften (wirwahlen den lokal billigsten Nachfolger) eine globale Eigenschaft (allegenerierten Wege sind optimal) und ist somit einGreedy-Algorithmus.

94

Andreas Jakoby



5. Vorlesung, 21.11.2007

Beispiel:

30

50 10

15

203015

20

10

45

54

321

Kostenmatrix:

C =

∞ 50 45 10 ∞∞ ∞ 10 15 ∞∞ ∞ ∞ ∞ 3020 ∞ ∞ ∞ 15∞ 20 30 ∞ ∞

S = 1 und next-node= 4

v 1 2 3 4 5D[v ] ∞ 50 45 10 ∞

v 1 2 3 4 5W [v ] - 1 1 1 1

95

Andreas Jakoby



5. Vorlesung, 21.11.2007

S = 1, 4 und next-node= 5

v 1 2 3 4 5D[v ] ∞ 50 45 10 25

v 1 2 3 4 5W [v ] - 1 1 1 4

S = 1, 4, 5 und next-node= 2

v 1 2 3 4 5D[v ] ∞ 45 45 10 25

v 1 2 3 4 5W [v ] - 5 1 1 4

S = 1, 2, 4, 5 und next-node= 3

v 1 2 3 4 5D[v ] ∞ 45 45 10 25

v 1 2 3 4 5W [v ] - 5 1 1 4

Endzustand: S = 1, 2, 3, 4, 5v 1 2 3 4 5

D[v ] ∞ 45 45 10 25v 1 2 3 4 5

W [v ] - 5 1 1 4

96

Andreas Jakoby



5. Vorlesung, 21.11.2007

Der Beweis, dass der Algorithmus von Dijkstra eine optimale Losungfindet erfolgt uber ein greedy algorithm stays ahead Argument.

Lemma 7 Sei S eine beliebige Menge, die im Algorithmus Dijkstra ineinem Aufruf der Prozedur modify berechnet wird, dann gilt fur alleu ∈ S , dass Pu der kurzeste Pfad von 1 nach u.

Beweis von Lemma 7: Der Beweis erfolgt uber vollstandige Induktionuber die Kardinalitat von S .

Fur |S | = 1, d.h. S = 1, ist das Lemma trivialer Weise erfullt.

Wir nehmen nun an, dass die Aussage fur das Lemma fur Mengen S

mit |S | ≤ k erfullt ist.

97

Andreas Jakoby



5. Vorlesung, 21.11.2007


Wir betrachten nun eine Menge S der Kardinalitat k und denKnoten v , der im nachsten Schritt zu S hinzugefugt wird.

Betrachten wir einen Pfad Pu von 1 zu einem Knoten u ∈ S , soerkennen wir, dass dieser vollstandig in S verlauft.

v

1

x

u

Px

Pu

y

S : Sei v der Knoten, der im k + 1-ten Schritt

in S eingefugt wird.

Sei (u, v) die letzte Kante in Pv .

Nach Induktion ist Pu der kurzeste Pfadvon 1 nach u.

Sei P ein beliebiger Pfad von 1 nach v .Wir wollen zeigen, dass P mindestens dieLange von Pv hat.

Sei y der erste Knoten auf P, der nicht inS ist und sei x der direkte Vorganger vony .

98

Andreas Jakoby



5. Vorlesung, 21.11.2007


Es gilt: P hat mindestens die Lange des kurzesten Pfades von 1 nach x , d.h.

D[x ] plus der Lange (Gewicht) der Kante (x , y) plus der Lange des Suffixes des Pfades P von y nach v .

Die Lange von P ist zumindest D[x ] + C [x , y ].

Wir wahlen jedoch (u, v) so, dass D[u] + C [u, v ] minimal ist fur alleu ∈ S und v ∈ V \ S .

Somit ist |P| ≥ D[x ] + C [x , y ] ≥ D[u] + C [u, v ] ≥ |Pv |.

99

Andreas Jakoby



5. Vorlesung, 21.11.2007

Satz 8 Der Algorithmus von Dijkstra lost SSSPP.

Beweis: In Lemma 7 haben wir gezeigt, dass der Algorithmus vonDijkstra fur jede der konstruierten Menge S und fur jeden Knoten v ∈ S

eine kurzesten Pfades von 1 nach v konstruiert. Dieses gilt insbesonderefur S = V .

100

Andreas Jakoby



5. Vorlesung, 21.11.2007

5 Backtracking bei diskretenOptimierungsproblemenWir wollen zunachst einige Begriffe definieren:

Definition 8 [Optimierungsprobleme]

Eine Instanz eines Optimierungsproblems ist ein Paar (F , f )wobei

F eine Menge von moglichen Losungen und f : F → R eine Kostenfunktion dieser Losungen abgibt.

Eine Losung x ∈ F nennen wir global optimal oder kurz optimal,wenn fur alle y ∈ F gilt

f (x) ≥ f (y) .

Gesucht ist eine optimale Losung bezuglich derKostenfunktion!

Ein Optimierungsproblem ist eine Menge von Instanz einesOptimierungsproblems.

101

Andreas Jakoby



5. Vorlesung, 21.11.2007

Anmerkungen zu Definition 8:

Die Form von Optimierungsproblemen aus Definition 8 nennen wirauch Maximierungsprobleme, da wir eine Losung x ∈ F mitf (x) ≥ f (y) fur alle y ∈ F suchen.

Suchen wir ein x ∈ F mit f (x) ≤ f (y) fur alle y ∈ F , so sprechenwir auch von einem Minimierungsproblem.

Beispiele fur solche Minimierungs- und Maximierungsproblemehaben wir schon einige in dieser Vorlesung kennen gelernt.

102

Andreas Jakoby



5. Vorlesung, 21.11.2007

Oft finden wir auch eine alternative Definition: EinOptimierungsproblem wird durch

eine Menge X potentieller Losungen und

einer Kostenfunktion dieser Losungen val : I × X → R.

Hierbei ist I die Menge aller Probleminstanzen (Eingaben) I von Q.Eine Instanz bezuglich Definition 8 erhalten wir dann uber

(F , f ) mit F := X und f ≡ val(I , ·) .

Abhangig von der Problemdefinition suchen wir nach

einem X ∈ X (oder allen X ∈ X ), die f minimieren bzw.maximieren oder

dem minimalen bzw. maximalen Wert von f .

103

Andreas Jakoby



6. Vorlesung, 28.11.2007

5.1 Das Rucksackproblem

Definition 9 [Rucksackproblem]

Gegeben ist eine Folge von n Gutern mit BewertungsvektorV = (v0, . . . , vn−1) ∈ Nn und GewichtsvektorW = (w0, . . . ,wn−1) ∈ Nn sowie eine Gewichtsobergrenze M ∈ N,d.h. I = (V ,W ,M).

Eine Losung ist ein binarer Verktor X = (x0, . . . , xn−1) ∈ 0, 1n. Gesucht ist ein Losungverktor X = (x0, . . . , xn−1) ∈ 0, 1n, so dass

val(I ,X ) :=∑n−1

i=0 vi · xi

unter der Nebenbedingung

∑n−1i=0 wi · xi ≤ M

maximal ist. xi = 1 bedeutet, dass das i-te Gut in den Rucksackaufgenommen wird. M gibt die maximale Belastung des Rucksacksan und

∑n−1i=0 wi · xi das aktuelle Gewicht.

104

Andreas Jakoby



6. Vorlesung, 28.11.2007

Algorithmus KS-ExhaustiveSearch(ℓ,Xopt, Vopt, Xakt, I )Eingabe: Instanz I = (V ,W , M), bisher beste Losung Xopt mit Wert

Vopt, neuer Losungsversuch Xakt = (xakt,0, . . . , xakt,n−1)Ergebnis: neue beste Losung Xneu mit Wert Vneu

1: if ℓ = n then2: if

∑n−1i=0 wi · xakt,i ≤ M then

3: Vakt :=∑n−1

i=0 vi · xakt,i4: if Vakt > Vopt then Vopt := Vakt; Xopt := Xakt end if5: end if6: else7: xakt,ℓ := 08: (Xopt, Vopt) :=KS-ExhaustiveSearch(ℓ + 1,Xopt,Vopt,Xakt, I )9: xakt,ℓ := 110: (Xopt, Vopt) :=KS-ExhaustiveSearch(ℓ + 1,Xopt,Vopt,Xakt, I )11: end if12: Return(Xopt,Vopt)

105

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beobachtung 6 KS-ExhaustiveSearch(0, (0, . . . , 0), 0, (0, . . . , 0), I ) findeteine optimale Losung fur das Rucksackproblem durch vollstandigesDurchsuchen des Losungsraumes. Wir nenne eine solche Suche nach eineroptimalen Losung exhaustive search.

Beobachtung 7 Da der Losungsraum 0, 1n exponentielle Große hat,und wir fur jeden Losungsvektor einmal die Summe in Zeile 3 vonKS-ExhaustiveSearch auswerten mussen, ist die Laufzeit vonKS-ExhaustiveSearch in O(n · 2n).

106

Andreas Jakoby



6. Vorlesung, 28.11.2007

5.2 Die allgemeine Backtracking-Strategie

Um die folgende allgemeine Backtracking-Strategie anwenden zu konnen,mussen wir die Form des Losungsraums einschranken:

X = X0 ×X1 × . . .×Xn wobei Xℓ fur alle ℓ endlich ist, d.h. derLosungsraum ist das kartesische Produkt von jeweils endlich vielenAlternativen Xℓ.

Cℓ ⊆ Xℓ bezeichnet eine moglichst kleine Auswahlmenge zubetrachtender Alternativen.

Mit Cℓ konnen wir versuchen die Alternativen einzuschranken.

107

Andreas Jakoby



6. Vorlesung, 28.11.2007

Wird die optimale Losung uber eine globale Variable festgehalten, dannkonnen wir die Beschreibung des Backtrackingalgorithmus erheblichvereinfachen:

Algorithmus Backtrack(ℓ, x1, . . . , xℓ−1)Eingabe: Tiefe ℓ ∈ N, partielle Losung (x1, . . . , xℓ−1)Ergebnis: optimale Losung (x1, . . . , xn−1) uber eine globale Variable

1: if x1, . . . , xℓ−1 ist eine zulassige Losung then2: bewerte x1, . . . , xℓ−1

3: else4: bestimme Cℓ

5: for all x ∈ Cℓ do Backtrack(ℓ + 1, x1, . . . , xℓ−1, x) end for6: end if

108

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel: Bei der Losung des Rucksackproblems konnen wir in manchenFallen eine Beschleunigung dadurch erzielen, dass wir das ℓ-te Gut nurdann zu einer partiellen Losung x0, . . . , xℓ−1 hinzufugen, wenn

wℓ +ℓ−1∑

i=0

xi · wi ≤ M

ist.

109

Andreas Jakoby



6. Vorlesung, 28.11.2007

Algorithmus KS-Backtrack(ℓ,Xakt,Vakt,Wakt)Eingabe: Instanz I = (V ,W , M), bisher beste Losung Xopt mit Wert

Vopt sind global gegeben, neuer LosungsversuchXakt = (xakt,0, . . . , xakt,n−1) mit Wert Vakt und Gewicht Wakt

Ergebnis: global gegeben neue beste Losung Xopt mit Wert Vopt

1: if ℓ = n then2: if Vakt > Vopt then Vopt := Vakt; Xopt := Xakt end if3: else4: if Wakt + wℓ ≤ M then Cℓ := 0, 1 else Cℓ := 0 end if5: for all x ∈ Cℓ do6: xakt,ℓ := x

7: KS-Backtrack(ℓ + 1,Vakt + x · vℓ,Wakt + x · wℓ)8: end for9: end if

110

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel: das Clique-Problem

Definition 10 [Clique-Problem]

Ein vollstandiger Graph Kℓ mit ℓ Knoten ist ein ungerichteter Graph,in dem es zwischen jedem Knotenpaar eine Kante gibt.

Gegeben ein ungerichteter Graph G = (V ,E ). Eine Clique von G istein vollstandiger Subgraph von G .

Wir betrachten die folgenden Probleme:

Gegeben ein ℓ ∈ N. Gibt es in G eine Clique der Große ℓ?

Bestimme das maximale ℓ ∈ N, so dass es in G eine Clique derGroße ℓ gibt.

Bestimme alle Cliquen in G .

Wir werden hier die dritte Variante untersuchen.

111

Andreas Jakoby



6. Vorlesung, 28.11.2007

Fur einen Knoten v definieren wir:

Γ(v) := u ∈ V | u, v ∈ E .

Wir gehen davon aus, dass die Knoten in G bezuglich einer Relation ≺vollstandig geordnet sind. Dann ist

B(v) := u ∈ V | v ≺ u .

Eine Liste von Elementen vi1 , . . . , vik bezeichnen wir mit

〈vi1 , . . . , vik 〉 .

Die leere Liste bezeichnen wir mit 〈〉. Um ein Element x hinten an dieListe L anzufugen benutzen den Operator :

〈vi1 , . . . , vik , x〉 := 〈vi1 , . . . , vik 〉 x

112

Andreas Jakoby



6. Vorlesung, 28.11.2007

Algorithmus Clique-Backtrack(ℓ,Xakt, Nℓ−1,G ,S)Eingabe: Instanz G , bisher gefundene Cliquen S , Knotenmengen Nℓ

neuer Versuch eine Clique zu finden Xakt = 〈xakt,0, . . . , xakt,ℓ−1〉Ergebnis: neue Menge von Cliquen S

1: S := S ∪ Xakt2: if ℓ = 0 then3: Nℓ := V und Cℓ := V

4: else5: Nℓ := Nℓ−1 ∩ Γ(xakt,ℓ−1) und Cℓ := Nℓ ∩ B(xakt,ℓ−1)6: end if7: if Nℓ = ∅ then Xakt ist eine maximale Clique end if8: for all x ∈ Cℓ do9: xakt,ℓ := x

10: S :=Clique-Backtrack(ℓ + 1,Xakt xakt,ℓ, Nℓ,G ,S)11: end for12: Return(S)

113

Andreas Jakoby



6. Vorlesung, 28.11.2007

Uber Induktion konnen wir zeige, dass

Cℓ =

V fur ℓ = 0Nℓ ∩ B(xakt,ℓ−1)

= B(xakt,ℓ−1) ∩⋂ℓ−1

i=0 Γ(xakt,i ) sonst.

Somit beschranken wir uns bei der Auswahl von xakt,ℓ auf solcheKnoten, die mit den Knoten in Xakt eine Clique bilden.

Da Nℓ =⋂ℓ−1

i=0 Γ(xakt,i ) ist die Clique genau dann maximal, wennNℓ = ∅ ist, d.h. Xakt kann um keinen Knoten aus V zu einergroßeren Clique erweitert werden.

114

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel: das Exact-Cover-Problem

Definition 11 [Exact-Cover-Problem]

Gegeben ist eine Menge S = S1, . . . ,Sm von Teilmengen Si ⊆ U

einer Grundmenge U.

Eine Auswahl Si1 , . . . ,Sik von Mengen aus S heißt exakteUberdeckung, wenn jedes Element aus U in genau einer Teilmengeder Auswahl Sij enthalten ist, d.h.

U =k⋃

j=1

Sij und |U| =k

∑

j=1

|Sij | .

Gegeben eine Instanz S = S1, . . . ,Sm, dann unterscheiden wirzwischen den folgenden Varianten des Exact-Cover-Problems:

Entscheide, ob eine exakt Uberdeckung existiert. Finde eine exakt Uberdeckung. Finde alle exakten Uberdeckungen.

115

Andreas Jakoby



6. Vorlesung, 28.11.2007

1. Losung: Das Exact-Cover-Problem konnen wir mit Hilfe desCliquen-Problems losen:

Fur eine Instanz S wir definieren einen Graphen G = (V , E ) wiefolgt:

V := S und E := Si ,Sj | Si ∩ Sj = ∅ .

Die maximale Cliquen stellen dann mogliche exakte Uberdeckungendar. Eine Clique Si1 , . . . ,Sik ist genau dann eine exakteUberdeckung, wenn

U =

k⋃

j=1

Sij .

Diese Idee fuhrt uns zum folgenden Algorithmus, der aufClique-Backtrack basiert. Sei U = 0, . . . , n − 1 und S := S1, . . . ,Sm,wobei S lexikographisch sortiert ist, d.h. fur alle i ∈ 0, . . . ,m − 2 giltSi ≤lex Si+1.

116

Andreas Jakoby



6. Vorlesung, 28.11.2007

Algorithmus XCover-Backtrack(ℓ,Xakt, C′ℓ−1, Uℓ−1, r

′,M)

Eingabe: bisher gefundene Uberdeckungen M, neuer Versuch eineUberdeckung zu finden Xakt = 〈xakt,0, . . . , xakt,ℓ−1〉

Ergebnis: neue Menge von Uberdeckungen M

1: if ℓ = 0 then2: U0 := 0, . . . , n − 1, r := 0, C ′0 := 0, . . . ,m − 13: else4: Uℓ := Uℓ−1 \ Sxℓ−1

, r := r ′, C ′ℓ := Γ(xℓ−1) ∩ B(xℓ−1) ∩ C ′ℓ−15: while r 6∈ Uℓ und r < n do r := r + 1 end while6: end if7: if r = n then M := M ∪ Xakt end if8: Cℓ := C ′ℓ ∩ H(r)9: for all x ∈ Cℓ do10: xakt,ℓ := x

11: M :=XCover-Backtrack(ℓ + 1, Xakt xakt,ℓ,C′ℓ,Uℓ, r ,M)

12: end for13: Return(M)

117

Andreas Jakoby



6. Vorlesung, 28.11.2007

In XCover-Backtrack gehen wir davon aus, dass Γ, B und H globalgegeben sind. Die Werte dieser Funktionen werden in der folgendenProzedur initialisiert:

Algorithmus ExactCover(n,S)Eingabe: Große n der Grundmenge U und sortierte Instanz SErgebnis: neue Menge aller Uberdeckungen S

1: m := |S|2: for i := 0 to m − 1 do Γ(i) := j |Si ∩ Sj = ∅ end for3: for i := 0 to m − 1 do B(i) := i + 1, . . . ,m − 1 end for4: for i := 0 to n − 1 do H(i) := j |Sj ∩ 0, 1, . . . , i = i end for5: H(n) := ∅6: M :=XCover-Backtrack(0, 〈〉, 0, . . . ,m − 1, 0, . . . , n − 1, 0, ∅)7: Return(M)

118

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel: Gegeben sei S := S0, S1, S2,S3, S4,S5,S6,S7 mit U = [0..10]und

S0 := 0, 1, 2, 8, 10 S1 := 0, 1, 8S2 := 2, 5, 8, 10 S3 := 2, 9, 10S4 := 3, 5, 7 S5 := 3, 5, 6, 10S6 := 4, 6 S7 := 5, 6, 7, 8

Wir erhalten

H(0) = 0, 1 H(1) = ∅H(2) = 2, 3 H(3) = 4, 5H(4) = 6 H(5) = 7H(6) = ∅ H(7) = ∅H(8) = ∅ H(9) = ∅

H(10) = ∅

119

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel (Teil 2)

Γ(0) = 4, 6 Γ(1) = 3, 4, 5, 6Γ(2) = 6 Γ(3) = 1, 4, 6, 7Γ(4) = 1, 3, 6 Γ(5) = 1Γ(6) = 0, 1, 2, 3, 4 Γ(7) = 3

S5

S7

S2S6S1

S3

S4 S0

120

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel (Teil 3) 1. Wurzel-Blatt-Pfad im Backtracking-Baum:

U0 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 r = 0C ′0 = 0, 1, 2, 3, 4, 5, 6, 7 C0 = 0, 1

↓ Xakt = 〈0〉U1 = 3, 4, 5, 6, 7, 9 r = 3C ′1 = 4, 6 C1 = 4

↓ Xakt = 〈0, 4〉U2 = 4, 6, 9 r = 4C ′2 = 6 C2 = 6

↓ Xakt = 〈0, 4, 6〉U3 = 9 r = 9C ′3 = ∅ C3 = ∅

121

Andreas Jakoby



6. Vorlesung, 28.11.2007

Beispiel (Teil 4) 2. Wurzel-Blatt-Pfad im Backtracking-Baum:

U0 = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 r = 0C ′0 = 0, 1, 2, 3, 4, 5, 6, 7 C0 = 0, 1

↓ Xakt = 〈1〉U1 = 2, 3, 4, 5, 6, 7, 9, 10 r = 2C ′1 = 3, 4, 5, 6 C1 = 3

↓ Xakt = 〈1, 3〉U2 = 3, 4, 5, 6, 7 r = 3C ′2 = 4, 6 C2 = 4

↓ Xakt = 〈1, 3, 4〉U3 = 4, 6 r = 4C ′3 = 6 C3 = 6

↓ Xakt = 〈1, 3, 4, 6〉U3 = ∅ r = 11 C ′3 = ∅ C3 = ∅ M = 〈1, 3, 4, 6〉

122

Andreas Jakoby



6. Vorlesung, 28.11.2007

5.3 Backtracking mit Bounding-Funktion

Fur ein Optimierungsproblem Q sei Y die Menge aller partiellenLosungen, d.h. jedes Element Y ∈ Y kann zu einer Losung X ∈ Xerweitert werden.

Definiere comp : Y → X wie folgt

comp(Y ) := X | Y kann zu X erweitert werden .

Fur ein Maximierungsproblem nennen wir eine Funktionbound : I × Y → R Bounding-Funktion, wenn fur alle I ∈ I, alleY ∈ Y und alle X ∈ comp(Y )

val(I ,X ) ≤ bound(I , Y )

ist.

123

Andreas Jakoby



6. Vorlesung, 28.11.2007

Somit kann keine Erweiterung von Y den Wert von bound(I ,Y )uberschreiten.

Liegt beim Backtracking bound(I , Y ) unter dem Wert des bishergefundenen Maximums, dann mussen wir die Erweiterungencomp(Y ) nicht mehr weiter untersuchen.

Mit Hilfe einer Bounding-Funktion konnen wir in vielen Fallen dasBacktracking erheblich beschleunigen.

Fur ein Minimierungsproblem nennen wir eine Funktionbound : I × Y → R Bounding-Funktion, wenn fur alle I ∈ I, alleY ∈ Y und alle X ∈ comp(Y )

val(I , X ) ≥ bound(I , Y )

ist.

124

Andreas Jakoby



6. Vorlesung, 28.11.2007

Algorithmus BoundedBacktrack(ℓ,X , Xopt,Vopt, I )Eingabe: Tiefe ℓ ∈ N, partielle Losung X := (x1, . . . , xℓ−1),

bisherige beste Losung Xopt mit Wert Vopt, Instanz I

Ergebnis: optimale Losung aus comp(X ) ∪ Xopt1: if X ist eine zulassige Losung then2: V := val(I ,X )3: if V > Vopt then Vopt := V ; Xopt := X end if4: end if5: bestimme Cℓ

6: for all x ∈ Cℓ do7: B := bound(I ,X x)8: if B > Vopt then9: (Xopt,Vopt) := BoundedBacktrack(ℓ + 1,X x , Xopt, Vopt, I )10: end if end for11: Return(Xopt,Vopt)

125

Andreas Jakoby



7. Vorlesung, 05.12.2007

Eine Bounding-Funktion fur das Rucksackproblem

In viele Fallen ist das finden einer sinnvollen Bounding-Funktion eineschwieriges Problem.

Betrachten wir das Rucksackproblem: Betrachten wir nun einmal den Fall, dass wir auch Anteile von einem

Gut in unseren Rucksack einpacken konnen. Hierbei hat der Anteil εmit 0 ≤ ε ≤ 1 von einem Gut j ein Gewicht von ε · wj und einenWert von ε · vj . Wir erhalten hierbei die rationale Variante desRucksackproblems.

Wir wahlen i , so dass der Quotient vi/wi maximal ist. Es gilt: Fur das Gewicht von wi konnen wir maximal den Wert vi

bekommen.

Diese Uberlegung fuhrt uns zu folgendem Algorithmus fur dierationale Variante des Rucksackproblems.

126

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus RationalesRucksack(n,V ,W ,M)Eingabe: Instanz (V ,W ,M) mit n GuternErgebnis: optimale Losung (x0, . . . , xn−1) ∈ [0; 1]n des Rucksack-

problems, wobei xi den Anteil vom i-ten Guts in der Losung ist.

1: sortiere die Guter nach dem Wert der Quotienten vi/wi

2: sei i0, . . . , in−1 die resultierende Folge der Guter3: for j := 0 to n − 1 do xj := 0 end for4: sei j := 0; V := 0; W := 05: while W ≤ M und j < n do6: if W + wwij

≤ M then

7: xij := 1; W := W + wij ; V := V + vij ; j := j + 18: else9: xij :=

M−Wwij

; W := M; V := V + xij · vij ; j := j + 1

10: end if11: end while12: Return((x0, . . . , xn−1))

127

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus BoundingRucksack(ℓ,Xakt, Vakt,Wakt)Eingabe: Instanz I = (V ,W , M), bisher beste Losung Xopt mit Wert

Vopt sind global gegeben, neuer LosungsversuchXakt = (xakt,0, . . . , xakt,n−1) mit Wert Vakt und Gewicht Wakt

Ergebnis: neue beste Losung Xopt mit Wert Vopt global gegeben

1: if ℓ = n then2: if Vakt > Vopt then Vopt := Vakt; Xopt := Xakt end if3: else4: if Wakt + wℓ ≤ M then Cℓ := 0, 1 else Cℓ := 0 end if5: for all x ∈ Cℓ do6: xakt,ℓ := x

128

Andreas Jakoby



7. Vorlesung, 05.12.2007

7: sei I ′ = (V ′,W ′,M −Wakt − x · wℓ) die Instanz I

8: eingeschrankt auf die Guter i > ℓ9: (x ′ℓ+1, . . . , x

′n−1) :=RationalesRucksack(n − ℓ− 1,

10: V ′,W ′, M −Wakt − x · wℓ)

11: B := Vakt + x · wℓ +∑n−1

i :=ℓ+1 x ′i · wi

12: if B > Vopt then13: BoundingRucksack(ℓ + 1, Xakt, Vakt + x · vℓ, Wakt + x · vℓ)14: end if15: end for16: end if

129

Andreas Jakoby



7. Vorlesung, 05.12.2007

5.4 Das Traveling Salesperson Problem

Definition 12 [Traveling Salesperson Problem (TSP)]

Gegeben ist ein ungerichteter Graph G = (V , E ) und eine Kosten-matrix M = (mi,j)i,j∈V , wobei mi,j =∞ fur i , j 6∈ E ist.2

Einen Hamiltonischer Kreis ist eine Knotenfolge v0, v1, . . . , vn,welcher jeden Knoten genau einmal besucht.

Die Kosten eines Kreises v0, . . . , vn definieren wir wie folgt:

cost(v0, . . . , vn−1) :=n−1∑

i :=0

mvi ,v(i+1) mod n.

Gesucht ist ein Hamiltonischer Kreis mit minimalen Kosten.

2Zur Vereinfachung bezeichnen wir die Knoten mit naturlichen Zahlen.

130

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus TSP-Backtrack(ℓ,Cℓ−1, Xakt,Xopt, Vopt)Eingabe: offene Knoten Cℓ−1, neuer Losungsversuch

Xakt = xakt,0, . . . , xakt,ℓ−1, bisher beste Losung Xopt mit Wert Vopt

Ergebnis: neue beste Losung Xopt mit Wert Vopt

1: if ℓ = n then2: Vakt := cost(Xakt)3: if Vakt < Vopt then Vopt := Vakt; Xopt := Xakt end if4: else5: if ℓ = 0 then Cℓ := 0 end if6: if ℓ = 1 then Cℓ := 1, . . . , n − 1 end if7: if ℓ > 1 then Cℓ := Cℓ−1 \ xakt,ℓ−1 end if8: for each xakt,ℓ ∈ Cℓ do9: (Xopt,Vopt) := TSP-Backtrack(ℓ + 1, Cℓ,Xakt xakt,ℓ,Xopt,Vopt)10: end for11: end if12: Return(Xopt,Vopt)

131

Andreas Jakoby



7. Vorlesung, 05.12.2007

1. Bounding-Funktion

Fur eine Knotenmenge W ⊆ V und ein Knoten x ∈ V sei

b(x , W ) := minw∈W

mx,w

die kostenminimale Verbindung von x zu einem Knoten der MengeW .

Fur einen Pfad X := x0, . . . , xℓ−1 in G sei X := V \ X und dieBounding-Funktion

BTSP(X ) :=

ℓ−2∑

i=0

mxi ,xi+1+

b(xℓ−1, X ) +∑

v∈X

b(v ,X ∪ x0) fur ℓ < n

mxℓ−1,x0 fur ℓ = n .

Da es fur jeden Knoten in X ∪ xℓ−1 einen Nachfolger auf demHamiltonischen Kreis geben muss, ist BTSP eine Bounding- Funktion,die die Lange jedes Hamiltonischen Kreises mit dem Teilpfad X nachunten beschrankt.

132

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus TSP-Bounding(ℓ,Cℓ−1, Xakt,Xopt,Vopt)Eingabe: offene Knoten Cℓ−1, neuer Losungsversuch

Xakt = xakt,0, . . . , xakt,ℓ−1, bisher beste Losung Xopt mit Wert Vopt

Ergebnis: neue beste Losung Xopt mit Wert Vopt

1: if ℓ = n then2: Vakt := cost(Xakt)3: if Vakt < Vopt then Vopt := Vakt; Xopt := Xakt end if4: else5: if ℓ = 0 then Cℓ := 0 end if6: if ℓ = 1 then Cℓ := 1, . . . , n − 1 end if7: if ℓ > 1 then Cℓ := Cℓ−1 \ xakt,ℓ−1 end if8: for each xakt,ℓ ∈ Cℓ mit Vopt ≥ BTSP(Xakt xakt,ℓ) do9: (Xopt,Vopt) := TSP-Bounding(ℓ + 1,Cℓ,Xakt xakt,ℓ,Xopt, Vopt)10: end for11: end if12: Return(Xopt,Vopt)

133

Andreas Jakoby



7. Vorlesung, 05.12.2007

2. Bounding-Funktion

Eine zweite Bounding-Funktion erhalten wir, indem wir die Eintrageder Kostenmatrix zunachst Spalten- und dann Zeilenweise um dasjeweilige Minimum der jeweiligen Spalte bzw. der Zeile verkleinern,und die Summe dieser Minima bestimmen. Sei redval diese Summe.

Die resultierende Matrix besitzt weiterhin nur positive Eintrage.Jedoch gibt es in jeder Zeile und in jeder Spalte mindesten eine 0.

Den Wert von redval konnen wir mit dem Algorithmus auf derfolgenden Folie bestimmen.

134

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus Redval(M)Eingabe: k × k-KostenmatrixErgebnis: Wert von redval

1: redval:= 02: for i := 0 do k − 1 do3: row:= minj∈[0..k−1] mi,j

4: for j := 0 to k − 1 do mi,j := mi,j−row end for5: redval:=redval+row6: end for7: for j := 0 do k − 1 do8: col:= mini∈[0..k−1] mi,j

9: for i := 0 to k − 1 do mi,j := mi,j−col end for10: redval:=redval+col11: end for12: Return(redval)

135

Andreas Jakoby



7. Vorlesung, 05.12.2007

Lemma 8 Jeder Hamiltonsche Kreis in einem Graphen G mitKostenmatrix M hat Kosten mindestens Redval(M).

Beweis von Lemma 34:

Markieren wir fur einen Hamiltonischen Kreis in der Kosten- matrixgenau die Kosten der Kanten des Kreises, so wird in jeder Zeile undin jeder Spalte genau ein Eintrag mi,j markiert.

Es kann gezeigt werden, dass die Summe dieser Werte mindestensden Wert Redval(M) haben muss.

Um die Bounding-Funktion zu berechnen, mussen wir die Kosten- matrixabhangig vom aktuellen Pfad modifizieren.

136

Andreas Jakoby



7. Vorlesung, 05.12.2007

Fur einen Pfad X := x0, . . . , xℓ−1 sei X := V \ X .

Sei MX die Teilmatrix der Kostenmatrix M, die nur aus den

Eintragen besteht, deren Zeilen und Spalten durch Knoten aus X

indiziert sind.

Wir indizieren die Zeilen und Spalten aus MX durch die jeweiligen

Knoten aus X .

X

XM M

X

137

Andreas Jakoby



7. Vorlesung, 05.12.2007

Jetzt fugen wir in MX noch eine Spalte und eine Zeile hinzu. Diesekonnen wir zum Beispiel and der Position von x0 tun.

In der neuen Zeile tragen wir die Kosten ein, um von dem jeweiligenKnoten aus X den Knoten x0 zu erreichen.

In der neuen Spalte tragen wir die Kosten ein, um von xℓ−1 denjeweiligen Knoten aus X zu erreichen.

An die Stelle, wo sich die neue Zeile und die neue Spalte schneiden,setzten wir ∞.

Sei M ′ die resultierende Matrix, dann setzten wir

BTSP2(X ) :=

ℓ−2∑

i=0

mxi ,xi+1+

Redval(M ′) fur ℓ < n

mxℓ−1,x0 fur ℓ = n .

138

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus BTSP2(X )Eingabe: ein Pfad X = x0, . . . , xℓ−1 in G

Ergebnis: ein Bounding-Wert

1: if ℓ = n then2: Return(cost(X ))3: else4: sei M ′ = (m′i,j)i,j∈[0..n−ℓ] eine n − ℓ + 1× n − ℓ + 1-Matrix5: sei m′0,0 :=∞; j := 1; i := 1

6: for all v ∈ X do m′0,j := mxℓ−1,v ; j := j + 1 end for

7: for all v ∈ X do m′i,0 := mv ,x0 ; i := i + 1 end for8: i := 09: for all u ∈ X do10: j := 1; i := i + 111: for all v ∈ X do m′i,j := mu,v ; j := j + 1 end for12: end for13: Return(

∑ℓ−2i=0 mxi ,xi+1

+ Redval(M ′))14: end if

139

Andreas Jakoby



7. Vorlesung, 05.12.2007

5.5 Das MAXCLIQUE Problem

Wir wollen nun das Problem untersuchen, die Große einer maximalenClique zu bestimmen.

Dieses Problem ist ebenfalls NP-schwierig. Ausgehend vom Algorithmus Clique-Backtrack

140

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus MAXCLIQUE(ℓ,Xakt, Cℓ−1,G , Vopt)Eingabe: Instanz G , bisher gefundene maximale Große einer Clique

Vopt, Knotenmengen Cℓ−1, neuer Versuch eine Clique zu findenXakt = 〈x0, . . . , xℓ−1〉

Ergebnis: maximale Große einer Clique

1: if ℓ = 0 then Cℓ := V else Cℓ := Cℓ−1 ∩ Γ(xℓ−1) ∩ B(xℓ−1) end if2: if Cℓ = ∅ then3: if ℓ > Vopt then Return(ℓ) else Return(Vopt) end if4: else5: for all x ∈ Cℓ do6: Vopt :=MAXCLIQUE(ℓ + 1, Xakt x , Cℓ,G ,Vopt)7: end for8: end if9: Return(Vopt)

141

Andreas Jakoby



7. Vorlesung, 05.12.2007

Welche Bounding-Funktion konnen wir fur das MAXCLIQUE Problemangeben?

Wir betrachten das Knotenfarbungsproblem fur den Restgraphen mitKnotenmenge Cℓ: Jeder Knoten des Graphen soll ein Farbebekommen, wobei benachbarte Knoten unterschiedlich gefarbtwerden mussen. Ziel ist es die Anzahl der Farben zu minimieren.

Besitzt ein Graph eine k-Farbung, so besitzt der Graph keine Cliqueder Große k + 1!

Das Farbungsproblem ist NP-schwierig. Daher suchen wir nach einem Greedy-Verfahren, welches die

Farbung gut approximiert.

142

Andreas Jakoby



7. Vorlesung, 05.12.2007

Sei V = 0, . . . , n − 1 die betrachtete Knotenmenge fur dasFarbungsproblem.

Sei N bzw. [0..k − 1] die Menge der Farben.

Fur eine Farbe h ist CClass[h] die Menge der Knoten mit Farbe h.

Fur einen Knoten v ist Color[v ] die Farbe von v .

143

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus Greedy-Color(G )Eingabe: Graph G

Ergebnis: Obere Schranke fur die Anzahl der Farben k

1: k := 02: for v = 0 to n − 1 do3: h := 04: while h < k und CClass[h] ∩ Γ(v) 6= ∅ do h := h + 1 end while5: if h = k then k := k + 1; CClass[h] := ∅ end if6: CClass[h] :=CClass[h] ∪ v7: Color[v ] := h

8: end for9: Return(k)

144

Andreas Jakoby



7. Vorlesung, 05.12.2007

Man kann Beispiele finden, bei denen Greedy-Color nicht dieoptimale Farbung findet.

Besitzt ein Graph einen maximalen Grad von d , d.h. |Γ(v)| ≤ d furalle Knoten des Graphen, dann findet der Algorithmus eine Farbungmit d + 1 Farben.

Berechnen wir in MAXCLIQUE fur jeden GraphenGℓ = (Cℓ, E ∩ 2Cℓ) mit Greedy-Color eine obere Schranke kℓ fur dieminimale Anzahl an benotigten Farben, so erhalten wir hierbei aucheine obere Schranke fur die maximale Große kℓ einer Clique in Gℓ.

Die maximale Große einer Cliquen die wir ausgehend von Xakt findenkonnen ist dann

Xakt + Greedy-Color(Gℓ) .

145

Andreas Jakoby



7. Vorlesung, 05.12.2007

5.6 Branch-and-Bound Verfahren

Mit Hilfe einer gegebenen Bounding-Funktion versuchen wir dieReihenfolge beim Traversieren des Backtracking-Baums so zumanipulieren, dass wir einige Losungskandidaten zusatzlichausschließen konnen.

Fur ein Maximierungsproblem sortieren wir Cℓ absteigend inAbhangigkeit vom Wert der Bounding-Funktion. Wir betrachtenanschließend die Elemente aus Cℓ entsprechend der erhaltenenReihenfolge.

Erhalten wir fur ein Elemente aus Cℓ eine Losung, deren Wert naheam Wert der Bounding-Funktion liegt, dann konnen wir alleElemente aus Cℓ, fur die die Bonding-Funktion einen kleineren Wertliefert, als Kandidaten fur eine optimale Losung ausschießen.

146

Andreas Jakoby



7. Vorlesung, 05.12.2007

Algorithmus BranchAndBound(ℓ,X ,Xopt, Vopt, I )Eingabe: Tiefe ℓ ∈ N, partielle Losung X := (x1, . . . , xℓ−1),

bisherige beste Losung Xopt mit Wert Vopt, Instanz I

Ergebnis: optimale Losung aus comp(X ) ∪ Xopt1: if X ist eine zulassige Losung then2: V := val(I ,X )3: if V > Vopt then Vopt := V ; Xopt := X end if4: end if5: bestimme Cℓ und Fℓ = (x , bound(I ,X x))|x ∈ Cℓ6: sortiere Fℓ absteigend nach der zweiten Koordinate7: sei Fℓ[1], . . . ,Fℓ[k] die resultierende sortierte Folge8: for i = 1 to k do9: Sei (x , B) := Fℓ[i ]10: if B ≤ Vopt then Return(Xopt, Vopt) end if11: (Xopt,Vopt) := BranchAndBound(ℓ + 1, X x , Xopt,Vopt, I )12: end for13: Return(Xopt,Vopt)

147

Andreas Jakoby



7. Vorlesung, 05.12.2007

6 2-Personen-Spielen6.1 Typen von 2-Personen-Spielen

Eine weitere Form von Optimierungsproblemen finden wir bei2-Personen-Spielen:

Ein Spiel, bei dem 2 Speiler abwechselnd Zuge aus einervorgegebenen Menge von endlich vielen Alternativen wahlen, kanndurch einen Spielbaum beschrieben werden.

Jeder Knoten reprasentiert eine Spielstellung und jede Kante einenSpielzug.

Die Kanten zu den Kinder eines Knoten reprasentieren jeweils einemalternativen Zug.

Der Spielbaum eines solchen 2-Personen-Spiels stellt eineVerallgemeinerung eines Losungsbaums eines Optimierungs-problems (Aufrufbaums des Backtrackingverfahrens) dar.

148

Andreas Jakoby



7. Vorlesung, 05.12.2007

Bei 2-Personen-Spielen unterscheiden wir zwischen Speilen mit

Zufallsentscheidungen, wie zum Beispiel mit Wurfeln oder mitDurchmischen von Karten, und deterministischen Spielen,

Spielen mit unvollstandiger Information, wie zum Beispielenverdeckte Karten, und Spielen mit vollstandiger Information, wiezum Beispiel Schach, Dame oder Go.

Bei einem Nullsummenspiel ist der Gewinn des einen Spielerzugleich der Verlust des anderen Spielers.

Jede Endstellung des Speils konnen wir mit einer Zahl bewerten, dieangibt, welchen Betrag der erste Spieler dem zweiten zu zahlen hat.

Bei einem Spiel mit nur einfachen Gewinn- oder Verlustbedingungenkonnen wir diese Bewertung mit +1 fur Gewinn, −1 fur Verlust und0 fur Unentschieden durchfuhren.

149

Andreas Jakoby



7. Vorlesung, 05.12.2007

6.2 Alpha-Beta-Suche bei 2-Personen-Spielen

Da wir einen exponentiell großen Spielbaum in der Regel nichtvollstandig durchsuchen konnen, suchen wir nach geeignetenheuristischen Verfahren, mit deren Hilfe wir uninteressanteTeilbaume erkennen und somit aussparen konnen.

Diese entspricht der Funktionsweise einer Bounding-Funktion beimBacktracking.

Bei 2-Personen-Spielen benotigen wir allerdings 2 Werte: eine α-Schranke, fur den maximalen Gewinn, den Spieler 1 aus dieser

Spielstellung heraus erzielen kann, und eine β-Schranke, fur den maximalen Gewinn, den Spieler 2 aus dieser

Spielstellung heraus erzielen kann.

Bei einem Nullsummenspiel entspricht der maximale Gewinn deseinen Spielers dem maximalem Verlust des zweiten Spielers.

150

Andreas Jakoby



7. Vorlesung, 05.12.2007

Die α- und β-Schranke werden aus den Werten der Vorgangerknotendurch Maximieren oder Minimieren berechnet, je nach dem Spieler,der am Zug ist.

Wir sprechen von einem α-Schnitt, wenn eine Spielstellung, woSpieler 1 am Zug ist, nicht weiter betrachtet wird, weil der Gegnergarantiert nicht in diese Spielstellung ziehen wurde, weil er durcheine Alternative eine bessere Schranke erzielen kann.

Das duale mit vertauschten Rollen der Spieler nennen wir β-Schnitt.

Eine weitere Betrachtung von 2-Personen-Spielen wurde denRahmen dieser Vorlesung sprengen.

151

Andreas Jakoby



8. Vorlesung, 12.12.2007

7 HeuristikenIm 5-ten Kapitel haben wir verschiedene Bounding-Funktionenbetrachtet. Eine Bounding-Funktion stellte eine Art von Approximationeines Optimierungsproblems dar und vice versa. Eine Kollektionverschiedener Approximationen sind unter dem Namen Heuristikenbekannt. Einige bekannte Heuristiken sind:

Local Search,

Hill-Climbing,

Simulated Annealing,

Tabu-Search, und

Genetic Algorithmen.

Im Folgenden wollen wir auf einige wesentliche Ideen von Local SearchAlgorithmen eingehen.

152

Andreas Jakoby



8. Vorlesung, 12.12.2007

7.1 Local Search

Ein Local Search Algorithmus ist ein Verfahren, welches denLosungsraum durchsucht, in dem es von einer aktuellen Losung zueiner neuen Losung geht, welche sich in der Nachbarschaft befindet.

Local Search Heuristiken finden oft ihre Anwendung bei Problemen,die nur mit großem Berechnungsaufwand exakt gelost werdenkonnen.

Ein Nachteil von Local Search Heuristiken ist die Schwierigkeit ihrerAnalyse.

Fur einige Local Search Heuristiken sind keine bewiesenenApproximationsaussagen bekannt.

153

Andreas Jakoby



8. Vorlesung, 12.12.2007

Local Search und physikalische Systeme

Viele Local Search Algorithmen wurden durch physikalische Systemeinspiriert: Bei einem Minimierungsproblem versuchen wir eine Großezu minimieren. In einem physikalischen System wird fortwahrendeine Minimierung der potentiellen Energie durchgefuhrt.

Z.B. rollt ein Ball immer bergab.

B

C

A Betrachte einen Ball, der in A startet.

Position B ist ein lokales Minimum. B istder tiefste Punkt, wenn wir dieNachbarschaft von B betrachten.

Der Ball wird das globale Minimum in derPosition C nie erreichen.

Ein weiteres System mit potentialerEnergie stellt ein erhitzte Flussigkeit dar,die sich abkuhlt und dabei denAggregatzustand wechselt. Dieses fuhrtuns zur statistischen Mechanik.

154

Andreas Jakoby



8. Vorlesung, 12.12.2007

Verwandschaft zu Optimierungsproblemen

Physikalische Systeme

große Anzahl moglicherZustande

Energie der einzelnenZustande

minimiere die Energie

benachbarte Zustande

Optimierungsprobleme

große (exponentielle) Anzahlmoglicher Losungen C

Kostenfunktion c(S) furjede Losung S

minimiere/maximiere dieKosten

Neu: Nachbarschaftsrelation ∼Kommentare:

Fur zwei S ,S ′ benachbarte Losungen S .S ′ schreiben wir S ∼ S ′.

Die Nachbarschaftsrelation definiert einen (ungerichteten) Graphaller moglichen Losungen.

Die Nachbarschaft eines Zustands definieren wir durchN(S) = S ′|S ∼ S ′.

Die Kostenfunktion ist ein Teil der Problembeschreibung. DieNachbarschaftsrelation konnen wir frei wahlen.

155

Andreas Jakoby



8. Vorlesung, 12.12.2007

Basisstrategie fur Local Search Algorithmen:

1: Sei S ∈ C die gegenwartige Losung.2: iterate wahle S ∈ N(S)3: merke die jeweilige Losung mit minimalen Kosten4: Return(S)

Kommentare:

Local Search findet immer besser und bessere Losungen.

Local Search Algorithmen durchlaufen Wege in dem durch ∼definierten Graphen dar, die versuchen in Richtung einer gutenLosung zu gehen.

156

Andreas Jakoby



8. Vorlesung, 12.12.2007

7.2 Anwendung: Neuronale Hopfield Netzwerke

Definition 13 [Neuronale Hopfield Netzwerke]

Gegeben ist ein ungerichteter Graph G = (V , E ) und eineKanten-Gewichtsfunktion w : E → Z \ 0. Fur e ∈ E schreiben wirwe := w(e).

Eine Konfiguration S : V → −1,+1 ist eine Zuweisung der Werte−1 und +1 fur die Knoten in G . Fur v ∈ V schreiben wir auchsv := S(v) und nennen sv den Zustand von v .

Eine Kannte e = u, v muss die folgende Bedingung erfullen: Istwe > 0 dann ist die Bedingung erfullt, wenn u und v unterschiedlicheZustande haben. Ist we < 0 dann ist die Bedingung erfullt, wenn u

und v gleiche Zustande haben. Somit gilt we · su · sv ≤ 0.

|we | nennen wir das absolute Gewicht von e.

157

Andreas Jakoby



8. Vorlesung, 12.12.2007

Beispiel

11

1

Ein neuronalesHopfield Netzwerk,in dem mindestenszwei Knoten dieBedingung nichterfullen.


Gegeben ist eine Konfiguration S . EineKante e = u, v nennen wir schlecht,wenn sie die Bedingung verletzt, d.h.we · su · sv > 0. Ansonsten nennen wir e

gut.

Ein Knoten u ist stabil in S wenn∑

e=u,v∈E

we · su · sv ≤ 0 .

Eine Konfiguration S ist stabil wenn alleKnoten in S zufriedengestellt sind.

Finde eine stabile Konfiguration.

Hat jedes neuronales Hopfield Netzwerk eine stabile Konfiguration?Betrachten wir die gerichtete Variante dieses Problems, so erkennen wir,dass der obige Graph keine stabile Konfiguration besitzt, wenn wir alleKanten im Uhrzeigersinn richten.

158

Andreas Jakoby



8. Vorlesung, 12.12.2007

Algorithmus Hopfield-1(G ,w)Eingabe: neuronales Hopfield Netzwerk G und Gewichtsfunktion w

Ergebnis: stabile Konfiguration

1: for all v ∈ V do sv := +1 end for2: while S ist keine stabile Konfiguration do3: wahle einen nicht stabilen Knoten u

4: andere den Zustand von u, d.h. su := −su5: end while6: Return(S)

Beobachtung 8 Wenn Hopfield-1(G ,w) terminiert, dann ist dasErgebnis eine stabile Konfiguration.

Fragen: Halt Hopfield-1(G , w) immer an? Wenn ja, wie schnellterminiert Hopfield(G ,w)?

159

Andreas Jakoby



8. Vorlesung, 12.12.2007

Beispiel: Fur rote Knoten u sei su = +1 und fur blaue Knoten u seisu = −1. Grune Knoten u sind stabil.

8 −4

−10

−1 −1

8 −4

−10

−1 −1

2 6

1−1

−12

8 −4

−10

−1 −1

−4

−10

−1 −1

8

1−1

−18 −6

−4

8 −4

−10

−1 −1

−10

−1 −1

8 −4

−1

−18 −6

−5

−1

160

Andreas Jakoby



8. Vorlesung, 12.12.2007

Wahlen wir c : C → R als die zu maximierende Kostenfunktion, dannkonnen wir Hopfield-1(G ,w) so modifizieren, dass er die Form einesLocal Search Algorithmus hat.

Fur eine Konfiguration S und einen Knoten u sei g(S) die Menge der guten Kanten in G , sei g(S , u) die Menge der guten Kanten inzident zu u und sei b(S , u) die Menge der schlechten Kanten inzident zu u.

Das Gewicht dieser Mengen definieren wir wie folgt:

c(S) :=∑

e∈g(S)

|we |

und

γ+S (u) :=∑

e∈g(S,u)

|we | und γ−S (u) :=∑

e∈b(S,u)

|we | .

161

Andreas Jakoby



8. Vorlesung, 12.12.2007

Beobachtung 9 Seien S ,S ′ zwei Konfigurationen, wobei S ′ durch dasandern des Zustands eines Knotens u aus S entsteht, dann gilt

c(S ′) := c(S)− γ+S (u) + γ−S (u) .

Beobachtung 10 Sei S eine Konfiguration und u ein nicht stabilerKnoten in S , dann gilt su = γ−S (u)− γ+S (u) > 0 und somit

γ−S (u) > γ+S (u)

Beobachtung 11 Seien S ,S ′ zwei Konfigurationen, wobei S ′ durch dasandern des Zustands eines nicht stabilen Knotens u aus S entsteht, danngilt

c(S ′) > c(S) .

Somit erhoht sich der Wert der Kostenfunktion bei jedemSchleifendurchlauf in Hopfield-1(G , w).

162

Andreas Jakoby



8. Vorlesung, 12.12.2007

Wir definieren die Nachbarschaft einer Konfiguration S wie folgt

N(S) := S ′ | Konfiguration S ′ kann durch das andern desZustands eines Knotens generiert werden .

Wir erhalten den folgenden modifizierten Algorithmus:

Algorithmus Hopfield-2(G ,w)Eingabe: neuronales Hopfield Netzwerk G und Gewichtsfunktion w

Ergebnis: stabile Konfiguration

1: for all v ∈ V do sv := +1 end for2: while ∃S ′ ∈ N(S) : c(S ′) > c(S) do3: wahle eine Konfiguration S ′ ∈ N(S) mit c(S ′) > c(S)4: sei S := S ′

5: end while6: Return(S)

163

Andreas Jakoby



8. Vorlesung, 12.12.2007

In jeder Wiederholung der while-Schleife erhoht sich der Wert von c(S)um mindestens 1. Der maximale Wert von c(S) ist

∑

e∈E |we |. Da wirjeden Schleifendurchlauf in Zeit O(|E |) im Wortmodel3 durchfuhrenkonnen, gilt:

Satz 9 Hopfield-2(G , w) gibt eine stabile Konfiguration fur einneuronales Hopfield Netzwerk G = (V ,E ) mit Gewichtenw : E → Z \ 0 in Zeit O(|E | ·∑e∈E |we |) aus.

Beachte, dass fur große Werte we die Laufzeit von Hopfield-2(G ,w)exponentiell sein kann.

3Operationen auf ganzen Zahlen haben einen Zeitbedarf von einer Einheit im Wort-model

164

Andreas Jakoby



9. Vorlesung, 19.12.2007

7.3 Maximum-Cut Approximation via Local Search

Wir wollen nun ein Optimierungsproblem analysieren, welches mit Hilfeeines Local Search Algorithmus approximiert werden kann.

Definition 13 [Maximum-Cut Problem]

Gegeben ist ein ungerichteter Graph G = (V , E ) und eine positiveganzzahlige Gewichtsfunktion w : E → N. Fur e ∈ E schreiben wirwe := w(e).

Gegeben eine Partition A, B der Knotenmenge, dann definieren wir

w(A, B) =∑

e=(u,v)∈E mit u∈A,v∈B

we .

Finde eine Partition A,B welche w(A,B) maximiert.

Die Entscheidungsproblemvariante dieses Problem definieren wir wiefolgt: Gegeben G ,w und eine Schranke β, entscheide, ob einePartition A, B mit w(A, B) ≥ β existiert.

Die Entscheidungsproblemvariante von Maximum-Cut ist NP-vollstandig.

165

Andreas Jakoby



9. Vorlesung, 19.12.2007

Kommentare:

Nicht verwechseln: Minimum-Cut ist in P — dieses Problem wird imweiteren Verlauf dieses Kurses untersucht.

Das Maximum-Cut Problem kann als die Optimierungsproblem-variante des Problems verstanden werden, eine neuronales HopfieldNetzwerks mit positiven Kantengewicht verstanden werden:

Eine Konfiguration S korrespondiert wie folgt zu einer PartitionAS , BS : Ein Knoten u ist genau dann in AS , wenn su = −1 und u istgenau dann in BS , wenn su = +1.

Das Maximum-Cut Problem ist das Problem die Summe derabsoluten Werte aller guten Kanten zu maximieren, d.h. maximierec(S) = w(AS , BS).

Eine Teilmenge C ⊆ V und ein Knoten u definieren wir

w(u,C ) :=∑

e=u,v∈E mit v∈C

we .

166

Andreas Jakoby



9. Vorlesung, 19.12.2007

Basierend auf unseren Beobachten auf der letzten Folie konnen folgendenAlgorithmus fur das Maximum-Cut Problem herleiten:

Algorithmus ApproxMaxCut(G ,w)Eingabe: ungerichteter Graph G = (V ,E ) mit Gewichtsfunktion w

Ergebnis: Knotenpartition A, B

1: A := ∅; B := V

2: while (∃u ∈ A : w(u,B) < w(u,A)) ∨ (∃u ∈ B : w(u,A) < w(u,B)) do3: sei u ein Knoten, der die Bedingung in Zeile 2 erfullt4: if u ∈ A then A := A \ u; B := B ∪ u5: else B := B \ u; A := A ∪ u enf if6: end while7: Return(A,B)

Beachte, dass ApproxMaxCut(G ,w) dem Algorithmus Hopfield-2(G , w)entspricht.

167

Andreas Jakoby



9. Vorlesung, 19.12.2007

Satz 10 Sei A,B das Ergebnis von ApproxMaxCut(G ,w) und sei A∗,B∗

eine optimale Losung fur das Maximum-Cut Problem. Dann gilt

2 · w(A, B) ≥ w(A∗,B∗) .

Beweis von Satz 10: Zur Vereinfachung der Notation definiere

wE :=∑

e∈E

we und wuv := wu,v

und fur u, v 6∈ E

wuv := 0 .

Es gilt: Fur alle u ∈ A gilt

∑

v∈A

wuv ≤∑

v∈B

wuv

(ansonsten bewegen wir u nach B) und fur alle u ∈ B gilt∑

v∈B

wuv ≤∑

v∈A

wuv .

168

Andreas Jakoby



9. Vorlesung, 19.12.2007


Wir bilden die Summe der beiden Seiten der obigen Ungleichungenuber alle u ∈ A bzw. u ∈ B:

2 ·∑

u,v⊆A

wuv =∑

u,v∈A

wuv ≤∑

u∈A,v∈B

wuv = w(A,B)

bzw.

2 ·∑

u,v⊆B

wuv =∑

u,v∈B

wuv ≤∑

u∈B,v∈A

wuv = w(A,B) .

Der Faktor 2 auf der rechten Seite resultiert davon, dass wir jedeKante zweimal erhalten.

Wir addieren nun die beiden linken und rechten Seiten dieserUngleichungen:

2 ·∑

u,v⊆A

wuv + 2 ·∑

u,v⊆B

wuv ≤ 2 · w(A, B) .

169

Andreas Jakoby



9. Vorlesung, 19.12.2007

Proof of Theorem 10 (Part 3):

Wir haben∑

u,v⊆A

wuv +∑

u,v⊆B

wuv ≤ w(A,B)

und somit

∑

u,v⊆A

wuv +∑

u,v⊆B

wuv + w(A, B) ≤ 2 · w(A, B) .

Die linke Seite dieser Ungleichung entspricht der Summe uber allewe uber alle Kanten e in G . Wir erhalten

w(A∗,B∗) ≤ wE ≤ 2 · w(A,B) .

170

Andreas Jakoby



9. Vorlesung, 19.12.2007

Die Laufzeit von ApproxMaxCut:

Da ApproxMaxCut aquivalent zu Hopfield-2 ist, ist auch die Laufzeitvon ApproxMaxCut in O(|E | ·W ).

Ist W groß (ist die Lange der binaren Kodierung linear in G ), dannist die Laufzeit von ApproxMaxCut exponentiell in |V |.

Im Folgenden wollen wir ApproxMaxCut so modifizieren, dass dieLaufzeit in O(ε−1 · |E | · logW ) fur ε > 0 ist. Wir erkaufen diesesuber eine Approximationsgute von 2 + ε.4

4Beachte: Eine solche Approximation konnen wir benutzen um eine Bounding Funk-tion zu generieren wie sie im Kapitel 5 diskutiert haben: Bestimme die Partition A, B

und den Wert w(A, B). Dann ist (2+ ε) ·w(A, B) eine obere Schranke fur die optimaleLosung.

171

Andreas Jakoby



9. Vorlesung, 19.12.2007

Wir nenne eine Modifikation der Mengen A und B in der while-Schleifevon ApproxMaxCut ein Big-Improvement-Flip, wenn fur die resultierendePartition A′,B ′ gilt

w(A,B) +2 · ε|V | · w(A,B) ≤ w(A′,B ′) .

Wir betrachten nun nur noch Big-Improvement-Flips im modifiziertenAlgorithmus, d.h. wir addieren 2·ε

|V | · w(A,B) auf jede linkte Seite einer

Ungleichung in Zeile 2 von ApproxMaxCut.

172

Andreas Jakoby



9. Vorlesung, 19.12.2007

Algorithmus ApproxMaxCut-2(G , w , ε)Eingabe: ungerichteter Graph G = (V ,E ) mit Kantengewichtsfunktion w

undApproximationsparameter ε > 0

Ergebnis: Kontenpartition A, B

1: A := ∅; B := V

2: while (∃u ∈ A : w(u,B) + 2·ε|V | · w(A, B) < w(u,A))

3: oder (∃u ∈ B : w(u,A) + 2·ε|V | · w(A, B) < w(u,B)) do

4: sei u ein Knoten, der die Bedingung in Zeile 2 oder 3 erfullt5: if u ∈ A then A := A \ u; B := B ∪ u6: else B := B \ u; A := A ∪ u enf if7: end while8: Return(A,B)

173

Andreas Jakoby



9. Vorlesung, 19.12.2007

Satz 11 Sei A,B das Ergebnis von ApproxMaxCut(G ,w , ε) und seiA∗,B∗ eine optimale Losung fur das Maximum-Cut Problem. Dann gilt

(2 + ε) · w(A,B) ≥ w(A∗, B∗) .

Beweis von Satz 11: Der Beweis erfolgt analog zum Beweis von Satz10. Wir mussen nur den Term 2·ε

|V | · w(A,B) (bzw. Vielfache dieses

Terms) auf der rechten Seite der Ungleichungen addieren.

Fur alle u ∈ A gilt

∑

v∈A

wuv ≤ 2 · ε|V | · w(A, B) +

∑

v∈B

wuv

(ansonsten bewegen wir u nach B) und fur alle u ∈ B gilt

∑

v∈B

wuv ≤ 2 · ε|V | · w(A,B) +

∑

v∈A

wuv .

174

Andreas Jakoby



9. Vorlesung, 19.12.2007


Summieren wir beide Seiten dieser Ungleichungen uber alle u ∈ A

bzw. alle u ∈ B so erhalten wir

2 ·∑

u,v⊆A

wuv =∑

u,v∈A

wuv ≤ 2 · ε · |A||V | · w(A, B) +

∑

u∈A,v∈B

wuv

=2 · ε · |A||V | · w(A, B) + w(A,B)

2 ·∑

u,v⊆B

wuv =∑

u,v∈B

wuv ≤ 2 · ε · |B||V | · w(A,B) +

∑

u∈B,v∈A

wuv

=2 · ε · |B||V | · w(A,B) + w(A,B) .

175

Andreas Jakoby



9. Vorlesung, 19.12.2007


Addieren wir jeweils die linken und die rechten Seiten dieserUngleichungen, dann erhalten wir

2·∑

u,v⊆A

wuv+2·∑

u,v⊆B

wuv ≤ 2 · ε · (|A|+ |B|)|V | ·w(A, B)+2·w(A, B) .

bzw.∑

u,v⊆A

wuv +∑

u,v⊆B

wuv ≤ (1 + ε) · w(A,B)

und somit∑

u,v⊆A

wuv +∑

u,v⊆B

wuv + w(A,B) ≤ (2 + ε) · w(A,B) .

Die linke Seite dieser Ungleichung entspricht der Summe uber allewe uber alle Kanten e in G . Wir erhalten

w(A∗, B∗) ≤ wE ≤ (2 + ε) · w(A,B) .

176

Andreas Jakoby



9. Vorlesung, 19.12.2007

Satz 12 Die Laufzeit von ApproxMaxCut-2(G ,w , ε) ist maximalO(ε−1 · |V | · |E | · log2 W ).

Beweis von Satz 12:

Jede Modifikation einer Permutation andert w(A, B) um einenFaktor von mindestens (1 + ε

|V | ).

Da (1 + 1n)n ≥ 2 ist, erhalten wir

(

1 +ε

|V |

)|V |/ε

≥ 2 .

Wir verdoppeln somit das Gewicht der Partition in |V |ε

Schleifendurchlaufen.

Da das maximale Gewicht W ist, konnen wir das Gewicht einerPartition maximal logW mal verdoppeln.

Folglich wird die while-Schleife maximal |V |·logW

ε mal wiederholt.

177

Andreas Jakoby



9. Vorlesung, 19.12.2007

7.4 Anwendung: Vertex Cover

Abschließend werden wir nun noch das Vertex Cover Problemuntersuchen.

Definition 14 [Vertex Cover Problem]

Gegeben ist ein ungerichteter Graph G = (V , E ). Eine TeilmengeS ⊆ V ist ein Knotenuberdeckung fur G wenn fur alle Kantenu, v ∈ E gilt u, v ∩ S 6= ∅.

Finde eine Teilmenge S ⊆ V minimaler Kardinalitat, welche eineKnotenuberdeckung von G darstellt.

Unter der Entscheidungsvariante fur dieses Problem verstehen wirdas folgende Problem: Gegeben G und eine Schranke β, entscheide,ob es eine Knotenuberdeckung S von G mit |S | ≤ β gibt.

Die Entscheidungsvariante des Vertex Cover Problems istNP-vollstandig.

178

Andreas Jakoby



9. Vorlesung, 19.12.2007

Aus der obigen Definition konnen wir die folgenden Punkte herleiten:

Die Menge der moglichen Losungen C ist die Menge allerTeilmengen S ⊆ V die eine Knotenuberdeckung von G darstellen.

Die Kostenfunktion ist die Große der Knotenuberdeckung, d.h. furalle S ∈ C gilt c(S) := |S |.

Eine erste Analyse fuhrt uns zu der folgenden Nachbarschafts-relation: S ∼ S ′, wenn S ′ aus S durch das Loschen oder Hinzufugeneines einzelnen Knotens generiert werden kann.

Beobachtung 12 Jede Knotenuberdeckung S hat maximal |V |Nachbarn, i.e. |N(S)| ≤ |V |.Beobachtung 13 V ist eine Knotenuberdeckung fur G = (V ,E ).

179

Andreas Jakoby



9. Vorlesung, 19.12.2007

Benutzen wir die Notation der letzten Folie, dann erhalten wir denfolgenden Local Search Algorithmus:

Algorithmus VertexCover(G )Eingabe: ungerichteter Graph G = (V ,E )Ergebnis: Knotenuberdeckung S fur G

1: S := V

2: while ∃S ′ ∈ N(S) : c(S ′) < c(S) do3: sei S ′ ∈ N(S) eine Knotenuberdeckung fur G mit c(S ′) < c(S)4: sei S := S ′

5: end while6: Return(S)

Beobachtung 14 Innerhalb der while-Schleife wird niemals ein Knotenzur Menge S hinzugefugt. Erreicht der Algorithmus ein lokales MinimumS , so stoppt die Berechnung und das Minimum wird ausgegeben.

180

Andreas Jakoby



9. Vorlesung, 19.12.2007

Wir wollen nun die Arbeitsweise von VertexCover(G ) auf einigenspeziellen Graphen analysieren:

Besitz G keine Kante, dann ist die optimale Losung fur das VertexCover Problem die leere Menge. Diese Losung wird in |V |Iterationen der while-Schleife erreicht.

Ist G der vollstandige Graph, dann ist die optimale Losung fur dasVertex Cover Problem V \ v fur alle v ∈ V . Da fur alle v ∈ V

N(V \ v) = V ist, erreicht unser Algorithmus diese Losung mitnur einem Schleifendurchlauf.

Ist G der Sterngraph, dann ist esmoglich, dass unser Algorithmuszunachst das Zentrum des Sternsloscht. Nach einem solchen Schrittkonnen wir eine optimale Losungnur noch um einen Faktor von|V | − 1 approximieren.

z

181

Andreas Jakoby



9. Vorlesung, 19.12.2007

Aus unseren Beobachtungen auf Folie 181 konnen wir die folgendenFolgerungen ableiten:

Fur einige Probleme scheint es notig zu sein, dass wir aufwendigereNachbarschaftsrelationen benutzen, z.B. addiere oder losche einekonstante Anzahl von Knoten.

Fur einige Probleme kann es hilfreich sein, einen Weg aus einemlokalen Optimum zu finden. Fur ein Minimierungsproblem kann esbesser sein zeitweise auch Losungen mit hoheren Kosten zuakzeptieren. Analog, fur ein Maximierungsproblem kann es bessersein zeitweise auch Losungen mit niedrigeren Kosten zu akzeptieren.

182

Andreas Jakoby



9. Vorlesung, 19.12.2007

7.5 Der Metropolis Algorithm und Simulated Annealing

Um aus einem lokalem Optimum heraus zu kommen wurde 1953 vonMetropolis, Rosenbluth, Rosenbluth, Teller und Teller ein Verfahrenvorgestellt, welches ein physikalisches System entsprechend denPrinzipien der statistischen Mechanik simuliert:

Die Wahrscheinlichkeit das wir ein physikalischen System in einemZustand mit Energie E zu finden, ist proportional zurGibbs-Boltzmann Funktion e−E/(kT ) wobei

T > 0 die Temperatur undk > 0 eine Konstante ist.

Ein solches System finden wir mit hoherer Wahrscheinlichkeit ineinem Zustand mit geringer Energie.

Bei hohen Temperaturen ist die Wahrscheinlichkeit hoch, dass einSystem in einen Zustand mit hoher Energie wechselt — zumindestist diese Wahrscheinlichkeit hoher als bei niedriger Temperatur.

183

Andreas Jakoby



9. Vorlesung, 19.12.2007

Metropolis, Rosenbluth, Rosenbluth, Teller und Teller stellten dasfolgende Verfahren vor, um eine Schritt fur Schritt Simulation fur einSystem bei fester Temperatur T durchzufuhren:

Zu jedem Zeitpunkt t befindet sich das System im Zustand St .

Um den Nachfolgezustand St+1 aus dem Zustand St zu bestimmen,verfahren wir wie folgt:

Sei S ′ ein zufalliger zu St benachbarter Zustand. Ist E(S ′) < E(St), dann wahlen wir St+1 := S ′. Ist E(S ′) ≥ E(St), dann wahlen wir St+1 := S ′ mit

Wahrscheinlichkeit e−(E(S′)−E(S))/(kT ), ansonsten ist St+1 := St .

Sei C die (endliche) Menge der Zustande, die von einem festeninitialen Zustand erreichbar sind.

Diese Simulation besitzt die folgende Eigenschaft:

Satz 13 Sei Z =∑

S∈C e−E(S)/(kT ). Fur einen Zustand S sei fS(t) derAnteil der ersten t Zustande, in denen sich das System im Zustand S

befindet. Fur t →∞ ist mit einer Wahrscheinlichkeit, die gegen 1 geht,fS(t) gleich

1Ze−E(S)/(kT ).

184

Andreas Jakoby



9. Vorlesung, 19.12.2007

Algorithmus MinimizationMetropolis(I )Eingabe: Instanz I

Ergebnis: Losung S

1: sei S eine initiale Losung S02: seien k und T zwei Konstanten3: while we continue do4: wahle S ′ ∈ N(S) zufallig5: if c(S ′) ≤ c(S) then6: S := S ′

7: else8: mit Wahrscheinlichkeit e−(c(S

′)−c(S))/(kT ) sei S := S ′

9: und ansonsten belasse S unverandert10: end if11: end while12: Return(S)

185

Andreas Jakoby



9. Vorlesung, 19.12.2007

Kommentare: Der Metropolis Algorithmus stellt eine Methode dar, um einem

lokalen Minimum zu entkommen. Betrachten wir zum Beispiel wieder das Vertex Cover Problem auf

einem Sterngraphen, so erkennen wir, dass der MetropolisAlgorithmus jedes lokale Minimum wieder schnell verlaßt.

Betrachten wir jedoch das Vertex Cover Problem auf einem Graphenohne kanten, dann stellen wir fest, dass der Metropolis Algorithmusdazu tendiert Knoten zu der Losung, die nur noch wenige Knotenbesitzt, hinzuzufugen.

Um dieses Problem zu losen wollen wir den Einfluss und dieBedeutung der Temperatur T im Kontext vonOptimierungsproblemen neu analysieren.

Ist T hoch, dann durchlauft der Metropolis Algorithmus einenzufalligen Lauf durch den Graphen, der mehr oder wenigerunabhangig von der Kostenfunktion ist.

Ist T klein, dann werden die Losungen auf dem Pfad immer besser.Da keine schlechtere Losung akzeptiert wird, wird der MetropolisAlgorithmus im ersten erreichten (lokalen) Optimum stecken bleiben.

186

Andreas Jakoby



9. Vorlesung, 19.12.2007

Simulated annealing

Simulated Annealing simuliert den physikalische Prozess deslangsamen Abkuhlens eines erhitzten Systems.

Um die Form der Abkuhlung zu implementieren benutzen wir einesogenannte Abkuhlungsschedule τ : N → R+ \ 0 um imMetropolis Algorithmus die Temperatur in jedem Schleifendurchlaufzu bestimmen.

Die Auswirkungen der Abkuhlungsschedule ist in vielen Fallen sehraufwendig zu analysieren. Daher existieren oft nur Ergebnisse, diedie Auswirkungen bei einer Folge von Versuchen beschreiben.

187

Andreas Jakoby



9. Vorlesung, 19.12.2007

Algorithmus MinimizationSimulatedAnnealing(I )Eingabe: Instanz I

Ergebnis: Losung S

1: sei S eine initiale Losung S02: sei k eine Konstante3: sei t = 04: while we continue do5: wahle ein zufallige Losung S ′ ∈ N(S)6: if c(S ′) ≤ c(S) then7: S := S ′

8: else9: mit Whrscheinlichkeit e−(c(S

′)−c(S))/(kτ(t)) sei S := S ′

10: und ansonsten lasse S unverandert11: end if12: t := t + 113: end while14: Return(S)

188

Andreas Jakoby



10. Vorlesung, 9.1.2008

8 Das Flussproblem fur Netzwerke8.1 Netzwerke mit Kapazitatsbeschrankung

Definition 15 Ein Netzwerk N = (V ,E , γ, q, s) besteht aus

einem gerichteten Graph G = (V ,E ),

einer Quelle q ∈ V und einer Senke s ∈ V

sowie einer Kapazitatsfunktion γ : E → R+0 .

Es sei n := |V | und m := |E |.

189

Andreas Jakoby



10. Vorlesung, 9.1.2008

Definition 15 (Teil 2) Ein Fluss in N ist eine Funktion f : E → R+0 mit

folgenden Eigenschaften:

die Kapazitatsschranken der Kanten werden eingehalten, d.h.

∀e ∈ E : f (e) ≤ γ(e)

fur alle Knoten v ∈ V \ q, s wird die Kirchhoffsche Regeleingehalten, d.h.

∀v ∈ V \ q, s :∑

(u,v)∈E

f ((u, v)) =∑

(v ,w)∈E

f ((v , w)) .

190

Andreas Jakoby



10. Vorlesung, 9.1.2008

Definition 15 (Teil 3) Als Wert eines Flusses definieren wir als

W (f ) :=∑

(q,v)∈E

f ((q, v)) =∑

(u,s)∈E

f ((u, s)) .

Die Eigenschaft, dass der Ausfluss aus der Quelle identisch sein muss mitdem Abfluss in die Senke folgt unmittelbar aus der Kirchhoffschen Regel,da im Netzwerk kein Fluss verloren geht.Ein Fluss heißt maximal, falls sein Wert großtmoglich unter allen Flussenin N ist. MAXFLOW(N) bezeichnet diesen Wert.

191

Andreas Jakoby



10. Vorlesung, 9.1.2008

6

x

q s

u v

w

5

6

7

3

4

4

4

5

6

x

q s

u v

w

5

6

7

3

4

4

4

5

Ein Netzwerk und ein Fluss mit dem Wert 3.

192

Andreas Jakoby



10. Vorlesung, 9.1.2008

Ein Fluss ist somit ein Transportproblem:

Es sollen moglichst viele Einheiten einer Ware von einem Absenderzu einem Empfanger zu schicken, wobei gewisse Kapazitatsschrankenauf dem Transportweg eingehalten werden mussen.

Beispiele fur solche Transportprobleme sind:

Lenkung von Verkehrsstromen (Eisenbahn, PKWs) oder

Lenkung von Nachrichtenstromen (Telefonverkehr, Datenverkehr imInternet).

193

Andreas Jakoby



10. Vorlesung, 9.1.2008

Der maximale Fluss ist beschrankt durch

die Kapazitat der Quelle (die Summe der Kapazitaten aller Kanten,die die Quelle verlassen) und

die Kapazitat der Senke (die Summe der Kapazitaten aller Kanten,die in der Senke enden).

Es seiγmax := max

e∈Eγ(e) .

Da hochstens |V | − 1 Kanten die Quelle verlassen, ist der maximale Flussist beschrankt durch

|V | · γmax .

194

Andreas Jakoby



10. Vorlesung, 9.1.2008

Definition 16 Die Zerlegung der Kontenmenge V = Q ∪ S mitQ ∩ S = ∅ nennen wir q|s-Schnitt, falls q ∈ Q und s ∈ S ist.

Die Schnittkapazitat eines q|s-Schnittes definieren wir als

γ(Q,S) :=∑

(u,v)∈E , u∈Q, v∈S

γ((u, v)) .

Ein minimaler Schnitt von N ist ein q|s-Schnitt (Q, S), so dass γ(Q, S)minimal unter allen q|s-Schnitten ist. MINCUT(N) bezeichnet diesenWert.

Fur einen Fluss f sei der Nettofluss von f uber einen Schnitt (Q,S)definiert als

f (Q,S) :=∑

u∈Q, v∈S

f ((u, v))−∑

u∈Q, v∈S

f ((v , u)) ≤ γ(Q,S) .

195

Andreas Jakoby



10. Vorlesung, 9.1.2008

G

s

Q S

γ(e1)

γ(e2)

γ(er )

q

q|s-Schnitt (Q, S) mit Schnittkapazitat γ(Q, S).

196

Andreas Jakoby



10. Vorlesung, 9.1.2008

Lemma 9 Fur jeden q|s-Schnitt (Q, S) gilt

f (Q,S) = W (f ) .

Beweis von Lemma 9 Der Beweis erfolgt per Induktion uber dieMachtigkeit von Q.

Fur |Q| = 1, d.h. fur Q = q folgt die Behauptung aus derDefinition von W (f ).

Sei |Q| > 1 und v ∈ Q mit v 6= q. Nach Voraussetzung gilt

f (Q \ v, S ∪ v) = W (f ) .

197

Andreas Jakoby



10. Vorlesung, 9.1.2008


f2

sv

q

SQ

G

f1

f3

f4

198

Andreas Jakoby



10. Vorlesung, 9.1.2008


Sei f1 der Gesamtfluss nach v von Knoten aus Q \ v und f2 derGesamtfluss nach v von Knoten aus S .

Sei f3 der Gesamtfluss aus v nach Q \ v und f4 der Gesamtflussvon v nach S .

Die Flussbedingung garantiert

f1 + f2 = f3 + f4 oder f4 − f2 + f3 − f1 = 0.

f (Q, S) lasst sich darstellen als

f (Q,S) = f (Q \ v,S ∪ v) + f4 − f2 + f3 − f1

= f (Q \ v,S ∪ v) = W (f ) .

199

Andreas Jakoby



10. Vorlesung, 9.1.2008

Definition 17 Der Restgraphen G ′ = (V ,E ′) fur einen Fluss f

definieren wir uber die Kantenmenge E ′, wobei:

Fur jede Kante e ∈ E mit f (e) < γ(e) ist e ∈ E ′ mit Kapazitatγ(e)− f (e).

Fur jede Kante e = (u, v) ∈ E mit 0 < f (e) ist die Ruckwartskantee = (v , u) in E ′ mit Kapazitat f (e).

3

3

x

q s

u v

w

6

7

4

4

4

5

x

q s

u v

w

5

6

7

3

4

4

4

5

66− 3 = 3

3− 3

= 0

3

5− 3 = 2

200

Andreas Jakoby



10. Vorlesung, 9.1.2008

Definition 17 (Teil 2) Sei G ′ = (V , E ′) der Restgraph von G fur einenFluss f , dann ist REST(N, f ) := (V ,E ′, q, s, r) mit

r(e) :=

γ(e)− f (e) falls e ∈ E und γ(e) > f (e)f ((v , u)) falls e = (u, v), (v , u) ∈ E

und f ((v , u)) > 0.

Ein Weg von der Quelle zur Senke im Restgraphen heißt zunehmenderWeg.

201

Andreas Jakoby



10. Vorlesung, 9.1.2008

Sei f ein Fluss in N = (V , E , q, s, γ) und π ein zunehmender Weg inNf = REST(N, f ) = (V ,E ′, q, s, γ). Wir gehen im folgeden davon aus,dass ein zunehmender Weg jeden Knoten maximal einmal besucht. Dernachfolgende Algorithmus modifiziert f :

Algorithmus modify-flow(N, f , π)Eingabe: Netzwerk N, Fluss f in N und zunehmender Weg π in Nf

Ergebnis: um π erhohter Fluss f ′ in N

1: ρ := minr(ei )|ei ∈ π2: for ei ∈ π do3: if ei ist Vorwartskante in Nf , d.h. ei ∈ E then4: f (ei ) := f (ei ) + ρ5: else if ei ist Ruckwartskante in Nf , d.h. ei ∈ E ′ \ E then6: f (ei ) := f (ei )− ρ7: end if8: end for9: Return(f )

202

Andreas Jakoby



10. Vorlesung, 9.1.2008

Lemma 10 Ist f ein Fluss in N und π ein zunehmender Weg in Nf , dannist modify-flow(N, f , π) auch ein Fluss in N.

Beweis von Lemma 10: Wir mussen zunachst zeigen, dass

f ′ := modify-flow(N, f , π)

die Kapazitatsschranken γ einhalt. Da wir nur den Fluss auf dem Weg πverandern, genugt es, wenn wir fur alle Kanten e ∈ π zeigen, dass

0 ≤ f ′(e) ≤ γ(e)

gilt. Ist e eine Vorwartskante, dann gilt

0 ≤ f (e) ≤ f (e) + ρ ≤ f (e) + r(e) = γ(e) .

Ist e eine Ruckwarts Kante, dann gilt

0 = f (e)− f (e) ≤ f (e)− ρ ≤ f (e) ≤ γ(e) .

203

Andreas Jakoby



10. Vorlesung, 9.1.2008

Beweis von Lemma 10 (Teil 2): Als zweites mussen wir nun zeigen,dass die Kirchhoffsche Regel fur jeden Knoten v auf π (bis auf q und s)erfullt ist:

∑

(u,v)∈E

f ′((u, v)) =∑

(v ,w)∈E

f ′((v , w))

Betritt und verlasst π den Knoten v auf jeweils einer Vorwartskante,dann erhohen wir beide Summen um den Wert ρ. Die KirchhoffscheRegel bleibt somit erfullt.

Betritt und verlasst π den Knoten v auf jeweils einerRuckwartskante, dann verringern wir beide Summen um den Wert ρ.Die Kirchhoffsche Regel bleibt somit erfullt.

204

Andreas Jakoby



10. Vorlesung, 9.1.2008


Betreten wir v uber eine Vorwartskante (u′, v) und verlassen wir v

auf einer Ruckwartskante (v , w ′), dann

∑

(u,v)∈E

f ′((u, v)) =∑

(u,v)∈E

f ((u, v)) − f ((u′, v))− f ((w ′, v))

+f ′((u′, v)) + f ′((w ′, v))

=∑

(u,v)∈E

f ((u, v)) − f ((u′, v))− f ((w ′, v))

+f ((u′, v)) + ρ + f ((w ′, v))− ρ

=∑

(v ,w)∈E

f ((v , w)) .

Die Kirchhoffsche Regel bleibt somit erfullt.

205

Andreas Jakoby



10. Vorlesung, 9.1.2008


Betreten wir v uber eine Ruckwartskante (u′, v) und verlassen wir v

auf einer Vorwartsskante (v ,w ′), dann

∑

(v ,w)∈E

f ′((v ,w)) =∑

(v ,w)∈E

f ((v , w)) − f ((v , u′))− f ((v , w ′))

+f ′((v , u′)) + f ′((v , w ′))

=∑

(v ,w)∈E

f ((v , w)) − f ((v , u′))− f ((v , w ′))

+f ((v , u′))− ρ + f ((v ,w ′)) + ρ

=∑

(u,v)∈E

f ((u, v)) .

Die Kirchhoffsche Regel bleibt somit erfullt.

Wir haben somit bewiesen, dass f ′ ein Fluss ist, wenn f ein Fluss ist.

206

Andreas Jakoby



10. Vorlesung, 9.1.2008

Aus der Konstruktion von REST(N, f ) folgt, dass jeder zunehmende Wegq immer uber eine Vorwartskante verlasst, und dass jeder zunehmendeWeg s uber eine Vorwartskante erreicht. Es folgt somit:

Lemma 11 Fuhren wir modify-flow(N, f , π) fur einen Fluss f und einenzunehmenden aus, so gilt fur den resultierenden Fluss f ′:

W (f ) < W (f ′) .

Existiert somit in REST(N, f ) ein zunehmender Weg, dann ist f keinmaximaler Fluss.

207

Andreas Jakoby



10. Vorlesung, 9.1.2008

Satz 14 [MAXFLOW-MINCUT-Theorem] Fur jedes Netzwerk N gilt:

MAXFLOW(N) = MINCUT(N) .

Beweis von Satz 14: Nach Lemma 9 gilt fur einen maximalen Fluss f

und fur jeden q|s-Schnitt (Q, S)

MAXFLOW(N) = W (f ) = f (Q,S) ≤ γ(Q,S) .

Insbesondere gilt fur den minimalen q|s-Schnitt (Q,S)

MAXFLOW(N) ≤ γ(Q,S) = MINCUT(N) .

208

Andreas Jakoby



10. Vorlesung, 9.1.2008

Beweis von Satz 14 (Teil 2): Es verbleibt zu zeigen, dass

MAXFLOW(N) ≥ MINCUT(N) .

Sei f ein maximaler Fluss in N.

Aus Lemma 10 folgt, dass es in REST(N, f ) = (V , E ′, q, s, r) keinenzunehmenden Weg gibt, d.h. es gibt in G ′ = (V , E ′) keinen Wegvon q nach s.

Sei Q die Menge der Knoten, die von q aus in G ′ erreichbar sind,und sei S := V \ Q.

(Q,S) ist ein q|s-Schnitt.

209

Andreas Jakoby



10. Vorlesung, 9.1.2008

Beweis von Satz 14 (Teil 3): Insbesondere gilt fur den q|s-Schnitt(Q,S):

Es gibt keine Vorwartskanten von Q nach S in G ′. Somit gilt furjede Kante e ∈ Q × S :

f (e) = γ(e) .

Es gibt keine Ruckwartskanten von Q nach S in G ′. Somit gilt furjede Kante e ∈ S × Q:

f (e) = 0 .

Wir erhalten

MINCUT(N) ≤ γ(Q,S) = f (Q, S)

= W (f ) = MAXFLOW(N) .

210

Andreas Jakoby



10. Vorlesung, 9.1.2008

Aus den bisher angestellten Beobachtungen (Lemma 11 und Satz 14)konnen wir den folgenden Algorithmus fur das MAXFLOW-Problemherleiten

Algorithmus General-MAXFLOW(N)Eingabe: Netzwerk N

Ergebnis: maximaler Fluss f in N

1: for e ∈ E do f (e) := 0 end for2: while es existiert ein zunehmender Weg in REST(N, f ) do3: sei π ein zunehmender Weg in REST(N, f )4: f :=modify-flow(N, f , π)5: end while6: Return(f )

211

Andreas Jakoby



11. Vorlesung, 16.1.2008

Eine entscheidende Bedingung fur das Terminieren unseres obenangegebenen Verfahrens General-MAXFLOW liegt darin, dass dieKapazitatsschranken und jeder konstruierte Fluss ganzzahlig sind:

Lemma 12 Sei N ein Netzwerk mit Kapazitatsschranken γ(e) ∈ N, danngilt fur jeden in General-MAXFLOW konstruierten Fluss f :

∀e ∈ E : f (e) ∈ N .

Beweis von Lemma 12: Der Beweis erfolgt uber eine Induktion uber dieAnzahl t der ausgefuhrten while-Schleifen-Durchlaufe:

Fur t = 0 ist f (e) = 0 fur alle Kanten e ∈ E . Die Aussage desLemmas ist somit erfullt.

212

Andreas Jakoby



11. Vorlesung, 16.1.2008


Annahme: die Aussage ist fur den Fluss erfullt, den wir nach demt-ten Durchlauf der while-Schleife mit t > 0 erhalten.

Im t + 1-ten Durchlauf wahlen wir ρ, so dass dieser Wert entwederder Restkapazitat einer Kante oder dem Fluss auf einer Kanteentspricht. ρ ist somit ganzzahlig.

Da wir die ganzzahligen Werte des alten Flusses nur um den Wertvon ρ erhohen oder verringern, sind die resultierenden Werte wiederganzzahlig.

Die Bedingung, dass die resultierenden Werte auch in N liegen, folgtaus der Beobachtung, dass das Ergebnis von modify-flow(N, f , π)wieder ein Fluss ist.

213

Andreas Jakoby



11. Vorlesung, 16.1.2008

Aus Lemma 11 und Lemma 12 folgt:

Jeder Durchlauf durch die while-Schleife erhoht den Fluss ummindestens 1.

Da der maximale Fluss durch (|V | − 1) · γmax beschrankt ist, istauch die Anzahl der Durchlaufe durch die while-Schleife durch(|V | − 1) · γmax beschrankt.

Satz 15 Die Laufzeit von General-MAXFLOW(N) ist durchO(|V | · γmax · TWeg) nach oben beschrankt, wobei TWeg die Zeit ist, diewir benotigen um einen zunehmenden Weg zu finden.

214

Andreas Jakoby



11. Vorlesung, 16.1.2008

Bemerkungen

Bei ungunstiger Wahl der zunehmenden Wege in entsprechendkonstruierten Netzwerken, konnen wir zeigen, dass die Laufzeitunseres Verfahren tatsachlich Ω(|V | · γmax) Durchlaufe durch diewhile-Schleife benotigt. Ein Beispiel fur ein solches Netzwerk, ist:

1 sq

a

b

M M

MM

Wahlen wir den zunehmenden Weg abwechselnd uber die Kante(a, b) und uber die Ruckwartskante (b, a), so benotigen wir 2MIterationen der while-Schleife.

215

Andreas Jakoby



11. Vorlesung, 16.1.2008

Bemerkungen

Sind die Kapazitatsschranken nicht ganzzahlig, so konnen Beispielekonstruiert werden, fur die ein maximaler Fluss bei entsprechenderWahl der zunehmenden Wege nicht nach einer endlichen Anzahl vonIterationen konstruiert worden ist.

Es sei

β :=

√5− 1

2= 0, 618 . . . und α := 1 + β

β steht in enger Beziehung zur Fibonacci-Folge und ergibt sich ausder Losung des goldenen Schnitt-Problems. Es gilt

β2 + β = 1 und somit βk+2 = βk − βk+1

fur alle k ≥ 2.

216

Andreas Jakoby



11. Vorlesung, 16.1.2008

Als Netzwerk wahlen wir:

α

q

v2

v4

v5

s

v6α

α

β

β

1

α

α

α

α

v1 v3α

α

α

αα

α

Wir betrachten nun die Rest Kapazitaten des Netzwerks, nach dem wirverschiedene Pfade in den Fluss aufgenommen haben.

217

Andreas Jakoby



11. Vorlesung, 16.1.2008

Wir betrachten eine Folge von Phasen k = 0, 1, 2, . . .. Wobei jede Phaseaus 6 Flußerhohungen besteht. Wir betrachten hierbei 6 zunehmendeWege:

Erhohung1. Pfad q − v1 − v2 − v3 − v6 − s β1+3k

2. Pfad q − v2 − v1 − v3 − v6 − v5 − s β2+3k

3. Pfad q − v1 − v2 − v4 − v6 − s β2+3k

4. Pfad q − v2 − v1 − v4 − v6 − v3 − s β3+3k

5. Pfad q − v1 − v2 − v5 − v6 − s β3+3k

6. Pfad q − v2 − v1 − v5 − v6 − v4 − s β4+3k

Diese 5 Pfade erhohen den Fluss um

β1+3k + 2 · (β2+3k + β3+3k) + β1+3(k+1) .

218

Andreas Jakoby



11. Vorlesung, 16.1.2008

Nach ℓ Runden ist der Fluss

2 ·ℓ

∑

i :=0

(

β1+3i + β2+3i + β3+3i)

− β + β1+3(ℓ+1)

= 2 ·3ℓ+4∑

i :=1

βi − β

≤ 2

1− β− β − 2 = 2, 618 . . . ≤ 2 · α .

219

Andreas Jakoby



11. Vorlesung, 16.1.2008

Wir wollen im folgenden betrachten, wie sich die ausgewahlten Pfade aufden Fluss auswirken. Da nur die Kanten (v1, v2), (v3, v6), (v4, v6) und(v6, v5) sowohl als Vorwartskanten als auch als Ruckwartskanteneingesetzt werden, werden wir die Kapazitatsschranken der anderenKanten im Folgenden vernachlassigen.

Pfad 1 erhoht den Fluss um β:

q − v1 − v2 − v3 − v6 − s .

β

v2

v4

v5

s

v6

β α0 β

β2v3v1

q

220

Andreas Jakoby



11. Vorlesung, 16.1.2008

Pfad 2 erhoht den Fluss um β2:

q − v2 − v1 − v3 − v6 − v5 − s .

1

v2

v4

v6

β

v3

β2β3

v1 0

v5

s1 + β3β2

q

221

Andreas Jakoby



11. Vorlesung, 16.1.2008


q − v1 − v2 − v4 − v6 − s .

β

v2

v6

v1

s1 + β3

0

v4

v3

v5

β2

β3

β20

1

q

222

Andreas Jakoby



11. Vorlesung, 16.1.2008


q − v2 − v1 − v4 − v6 − v3 − s .

β

v2

v6

v3v1

v5

s1 + β3β2

v4

β3

1− β3

β3β2

0

q

223

Andreas Jakoby



11. Vorlesung, 16.1.2008


q − v1 − v2 − v5 − v6 − s .

1 + 2β3

v2

v6

v3v1

v5

s

v4

β3

1− β3

0

β0 β

β4

q

224

Andreas Jakoby



11. Vorlesung, 16.1.2008


q − v1 − v2 − v5 − v6 − v4 − s .

β − β4

v2

v6

v3v1

v5

s

v4

β3

1− β3

1 + β0

β4

β4β − β4q

225

Andreas Jakoby



11. Vorlesung, 16.1.2008

Effiziente Wahl der Flusserhohungen: Um die Laufzeitschranke ausSatz 10 zu verbessern konnen wir verschiedene Ansatze verfolgen:

Wahle unter allen zunehmenden Wegen einen Weg mitmaximaler Flusserhohung.Es kann gezeigt werden, dass:

Nach maximal 2|E | Flusserhohungen hat sich die maximal noch zuerzielende Flusserhohung halbiert.

Die Anzahl der Iterationen ist hochstens 2|E | · log2 γmax . Einen maximal zunehmenden Weg konnen wir mit Hilfe des

SSSP-Algorithmus finden. Die Gesamtlaufzeit ist somit O((m + n log n) ·m · log γmax).

226

Andreas Jakoby



11. Vorlesung, 16.1.2008

Wahle einen kurzesten zunehmenden Wegen.Hierbei entspricht die Lange eines Weges der Anzahl der Kanten aufdem Weg. Es kann gezeigt werden, dass:

Jede Flussvergroßerung sattigt mindestens eine Kante desRestgraphens (bei gegebener Weglange).

Nach maximal m Flussvergroßerungen mussen wir die Weglange um1 erhohen.

Die maximale Pfadlange ist n − 1. Einen kurzesten zunehmenden Weg konnen wir mit Hilfe der

Breitensuche in Zeit O(m) finden. Die Gesamtlaufzeit ist somit O(n ·m2).

227

Andreas Jakoby



11. Vorlesung, 16.1.2008

Betrachte alle kurzesten zunehmenden Wegen gleichzeitig undvergroßere den Fluss entlang all dieser Wege.Es kann gezeigt werden, dass:

Wir teilen den Restgraphen in eine Folge von Stufen auf, wobei diei-te Stufe aus allen Knoten besteht, deren Entfernung von der Quelleexakt i ist.

Wir betrachten zunachst den Teilgraph des Restgraphen, der nur dieKanten beinhaltet, die aufeinanderfolgende Stufen verbinden. DiesenTeilgraph nennen wir Niveaugraph.

Die Flussvergroßerung wird entlang zunehmender Wege imNiveaugraphen solange durchgefuhrt, bis q von s getrennt wird.

Derartige Wege kann man mit Hilfe der Breitensuche mit linearemAufwand finden.

228

Andreas Jakoby



11. Vorlesung, 16.1.2008

Weiter zu: Betrachte alle kurzesten zunehmenden Wegen gleichzeitigund vergroßere den Fluss entlang all dieser Wege:

Jede Flussvergroßerung sattigt mindestens eine Kante. Somit gibt esfur jeden Niveaugraphen maximal m Iterationen und der Aufwand furjede Iteration ist in O(n).

Konstruieren wir den neuen Niveaugraphen, so wachst dieEntfernung zwischen Quelle und Senke um mindestens 1.

Wir betrachten hochstens n viele Niveaugraphen. Die Gesamtlaufzeit ist somit O(m · n2).

229

Andreas Jakoby



11. Vorlesung, 16.1.2008

In den letzten Jahrzehnten wurden verschieden Algorithmen zur Losungdes MAXFLOW-Problems vorgestellt:

1956 Ford, Fulkerson: O(n ·m · γmax)

1972 Edmonds, Karp: O(n ·m2)

1970 Dinic: O(n2 ·m)

1974 Karzanov: O(n3) 1977 Cherkasky: O(n2 · √m)

1978 Malhotra, Kumar, Maheshwari: O(n3) 1980 Galil: O(n5/3 ·m2/3)

1978 Shiloach, 1980 Galil, Naamand: O(n ·m · log2 n)

1982 Shiloach, Vishkin: O(n3) 1983 Sleator, Tarjan: O(n ·m · log n)

1984 Tarjan: O(n3) 1985 Gabow: O(n ·m · log γmax)

230

Andreas Jakoby



11. Vorlesung, 16.1.2008

Weitere Algorithmen:

1985 Goldberg: O(n3) 1986 Goldberg, Tarjan: O(n ·m · log(n2/m))

1986 Bertsekas: O(n3) 1987 Cheriyan, Maheshwari: O(n2 · √m)

1987 Ahuja, Orlin: O(n ·m + n2 · log γmax)

1988 Ahuja, Orlin, Tarjan: O(n ·m + n2 · log γmax/ log log γmax)

1989 Cheriyan, Hagerup: O(minn ·m · log n, n ·m + n2 · log2 n)Probabilistische Algorithmen und deren erwartete Laufzeit:

1994 King, Rao, Tarjan: O((n ·m log n)/ log mn·log n

) fur m ≥ 2n log n

1996 Cheriyan, Hagerup, Mehlhorn: O(n3/ log n)

231

Andreas Jakoby



11. Vorlesung, 16.1.2008

8.2 Das Transport-Problem

Definition 18 [Transport-Problem] Gegeben sind zwei Folgenα1, . . . , αn ∈ N und β1, . . . , βm ∈ N mit

n∑

i=1

αi =

m∑

i=1

βi .

Gesucht sind n ·m Werte xi,j ∈ N mit i ∈ [1..n], j ∈ [1..m], so dass

∀i ∈ [1..n] :m∑

j=1

xi,j = αi und ∀i ∈ [1..m] :n

∑

i=1

xi,j = βj .

232

Andreas Jakoby



11. Vorlesung, 16.1.2008

Interpretation:

Wir betrachten n Produzenten P1, . . . ,Pn, die alle die gleiche Wahrproduzieren. Pi produziert αi Stucke dieser Wahre.

Wir betrachten m Kunden K1, . . . ,Km fur die von den Produzentenhergestellten Wahren. Kunde Kj mochte βj Stucke dieser Wahreerhalten.

Produzent Pi liefert xi,j Stucke der Wahre an den Kunden Kj .

233

Andreas Jakoby



11. Vorlesung, 16.1.2008

Das Transport-Problem kann mit Hilfe eines Netzwerks und einesMAXFLOW-Problems dargestellt werden:

Wir betrachten ein Netzwerk mit n + m + 2 Knotenq, s, v1, . . . , vn, u1, . . . , um und n + m + n ·m Kanten

E = (q, vi )|1 ≤ i ≤ n ∪ (uj , s)|1 ≤ j ≤ m∪ (vi , uj)|1 ≤ i ≤ n, 1 ≤ j ≤ m .

σ

vn

q

v2

u1

u2

um

s

β1

α1

α2

αn

β2

βm

σ

σσ

σ

σ

σ

σ

σ

v1

Als Gewichtsfunktion definieren wir

γ((vi , uj)) :=

n∑

i=1

αi

γ((q, vi )) := αi

γ((uj , s)) := βj

fur alle i ∈ [1..n] und j ∈ [1..m].

234

Andreas Jakoby



11. Vorlesung, 16.1.2008

Wir erkennen:

Das MAXFLOW-Problem fur die so generierte Instanz besitzt immereine ganzzahlige Losung f mit W (f ) =

∑ni=1 αi .

Der Flus uber die Kanten (vi , ui ) entspricht einer Losung fur dasTransport-Problem mit xi,j := f ((vi , uj)).

235

Andreas Jakoby



11. Vorlesung, 16.1.2008

9 Lineare Programmierung9.1 Was ist lineare Programmierung

Optimierungsprobleme wurden auf Folie 101 definiert:

Eine Instanz eines Optimierungsproblems ist ein Paar (F , f )wobei

F eine Menge von moglichen Losungen und f : F → R eine Kostenfunktion dieser Losungen abgibt.

Eine Losung x ∈ F nennen wir global optimal oder kurz optimal,wenn fur alle y ∈ F gilt

f (x) ≥ f (y) .

Gesucht ist eine optimale Losung bezuglich derKostenfunktion!

Ein Optimierungsproblem ist eine Menge von Instanz einesOptimierungsproblems.

236

Andreas Jakoby



11. Vorlesung, 16.1.2008

Die Definition des Transport-Problem gibt uns ein System vonGleichungen oder Ungleichungen vor und kann recht einfach als einOptimierungsproblem (Maximierungsproblem) dargestellt werden:

F := x = (xi,j)i∈[1..n], j∈[1..m] ∈ Nm×n |

∀i ∈ [1..n] : αi ≤m∑

j=1

xi,j

∀j ∈ [1..m] : βj ≤n

∑

i=1

xi,j

f (x) :=∑

i∈[1..n], j∈[1..m]

xi,j .

Optimierungsprobleme dieser Form nennen wir auch lineare Programme.

237

Andreas Jakoby



11. Vorlesung, 16.1.2008

Definition 19 [Lineares Optimierungsproblem (LP)] Ein linearesOptimierungsproblem uber einem geordneten Ring R ist folgendermaßenspezifiziert:

Gegeben sind zwei Vektoren

~c =

c1...cn

∈ Rn und ~b =

b1...

bm

∈ Rm .

und eine Matrix

A =

a1,1 . . . a1,n...

. . ....

am,1 . . . am,n

∈ Rm×n .

238

Andreas Jakoby



11. Vorlesung, 16.1.2008

Definition 19 (Teil 2) Einen Vektor ~x nennen wir eine zulassigeLosung des Optimierungsproblems, falls:

Fur alle i ∈ [1..m] die Bedingung

n∑

j=1

ai,j · xj ≤ bi

erfullt ist. Kompakt schreiben wir auch A · ~x ≤ ~b.

Gesucht ist eine zulassige Losung x , welche

Z =

n∑

j=1

cj · xj

oder kompakt Z = ~cT · ~x maximiert, wobei ~cT die Transponierte von ~cbezeichnet.

239

Andreas Jakoby



11. Vorlesung, 16.1.2008

Definition 19 (Teil 3) Im Wesentlichen betrachten wir lineareProgramme uber Z, Q und R und unterscheiden daher zwischen

Integer linearen Programmen (ILP) oder ganzzahligen linearenProgrammen mit R = Z,

rationalen linearen Programmen (QLP) mit R = Q und

reelen linearen Programmen (RLP) mit R = R.

Beim linearen Programmieren stellen wir ein Optimierungsproblem mitHilfe eines Systems von linearen Ungleichungen uber n Unbekanntendar. Ferner geben wir eine lineare Zielfunktion an, die es zu optimierengilt, d.h. deren Wert es zu maximieren bzw. zu minimieren gilt.

240

Andreas Jakoby



11. Vorlesung, 16.1.2008

Beispiel: Optimale Produktion

Ein klassisches Beispiel fur die lineare Programmierung aus derOkonomie stellt die Optimierung einer Produktion unter gegebenenRandbedingungen dar.

Ein Unternehmen mochte den Gewinn, den es mit einer Maschinemacht, optimieren.

Diese Maschine kann zwei Produkte P1 und P2 herstellen. Eine Einheit von P1 kann mit Gewinn von 7 Euro und eine Einheit

von P2 mit Gewinn von 4 Euro verkauft werden. Sei x1 die Anzahl der Einheiten, die die Maschine von dem Produkt

P1 herstellt, und x2 die Anzahl der Einheiten, die die Maschine vondem Produkt P2 herstellt, dann gilt es, die Produktion soeinzustellen, dass wir den Wert von

g(x1, x2) := 7 · x1 + 4 · x2

maximieren. Es existieren jedoch einige Bedingungen, die wir bei der Einstellung

der Maschine, d.h. bei der Bestimmung der optimalen Werte x1 undx2, berucksichtigen mussen.

241

Andreas Jakoby



11. Vorlesung, 16.1.2008

Beschrankungen fur die Produktion: Die Produktion einer Einheit von P1 benotigt 4 Minuten und die

Produktion einer Einheit von P2 benotigt 2 Minuten. Fur dieProduktion stehen insgesamt 240 Maschinenstunden im Monat zurVerfugung, das sind 14400 Minuten. Es gilt somit

4 · x1 + 2 · x2 ≤ 14400 .

Die Produktion von P1 benotigt 3 Liter eines Rohstoffs pro Einheit,von dem im Monat 9000 Liter zur Verfugung stehen. Es gilt somit

3 · x1 ≤ 9000 .

Bei der Produktion von P2 werden 5 g eines umweltpolitisch nichtunbedenklichen Gases freigesetzt. Der monatliche Ausstoß diesesGases soll daher auf 20.000 g beschrankt sein. Wir erhalten

5 · x2 ≤ 20000 .

242

Andreas Jakoby



11. Vorlesung, 16.1.2008

Beschrankungen fur die Produktion (Teil 2): Fur 200 Einheiten von P1 und fur 500 Einheiten von P2 existieren

bereits feste Vertrage. Somit gilt

x1 ≥ 200 und x2 ≥ 500 .

Wird die Maschine weniger als 4200 Minuten im Monat eingesetzt,dann besteht die Gefahr, dass sie Schaden nimmt. Um dieses zuverhindern fordern wir

4 · x1 + 2 · x2 ≥ 4200 .

Und schließlich muss jedes Produkt nach der Herstellung einegewisse Zeit gelagert werden. Die monatliche Lagerkapazitat desUnternehmens beschrankt sich auf 5000 Einheiten. Wir erhalten

x1 + x2 ≤ 5000 .

243

AndreasJakoby

Universitatzu

Lubeck

AlgorithmikWS07/08

11.Vorlesung,16.1.2008

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!!

!!!

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

""""

"""

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

####

###

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

&&

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

''

(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((( ))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

****

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

++++

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

--

Masc

hin

enzeit

2000

3000

4000

5000

Vert

rag

P2

Rohst

offzuliefe

rung

Um

welt

Lagerp

latz

Vert

rag

P1

(min

)1000

x2

x1

1000

2000

3000

4000

5000

6000

Masc

hin

enzeit

(max)

Das

Ungleichungssystem

faßt

die

Einschrankungenuber

den

Losungsraum

zusammen.

Genau

dieTupel(x

1,x

2),die

konform

zuallenRestriktionen

sind,

sindLosungenunseresSystems.

Unterihnen

istdiemitden

optimalen

Zielwertenfur

g(x

1,x

2)

ausfindigzu

machen.

Im

obigen

FallfuhrtjedeUngleichungzu

einer

Einschrankungder

Losungsmenge.Diesesistnichtimmer

der

Fall.Gilt

furden

Rohstoffl

ieferung

x1≤4000,so

fuhrtdieseszu

keiner

Einschrankung

der

Losungsmenge.

SolcheEinschrankungennennen

wir

redundant.

244

AndreasJakoby

Universitatzu

Lubeck

AlgorithmikWS07/08


1000/4000

4000

5000

6000

1000

2000

3000

4000

5000

2200/2800

200/4000

800/500

3000/500

3000/1200

200/1700

x2

x1

1000

2000

3000

Diezusatzlichen

Linienstelleneine

Auswahlvonmoglichen

Gew

inngleichungen

g(x

1,x

2)=

c

furverschiedeneGew

inne

cdar.

Weiteroben

verlaufenden

Geraden

stellenhohereGew

innedar.

GesuchtistdiehochsteGerade,die

das

Pla

nungsv

iele

ckberuhrt.

In

unserem

Fallistder

Punkt

2200/2800optimal.

Der

optimaleGew

inn(Zielwert)

ist7·2200+4·2800=26600.

Zum

Vergleich:DiebenachbartenEckpunkte1000/4000und

3000/1200haben

dieZielwerte

23000bzw

.25800.

245

AndreasJakoby

Universitatzu

Lubeck

AlgorithmikWS07/08


Beider

Bestimmungder

optimalen

Losungkonnen

zweiFalle

auftreten:

1.DieGeraden

der

Punktegleicher

Zielwerte

verlaufennicht

parallelzu

einer

der

relevantenSeitendes

Vielecks.In

diesem

Fallstellteinkonkreter

Eckpunkt

des

Vielecksdieeindeutige

optimaleLosungdar.

2.DieGeraden

der

Punktegleicher

Zielwerte

verlaufenparallelzu

einer

der

relevantenSeitendes

Vielecks.In

diesem

Fallhat

jeder

Punkt

entlangdieserSeite

denselben

optimalen

Zielwert.

Insbesonderestellenauch

diebeiden

Eckpunkteoptimale

Losungendar.

In

jedem

der

beiden

FalleisteineEckedes

Vielecksoptimal.

Esgenugt

also

einfach

dieEcken

des

Planungsvielecks

auszuw

erten.

246

AndreasJakoby

Universitatzu

Lubeck

AlgorithmikWS07/08


DieAuswertungder

Eckpunkteistbeizw

eiVariablennoch

relativ

uberschaubar.Beieiner

großerenAnzahlvonVariablen–d.h.bei

einer

hoheren

Dimension–wirddiese

Aufgabeschnellsehrviel

schwerer.

Bilden

dieEinschrankungen

kein

geschlossenes

Vieleck,so

istder

Losungsraum

ineiner

Richtungunbegrenzt.

In

diesem

Fallmussen

wirdieobigeBetrachtungen

sinngem

aßanpassen.

247

Andreas Jakoby



12. Vorlesung, 23.1.2008

9.2 Komplexitat von linearen Programmen

Um die Komplexitat der eingeschrankten Versionen von linearenProgrammen zu analysieren betrachten wir naheliegende Abwandlungenvon linearen Programmen als Entscheidungsproblem:

Gegeben sind die beiden Vektoren ~b ∈ Rm, ~c ∈ Rn, die MatrixA ∈ Rm×n und ein Wert z ∈ R.

Frage: Existiert eine Losung ~x ∈ Rn, so dass A · ~x ≤ ~b und~cT · ~x ≥ z ist.

Eine wesentliche Erkenntnis uber lineare Programme ist, dass diesesEntscheidungsproblem in polynomieller Zeit losbar ist, wenn wir R = R

betrachten. Jedoch ist das Problem NP-vollstandig fur den Fall, dass wireine ganzzahlige Losung suchen.

248

Andreas Jakoby



12. Vorlesung, 23.1.2008

Der Beweis, dass das Entscheidungsproblem zum ILP in NP liegt, istrelativ aufwendig und soll an dieser Stelle nicht untersucht werden.Vielmehr wollen wir hier den einfachen Beweis der NP-harte vorstellen.Wir gehen davon aus, dass

NP und NP-hart bzw. NP-schwierig, polynomial-Zeit- und logarithmisch-Platz-reduzierbar sowie

das 3-SAT Problem

dem Teilnehmer der Veranstaltung bekannt sind.

Satz 16 Das Entscheidungsproblem zum ILP ist NP-schwierig.Beweis von Satz 16: Um den Satz 11 zu beweisen, wollen wir eineReduktion von 3-SAT auf das Entscheidungsproblem zum ILP angegeben.

249

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beweis von Satz 16 (Teil 2): Wir betrachten eine Instanz des 3-SATProblems:

Gegeben ist eine Folge von Klauseln C1, . . . ,Cm uber den Variablenx1, . . . , xn mit

Ci = xαi,1

i,1 ∨ xαi,2

i,2 ∨ xαi,3

i,3

xi,1, xi,2, xi,3 ∈ x1, . . . , xnαi,1, αi,2, αi,3 ∈ 0, 1 .

Hierbei gilt

xαi,j

i,j :=

x i,j fur αi,j = 0xi,j fur αi,j = 1 .

250

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beweis von Satz 16 (Teil 3): Fur die auf der letzten Folie beschriebeneInstanz des 3-SAT Problems generieren wir folgende Instanz fur dasILP-Entscheidungsproblem:

Fur jede Variable xi des 3-SAT Problems betrachten wir zweiVariablen y0i und y1i in unserem linearen Programm.

Wir generieren folgende Ungleichungen:

y0i + y1i ≤ 1 und − y0i − y1i ≤ −1

sowie−y0i ≤ 0 und − y1i ≤ 0 .

Diese beiden Ungleichungen garantieren in einer zulassigen Losungdes ILPs, dass genau eine dieser Variable y0i , y1i den Wert 1 und eineden Wert 0 hat.

Fur jede Klausel Ci = xαi,1

i,1 ∨ xαi,2

i,2 ∨ xαi,3

i,3 generieren wir diefolgenden Ungleichung

−yαi,1

i,1 − yαi,2

i,2 − yαi,3

i,3 ≤ −1 .

251

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beweis von Satz 16 (Teil 4): Optimieren wollen wir die Summe allerVariablen und wahlen

n∑

i=1

(y0i + y1i ) ≥ n .

Es ist einach zu erkennen, dass jede zulassige Losung desUngleichungssystems von Folie 251 diese Ungleichung erfullt. Wir wollennun zeigen, dass das ILP genau dann eine zulassige Losung besitzt, wenn

C1 ∧ C2 ∧ . . . ∧ Cm

eine erfullende Belegung besitzt. Hierbei konnen wir

y0i = 1 ⇐⇒ xi = 0

undy1i = 1 ⇐⇒ xi = 1

wahlen.

252

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beweis von Satz 16 (Teil 5): Sei x1 = b1, . . . , xn = bn eine erfullendeBelegung fur

C1 ∧ C2 ∧ . . . ∧ Cm .

Dann gilt:

Aufgund unserer Vereinbarung gilt y1i = bi und y0i = 1− bi , undsomit

y0i + y1i = 1− bi + bi = 1 .

Folglich sind alle Ungleichungen vom Typ

y0i + y1i ≤ 1 und − y0i − y1i ≤ −1

erfullt.

253

Andreas Jakoby



12. Vorlesung, 23.1.2008


Da x1 = b1, . . . , xn = bn eine erfullende Belegung ist, gibt es fur jedeKlausel Ci ein Literal x

αi,j

i,j mit xαi,j

i,j = 1. Somit gilt yαi,j

i,j = 1. Somitgilt

yαi,1

i,1 + yαi,2

i,2 + yαi,3

i,3 ≥ 1 .

Somit sind auch alle Ungleichungen vom Typ

−yαi,1

i,1 − yαi,2

i,2 − yαi,3

i,3 ≤ −1

erfullt.

Es gibt somit eine zulassige Losung.

254

Andreas Jakoby



12. Vorlesung, 23.1.2008


Sei y01 = 1− y11 = b1, . . . , y0n = 1− y1n = bn eine zulassige Losung des

ILPs. Dann gilt fur alle Klauseln Ci , dass

−yαi,1

i,1 − yαi,2

i,2 − yαi,3

i,3 ≤ −1

Somit gilt xαi,j

i,j = 1 und folglich ist auch die Klausel Ci erfullt.

255

Andreas Jakoby



12. Vorlesung, 23.1.2008

9.3 Geometrische Interpretation von linearen Programmen

Eine geometrische Interpretation von linearen Programmen haben wirbereits in dem Beispiel auf den Folien 244 und 245 vorgestellt.

Jede Gleichungn

∑

j=1

ai,j · xj = bi

mit festen Werten ai,j und bi definiert eine n − 1-dimensionaleHyperebene im n-dimensionalen Raum.

Eine Ungleichungn

∑

j=1

ai,j · xj ≤ bi

definiert einen Halbraum des n-dimensionalen Raums auf derrichtigen Seite der Hyperebene

∑nj=1 ai,j · xj = bi .

256

Andreas Jakoby



12. Vorlesung, 23.1.2008

x3

(1, 0, 3)(0, 0, 3)

(0, 2, 3)

(2, 0, 2)

(2, 0, 0)

(0, 2, 0) (2, 2, 0)

(0, 0, 0)

x2

x1

Ungleichungen:

x1 + x2 + x3 ≤ 4x1 ≤ 2

x3 ≤ 33x2 + x3 ≤ 6

−x1 + x2 + x3 ≤ 0−x2 ≤ 0

−x3 ≤ 0

Blau ist die Hyperebene x3 = 3eingezeichet.

Der Halbraum x3 ≤ 3 befindet sichunter der Hyperebene.

257

Andreas Jakoby



12. Vorlesung, 23.1.2008

(0, 0, 0)

(1, 0, 3)(0, 0, 3)

(0, 2, 3)

(2, 0, 2)

(2, 0, 0)

(0, 2, 0) (2, 2, 0)x2

x1

x3

Mit S bezeichnen wir dieMenge aller zulassigenLosungen.

S ist der Schnitt aller durchdie Hyperebenenbeschriebenen Halbraume.

Mit Sopt ⊆ S wir die Mengeder optimalen zulassigenLosungen, die Menge derzulassigen Losungen fur diedie Zielfunktion Z = ~cT · ~xmaximal ist.

258

Andreas Jakoby



12. Vorlesung, 23.1.2008

Das LP heißt unlosbar, falls es keine zulassige Losung besitzt.

Fur die Ringe der rationalen und reellen Zahlen gilt: Ist S beschrankt, so bildet S ein konvexes Polyeder. Sopt ist entweder leer, einelementig oder unendlich groß. Ist Sopt 6= ∅, dann enthalt die Menge Sopt mindestens einen Eckpunkt

des durch A · ~x ≤ ~b beschriebenen Polyeders.

Ist Sopt leer, obwohl S nicht leer ist, dann kann die Zielfunktion Z

beliebig groß werden. In diesem Fall nennen wir das LPunbeschrankt.

259

Andreas Jakoby



12. Vorlesung, 23.1.2008

9.4 Formen linearer Programme

Bevor wir auf den Simplex-Algorithmus eingehen, wollen wir noch aufeine Vereinfachung eingehen:

Wir ersetzen jede Variable xj durch ein Paar x+j , x−j von

Hilfsvariablen fur die wir x+j ≥ 0 und x−j ≥ 0 verlangen. DieseUngleichungen nehmen wir in unser Ungleichungssystem mit auf.

Hierbei substituieren wir das Vorkommen von xj durch x+j − x−j .

Wir fuhren fur jede Bedingung∑n

j=1 ai,j · xj ≤ bi fuhren wir eine

sogenannte Schlupfvariable5 yi ein, die angibt, um wie viel∑n

j=1 ai,j · xj kleiner als bi ist.

5Nicht Schlumpfvariable!

260

Andreas Jakoby



12. Vorlesung, 23.1.2008

Wir erhalten folgende Variante des LPs Maximiere

Z =n

X

j=1

cj · (x+j − x

−j )

unter den Bedingungen

yi +n

X

j=1

ai,j · (x+j − x

−j ) = bi

undx+1 , x

−1 , . . . , x

+n , x

−n , y1, . . . , ym ≥ 0 .

261

Andreas Jakoby



12. Vorlesung, 23.1.2008

Formen von linearen Programmen

In der Literatur unterscheiden wir drei Formen von linearen Programmenuber einem Ring R:

die generelle Form: Gegeben ist eine Matrix A ∈ Rm×n und ein Vektor ~b ∈ Rm.

Desweiteren ist eine Partition von 1, . . . , m in drei paarweisedisjunkte Teilmengen M1, M2, M3 gegeben. Seien A1, . . . , An dieZeilenvektoren der Matrix A. Damit eine Losung ~x ∈ Rn gultig ist,mussen die folgenden Bedingungen erfullt sein:

fur alle i ∈ M1 gilt Ai · ~x ≤ bi , fur alle i ∈ M2 gilt Ai · ~x = bi und fur alle i ∈ M3 gilt Ai · ~x ≥ bi .

Sie 0 das neutrale Element in R bezuglich der Addition, dann gibt eseine Poritionierung N1, N2, N3 von 1, . . . , n, so dass

fur alle i ∈ N1 gilt xi ≤ 0, fur alle i ∈ N2 gilt xi ≥ 0 und fur alle i ∈ N3 ist die Variable xi nicht weiter beschrankt.

Ferner ist ein Vektor ~c ∈ Rn und somit die Zielfunktion ~cT · ~xgegeben. Abhangig vom Typ des linearen Programms unterscheidenwir zwischen dem Minimierungproblem, hierbei ist die Zielfunktion zuminimieren, und dem Maximierungsproblem, hierbei ist dieZielfunktion zu maximieren.

262

Andreas Jakoby



12. Vorlesung, 23.1.2008

die Standardform: Gegeben ist eine Matrix A ∈ Rm×n und ein Vektor ~b ∈ Rm. Damit

eine Losung ~x ∈ Rn gultig ist, mussen die folgenden Bedingungerfullt ist:

A · ~x ≤ ~b .

Sie 0 das neutrale Element in R bezuglich der Addition, dann gibt

xi ≥ 0 .

Ferner ist ein Vektor ~c ∈ Rn und somit die Zielfunktion

~cT · ~x

gegeben. Gesucht ist eine Losung ~x ∈ Rn, die die Zielfunktion zuminimiert.

263

Andreas Jakoby



12. Vorlesung, 23.1.2008

die kanonische Form: Gegeben ist eine Matrix A ∈ Rm×n und ein Vektor ~b ∈ Rm. Damit

eine Losung ~x ∈ Rn gultig ist, mussen die folgenden Bedingungerfullt ist:

A · ~x = ~b .

Sie 0 das neutrale Element in R bezuglich der Addition, dann gibt

xi ≥ 0 .

Ferner ist ein Vektor ~c ∈ Rn und somit die Zielfunktion

~cT · ~x

gegeben. Gesucht ist eine Losung ~x ∈ Rn, die die Zielfunktion zuminimiert.

264

Andreas Jakoby



12. Vorlesung, 23.1.2008

Es ist recht einfach einzusehen, dass sich jedes lineare Programm P1,welches in der generellen Form gegeben ist, auch als ein linearesProgramm P2 in kanonischer Form so darstellen laßt, dass aus eineroptimalen Losung von P2 eine optimale Losung von P1 abgeleitet werdenkann. Die jeweiligen Transformationen konnen linearer Zeit6 ausgefuhrtwerden.

6Die lineare Zeit bezieht sich auf das Modell einer RAM.

265

Andreas Jakoby



12. Vorlesung, 23.1.2008

9.5 Der Simplex-Algorithmus

Der Simplex-Algorithmus (1951 von G. Dantig vorgestellt) ist dasbekannteste Verfahren zur Losung linearer Programme. Jedoch konntebisher fur keine Variante des Simplex-Algorithmus nachgewiesen werden,dass diese polynomielle Zeit benotigt.

Der Simplex-Algorithmus arbeitet in drei Phasen:

Phase 1: Finde eine Basislosung oder zeige, dass das LP unlosbarist.

Phase 2: Finde eine zulassige Basislosung oder zeige, dass das LPunlosbar ist.

Phase 3: Verbessere die aktuelle zulassige Basislosung solange, bis die aktuelle zulassige Basislosung optimal (d.h. minimal) ist oder gezeigt werden kann, dass das LP unlosbar ist.

266

Andreas Jakoby



12. Vorlesung, 23.1.2008

Definition 20 Sei A ∈ Rm×n,~b ∈ Rm,~c ∈ Rn ein LP in kanonischer Formmit m ≤ n. Mit A1, . . . ,An bezeichnen wir die Spalten von A, d.h. Aj istdie j-te Spalte von A.

~x ist eine Losung des LP mit A,~b,~c , wenn A · ~x = ~b ist.

~x ist eine zulassige Losung des LP mit A,~b,~c , wenn A · ~x = ~b und~x ≥ 0 ist.

Sei A eine Matrix vom Rang m, d.h. die Zeilen von A sind linearunabhangig. Seien Aj1 , . . . ,Ajm m linear unabhangiger Spalten undB = (Aj1 , . . . ,Ajm) die Matrix, die sich aus diesen Spaltenzusammensetzt.

~xB ist eine Basislosung des LP mit A,~b,~c , wenn B · ~xB = ~b ist.

~xB ist eine zulassige Basislosung des LP mit A,~b,~c , wennB · ~xB = ~b und ~xB ≥ 0 ist.

267

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beobachtung 15 Sei A eine Matrix deren Zeilen linear unabhangig sind,dann gilt:

Es existieren m linear unabhangiger Spalten Aj1 , . . . ,Ajm in A unddie Matrix B = (Aj1 , . . . ,Ajm).

Da B eine nicht-singulare m ×m-Matrix ist, existiert die InverseB−1.

Sei ~xB := B−1 · ~b, dann erfullt ~x ∈ Rn mit

xj =

xBi falls j = ji ist und0 sonst

die Gleichung A · ~x = ~b.

Ist ~xB ≥ 0, dann ist auch ~x ≥ 0.

Sei ~cB := (cj1 , . . . , cjm), dann gilt

~cT · ~x = (~cB)T · ~xB .

268

Andreas Jakoby



12. Vorlesung, 23.1.2008

Beobachtung 15 (Teil 2)

Sei Y := B−1 · A und ~z := ((~cB)T · Y )T , dann gilt

~zT · ~x = (~cB)T · B−1 · A · ~x= (~cB)T · B−1 · ~b = (~cB)T · ~xB .

Im Folgenden gehen wir zunachst davon aus, dass die Zeilen von A linearunabhangig sind.

Der Einfachheit halber nennen wir die Losung ~x , die wir aus ~xB gemaßder Regel auf der Folie 268 konstruieren auch Basislosung.

269

Andreas Jakoby



13. Vorlesung, 30.1.2008

Lemma 13 Besitzt ein kanonisches lineares Programm eine zulassigeLosung, dann gibt es fur dieses lineare Programm auch eine zulassigeBasislosung.

Beweis von Lemma 13: Sei ~x ∈ Rn eine zulassige Losung und sei p ≤ n

die Anzahl der Variablen xi mit xi > 0.

Durch Vertauschen der Spalten in A und der Positionen in ~x ,~ckonnen wir garantieren, dass x1, . . . , xp großer 0 sind.

Da ~x eine zulassige Losung ist, gilt xi = 0 fur alle i ∈ [p + 1..n], esgilt somit

p∑

j=1

xj · Aj = ~b .

Sind A1, . . . ,Ap linear unabhangig, dann ist p ≤ m und wir konnenA1, . . . ,Ap mit Hilfe von m − p weiteren Spalten aus A zu einerMatrix B erganzen. ~xB ist somit eine zulassige Basislosung.

270

Andreas Jakoby



13. Vorlesung, 30.1.2008


Sind A1, . . . ,Ap linear abhangig, dann sind nicht alle diese Spaltenin einer Matrix B enthalten. Es gilt:

Es existieren p Werte α1, . . . , αp, von denen zumindest ein Wert αr

ungleich 0 ist, so dass

pX

j=1

αj · Aj = 0

ist. Dann gilt

X

j∈[1..p]\r

„

xj −αj

αr

· xr

«

· Aj = ~b .

Wir erhalten eine Losung mit hochstens p − 1 Eintragen ungleich 0.Wir mussen jedoch zunachst annehmen, dass dieses keine zulassigLosung ist.

271

Andreas Jakoby



13. Vorlesung, 30.1.2008


Die Losung

x ′j =

xj − αj

αr· xr fur j ∈ [1..p] \ r

0 sonst.

ist zulassige, wenn fur alle j ∈ [1..p] \ r

xj −αj

αr

· xr ≥ 0

ist.

Ist αj = 0, so ist dieses erfullt.

Ist αj 6= 0, so muss

xj

αj

−xr

αr

≥ 0 fur αj > 0 und

xj

αj

−xr

αr

≤ 0 fur αj < 0 sein.

272

Andreas Jakoby



13. Vorlesung, 30.1.2008


Um diese Bedingungen zu erfullen wahlen wir entweder

xr

αr

= minj∈[1..p]

xj

αj

∣

∣

∣

∣

αj > 0

oderxr

αr

= maxj∈[1..p]

xj

αj

∣

∣

∣

∣

αj < 0

.

Wir konnen diesen Schritt wiederholen, bis eine zulassigeBasislosung entstanden ist.

273

Andreas Jakoby



13. Vorlesung, 30.1.2008

Eine zentrale Komponente im Simplex-Algorithmus ist die Pivotierungoder die Gaußelimination:

Sei ar ,s 6= 0 ein Eintrag in A.

Wir ersetzen jede Zeile von A mit i 6= r durch

(ai,1, . . . , ai,n) −ai,s

ar ,s· (ar ,1, . . . , ar ,n)

und die r -te Zeile durch

1

ar ,s· (ar ,1, . . . , ar ,n) .

Durch diesen Schritt wird aus der s-ten Spalte (0, . . . , 0, 1, 0, . . . , 0),wobei die 1 an der r -ten Stelle steht.

Um eine Basislosung zu finden, wahlen wir iterativ furi = 1, 2, . . . ,m ein ai,ji 6= 0 in Zeile i und pivotieren auf ai,ji .

Auf diese Weise wahlen wir m linear unabhangige SpaltenAj1 , . . . ,Ajm von A und bestimmen eine Basislosung ~xB mitB = (Aj1 , . . . ,Ajm).

274

Andreas Jakoby



13. Vorlesung, 30.1.2008

Algorithmus Pivotieren(A, r , s)Eingabe: k × ℓ-Matrix A, Position r ∈ [1..k] und s ∈ [1..ℓ]Ergebnis: modifizierte Matrix A mit s-ter Spalte (0, . . . , 0, 1, 0, . . . , 0)

1: for i = 1 to k by +1 with i 6= r do2: (ai,1, . . . , ai,ℓ) := (ai,1, . . . , ai,ℓ) − ai,s

ar,s· (ar ,1, . . . , ar ,ℓ)

3: end for4: (ar ,1, . . . , ar ,ℓ) := 1

ar,s· (ar ,1, . . . , ar ,ℓ)

5: Return(A)

275

Andreas Jakoby



13. Vorlesung, 30.1.2008

Phase 1: Finde eine Basislosung:

Mit Hilfe von Tableaus reduziert sich der Simplex-Algorithmusdarauf, bezuglich bestimmter Eintrage zu pivotieren.

Ein Tableau eines kanonischen linearen Programms ist die(m + 1)× (n + 1)-Matrix

T :=

[

A ~b~cT 0

]

.

Sei B ∈ Rm×m eine invertierbare Teilmatrix von A, wie wir sie aufder Folie 267 beschrieben haben. Zur Vereinfachung gehen wirdavon aus, dass die Spalten von B durch die ersten m Spalten von A

gegeben sind, dann hat das Tableau die Form

T :=

[

B Am+1 . . . An~b

(cB)T cm+1 . . . cn 0

]

.

276

Andreas Jakoby



13. Vorlesung, 30.1.2008

Multiplizieren wir dieses Tableau von links mit

[

B−1 0(~cB)T · B−1 1

]

.

so erhalten wir[

Y ~xB

~cT − ~zT −Z

]

=

[

I Ym+1 . . . Yn ~xB

0 cm+1 − zm+1 . . . cn − zn −Z

]

wobei I die m ×m-Einheitsmatrix ist.

Algorithmisch konnen wir dieses mit Hilfe der Pivotierung und demAlgorithmus Finde-Basislosung auf Folie 278 losen.

Hierbei ist zu beachten, dass wir in diesem Algorithmus nicht davonausgehen, dass sich B in den ersten m Spalten von A befindet.Ferner gehen wir nicht davon aus, dass die Zeilen von A linearunabhangig sind.

277

Andreas Jakoby



13. Vorlesung, 30.1.2008

Algorithmus Finde-Basislosung(T )

Eingabe: m + 1× n + 1-Tableau T =

[

A ~b~cT 0

]

Ergebnis: Tableau mit Basislosung ~xB oder infeasible

1: r := 12: while r ≤ m do3: s := min(j ∈ [1..n]|T [r , j ] 6= 0 ∪ ∞)4: if s =∞∧ T [r , n + 1] 6= 0 then Return(infeasible)5: else if s =∞∧ T [r , n + 1] = 0 then6: for i = r + 1 to m + 1 by +1 do7: (T [i − 1, 1], ..,T [i − 1, n + 1]) := (T [i , 1], ..,T [i , n + 1])8: end for9: m := m − 110: else setze T :=Pivotieren(T , r , s), jr := s und r := r + 111: end if12: end while13: Return(T , j1, . . . , jm)

278

Andreas Jakoby



13. Vorlesung, 30.1.2008

Phase 2: Finde eine zulassigen Basislosung:

In Phase 1 haben wir eine Basislosung ~xB = B−1 ·~b des kanonischenProgramms KLP 1:

minimiere Z = ~cT · ~x unter der Bedingung A · ~x = ~b und ~x ≥ 0

gefunden und dabei das Tableau

[

Y1 . . . Yn ~xB

c1 − z1 . . . cn − zn −Z

]

berechnet.

Ist xBi < 0 fur eine Zeile i , dann ist die gefundene Losung nicht

zulassig.

279

Andreas Jakoby



13. Vorlesung, 30.1.2008

Sei ~e = (e1, . . . , em)T ∈ Rm mit

ei =

−1 falls xBi < 0 und

0 falls xBi ≥ 0

Sei x0 eine neue Variable, dann betrachten wir das neue kanonischelineare Programm KLP 2:

minimiere Z∗ = x0 unter der Bedingung ~e · x0 + Y · ~x = ~xB und x0, ~x ≥ 0.

Wir betrachten hierbei das Tableau

T ∗ =

~e Y1 . . . Yn ~xB

0 c1 − z1 . . . cn − zn −Z

1 0 . . . 0 0

mit den Spalten 0 bis n + 1 und den Zeilen 1 bis m + 2. Die Zeilem + 1 belassen wir zur Vereinfachung im Tableau. Sie wird nichtberucksichtigt, wenn wir das LP losen. Wir modifiziere sie jedochbeim pivotieren.

280

Andreas Jakoby



13. Vorlesung, 30.1.2008

Lemma 14 KLP 2 ist immer losbar und hat einen nicht-negativen Wert.


Sei r die Zeile, fur die xBr minimal ist.

Wir pivotieren auf Zeile r und Spalte s = 0.

Hierbei gilt T ∗[r , s] = −1 und

T ∗[i , s] =

−1 falls xBi < 0 und

0 sonst.

281

Andreas Jakoby



13. Vorlesung, 30.1.2008


Durch die Pivotierung erhalten wir

(T ∗[i , 0], . . . ,T ∗[i , n + 1])

=

−(T ∗[r , 0], . . . ,T ∗[r , n + 1])falls i = r

(T ∗[i , 0], . . . ,T ∗[i , n + 1])falls i 6= r und xB

i ≥ 0(T ∗[i , 0], . . . ,T ∗[i , n + 1])− (T ∗[r , 0], . . . ,T ∗[r , n + 1])

falls i 6= r und xBi < 0 .

Somit ist das Ergebnis eine zulassige Losung des KLP 2.

Wegen x0 ≥ 0 kann der optimale Wert nicht negativ sein.

Beachte: Nach dem im Beweis beschriebenen Schritt liegt uns einezulassige Basislosung des KLP 2 vor, und wir konnen diese analog zuPhase 3 verbessern!

282

Andreas Jakoby



14. Vorlesung, 6.2.2008

Lemma 15 KLP 1 ist genau dann losbar, wenn das dazugehorige LPKLP 2 eine Losung mit dem Wert Z∗ = 0 besitzt. Ist Z∗ = 0 furx0,~x ≥ 0, dann ist ~x eine zulassige Losung von KLP 1.


Nach Lemma 14 ist der Wert der Zielfunktion Z∗ von KLP 2 nichtnegativ.

Wir betrachten zunachst den Fall, dass Z∗ = x0 = 0 ist. Dann gibtes ein ~x ≥ 0 in Rn, so dass

~e · x0 + Y · ~x = Y · ~x = ~xB

ist (siehe Bedingung von KLP 2).

283

Andreas Jakoby



14. Vorlesung, 6.2.2008


Somit gilt fur diese Losung

B−1 · A · ~x = Y · ~x = ~xB = B−1 · ~b

und folglichA · ~x = ~b .

Dieses ~x ist folglich eine zulassige Losung des ursprunglichen LPKLP 1.

284

Andreas Jakoby



14. Vorlesung, 6.2.2008

Beweis von Lemma 15 (Teil 3): Wir betrachten nun die Ruckrichtung:

Sei ~x eine zulassige Losung von KLP 1, d.h. A · ~x = ~b.

Dann gilt

Y · ~x = B−1 · A · ~x = B−1 · ~b = ~xB .

Folglich ist x0 = 0 zusammen mit diesem Vektor ~x eine zulassigeLosung fur das KLP 2, wobei der Wert der Zielfunktion

Z∗ = x0 = 0

ist.

Da eine Bedingung des KLP 2 x0 ≥ 0 ist, ist diese Wert derZielfunktion minimal.

285

Andreas Jakoby



14. Vorlesung, 6.2.2008

Um eine erste zulassige Basislosung zu finden konnen wir wie folgtvorgehen:

Wir generieren aus einer Basislosung fur ein kanonisches linearesProgramm ein neues kanonisches lineares Programm in der Formvon KLP 2.

Wir bestimmen eine zulassige Basislosung fur dieses LP wie imBeweis von Lemma 14 beschrieben.

Verfahren analog zur Phase 3 um eine optimale Losung zu finden.

Interpretiere diese Losung wie in Lemma 15 beschrieben.

286

Andreas Jakoby



14. Vorlesung, 6.2.2008

Algorithmus Finde-zulassige-Basislosung(T , j1, . . . , jm)

Eingabe: m + 1× n + 1-Tableau T :=

[

Y ~xB

~cT − ~zT −Z

]

Ergebnis: Tableau mit zulassiger Basislosung ~xB oder infeasible

1: if ∀i ∈ [1..m] : T [i , n + 1] ≥ 0 then Return(T , j1, . . . , jm) end if2: generiere in T Spalte 0 und Zeile m + 23: T [m + 2, 0] := 1, T [m + 1, 0] := 04: for i = 1 to n + 1 by +1 do T [m + 2, i ] := 0 end for5: for i = 1 to m by +1 do6: if T [i , n + 1] < 0 then T [i , 0] := −1 else T [i , 0] := 0 end if7: end for8: wahle r ∈ [1..m] mit T [r , n + 1] ≤ T [i , n + 1] fur alle i ∈ [1..m]9: setze jr := 0 und T :=Pivotieren(T , r , 0)10: setze H =Verbessere-zulassige-Basislosung-2(T , j1, . . . , jm)11: if H =unb ∨ T [m + 2, n + 1] 6= 0 then Return(infeasible) end if12: setze (T , j1, .., jm) := H und entferne in T Spalte 0 und Zeile m + 213: Return(T , j1, . . . , jm)

287

Andreas Jakoby



14. Vorlesung, 6.2.2008

Phase 3: Verbessern einer zulassigen Basislosung:

Da die Idee hinter dem verbessern einer zulassigen Basislosungeinfacher ist, wollen wir diese Phase vorziehen.

Sei ~xB = B−1 · ~b eine zulassige Basislosung eines kanonischenlinearen Programms und Z = (~cB)T · ~xB .

Sei Y = B−1 · A und Yj = (y1,j , . . . , ym,j) die j-te Spalte von Y .

Da B regular ist, gilt

Aj = B · Yj =

m∑

i=1

yi,j · Bi .

Ist yr ,j 6= 0, dann sind auch die SpaltenB1, . . . ,Br−1,Aj , Br+1, . . . ,Bm linear unabhangig und wir konnen B

durchB∗ = (B1, . . . ,Br−1, Aj ,Br+1, . . . ,Bm)

ersetzen und eine neue Basislosung ~xB∗ = (B∗)−1 · ~b .

288

Andreas Jakoby



14. Vorlesung, 6.2.2008

~xB∗ muss keine zulassige Basislosung sein. Mit Hilfe einiger elementarerUmformungen folgt:

Lemma 16 ~xB∗ ist genau dann eine zulassige Basislosung, wenn fur allei ∈ [1..m] \ r

xBi − xB

r ·yi,j

yr ,j≥ 0

ist undxBr

yr ,j≥ 0

gilt.

289

Andreas Jakoby



14. Vorlesung, 6.2.2008

Wir untersuchen nun, unter welchen Voraussetzungen ~xB∗ eine zulassigeBasislosung ist. Es gilt:

Ist xBr = 0, dann sind beide Ungleichungen aus Lemma 16 erfullt.

Ist xBr 6= 0, dann folgt aus der zweiten Ungleichung von Lemma 16,

dass yr ,j > 0 ist. Ist yi,j < 0, dann ist auch die erste Ungleichungerfullt.

Ist xBr 6= 0 und yr ,j < 0, dann ist nach Lemma 16 ~xB∗ keine

zulassige Basislosung.

Wir mussen nun noch den Fall xBr 6= 0, yr ,j > 0 und yi,j > 0

betrachten.

Damit ~xB∗ eine zulassige Basislosung ist, muss nach Lemma 16 indiesem Fall

xBr

yr ,i≤ xB

i

yi,j

gelten.

290

Andreas Jakoby



14. Vorlesung, 6.2.2008

Damit ~xB∗ eine zulassige Basislosung ist, mussen wir r so aus B

auswahlen, dass

xBr

yr ,i= min

i∈[1..m]

xBi

yi,j

∣

∣

∣

∣

yi,j > 0

=: θ

ist.

Idee fur einen Algorithmus: Wir wahlen eine (beliebige) Spalte Aj

von A, die nicht in B vorkommt. Gibt es ein yi,j > 0, dann gibt es inB eine Spalte Br , die wir durch Aj ersetzen konnen, um einezulassige Basislosung ~xB∗ zu erhalten. Diese Spalte konnen wir mitHilfe der obigen Formel bestimmen.

291

Andreas Jakoby



14. Vorlesung, 6.2.2008

Mit Hilfe einiger elementarer Umformungen7 folgt:

Lemma 17 Der Wert der Zielfunktion der zulassige Basislosung ~xB∗ ist

Z∗ = Z +xBr

yr ,j· (cj − zj) = Z + θ · (cj − zj) .

7und etwas rechnen

292

Andreas Jakoby



14. Vorlesung, 6.2.2008

Idee fur einen Algorithmus:

Wir wahlen eine Spalte Aj von A, die nicht in B vorkommt, fur die(cj − zj) < 0 ist und fur die es ein yi,j > 0 gibt. Wahlen wir eingeeignetes Br und ersetzen Br durch Aj , dann erhalten wir einenneuen Wert der Zielfunktion Z∗ ≤ Z . Ist die Basislosung ~xB nichtdegeneriert, d.h. ist xB

r 6= 0, dann gilt sogar Z∗ < Z .

Bezuglich des Tableaus

[

I Ym+1 . . . Yn ~xB

0 cm+1 − zm−1 . . . cn − zm −Z

]

von ~xB bedeutet dieses: Wir suchen eine Spalte j mit negativemEintrag in der letzten und positivem yi,j in der i-ten Zeile. Fur jedenpositiven Eintage yi,j berechnen wir θi = xB

i /yi,j und wahlen r , sodass θr minimal ist. Dann pivotieren wir auf Zeile r und Spalte j .

293

Andreas Jakoby



14. Vorlesung, 6.2.2008

Wann liegt eine unbeschrankte Losung vor?

Wir betrachten eine Spalte Aj mit yi,j ≤ 0 fur alle i ∈ [1..m].

Es gilt

~b = B · ~xB =

m∑

i=1

Bi · xBi

wobei der Wert der Zielfunktion Z = (~cB)T · ~xB ist.

Fur einen beliebigen Wert θ gilt

~b = B · ~xB − θ · Aj + θ · Aj =m∑

i=1

Bi · xBi − θ · Aj + θ · Aj

und

Aj = B · Yj =m∑

i=1

Bi · yi,j .

294

Andreas Jakoby



14. Vorlesung, 6.2.2008

Somit ist

~b =

m∑

i=1

Bi · (xBi − θ · yi,j) + θ · Aj .

Ist θ > 0, dann ist xBi − θ · yi,j ≥ xB

i ≥ 0 fur alle i ∈ [1..m].

Aus der obigen Gleichung erhalten wir eine neue zulassige Losungfur das LP:

xi = xBi − θ · yi,j fur i ∈ [1..m]

undxj = θ .

Als Wert der Zielfunktion erhalten wir Z∗ = Z + θ · (cj − zj).

Ist cj − zj < 0, dann konnen wir den Wert der Zielfunktion beliebigklein machen.

295

Andreas Jakoby



14. Vorlesung, 6.2.2008

Fur unseren Algorithmus merken wir uns:

Gibt es eine Spalte Aj , die nicht in B vorliegt und fur die sowohlcj − zj < 0 als auch Yj = B−1 · Aj ≤ 0 ist, dann ist das lineareProgramm unbeschrankt.

Gibt es im Tableau eine Spalte j in der kein Eintrag positiv und derletzte Eintrag negativ ist, dann ist das lineare Programmunbeschrankt.

296

Andreas Jakoby



14. Vorlesung, 6.2.2008

Wann ist eine zulassige Losung optimal?

Lemma 18 Sei ~xB = B−1 · ~b eine zulassige Basislosung des kanonischenlinearen Programms A,~b,~c wobei Z = (~cB)T · ~xB . Ist cj − zj ≥ 0 fur alleSpalten Aj , die nicht zu B gehoren,8 dann ist Z minimal und ~xB

beschreibt eine optimale zulassige Losung fur das lineare Programm.


Jede Spalte Aj von A kann als Linearkombination Aj = B · Yj

geschrieben werden. Wir erhalten

A = B · Y und ~zT = (~cB)T · Y .

8Das bedeutet, dass der Wert der aktuellen Losung nicht durch Austausch einerSpalte von B mit einer anderen Spalte aus A verbessert werden kann.

297

Andreas Jakoby



14. Vorlesung, 6.2.2008


Sei ~x ′ eine beliebige zulassige Losung des LPs und Z ′ = ~cT · ~x ′ derdazugehorige Wert der Zielfunktion.

Fur alle Losungen ~x (also insbesondere auch fur ~x ′) gilt

B · ~xB = b = A · ~x = B · Y · ~x

und somit~xB = Y · ~x .

Betrachten wir nun die Zielfunktion, so erkennen wir, dass

Z = (~cB)T · ~xB = (~cB)T · Y · ~x ′ = ~zT · ~x ′ ≤ cT · ~x ′ = Z ′.

Die letzte Ungleichung folgt aus der Tatsache, dass ~z ≤ ~c und ~x ≥ 0ist.

Z ist somit minimal und folglich ist ~xB eine optimale zulassigeLosung.

298

Andreas Jakoby



14. Vorlesung, 6.2.2008

Fur unseren Algorithmus gilt:

Gibt es im Tableau keinen negativen Eintrag in der letzten Zeile,dann haben wir eine optimale Losung gefunden.

Um die optimale Losung auszugeben, suchen wir die m Spaltenj1, . . . , jm im Tableau , die die m ×m-Einheitsmatrix auf den erstenm Zeilen enthalten. Dann gilt fur die optimale Losung ~x ∈ Rn:

xj =

xBi falls j = ji ist und0 sonst

299

Andreas Jakoby



14. Vorlesung, 6.2.2008

Algorithmus Verbessere-zulassige-Basislosung(T , j1, . . . , jm)Eingabe: Tableau T ∈ Rm+1×n+1

Ergebnis: Tableau mit optimaler Losung ~xB oder unbounded

1: while ∃j ∈ [1..n] : T [m + 1, j ] < 0 do2: if ∃j ∈ [1..n]∀i ∈ [1..m] : T [i , j ] ≤ 0 ∧ T [m + 1, j ] < 0 then3: Return(unbounded) end if4: wahle s ∈ [1..n] \ j1, . . . , jm mit T [m + 1, s] < 0

5: wahle r ∈ [1..m] mit T [r ,n+1]T [r ,s] ≤ T [i,n+1]

T [i,s] fur alle i ∈ [1..m]

6: mit T [i , s] > 0 und T [r , s] > 07: setze T :=Pivotieren(T , r , s) und jr := s

8: end while9: Return(T , j1, . . . , jm)

300

Andreas Jakoby



14. Vorlesung, 6.2.2008

Algorithmus Verbessere-zulassige-Basislosung-2(T , j1, . . . , jm)Eingabe: Tableau T ∈ Rm+2×n+2

Ergebnis: Tableau mit optimaler Losung ~xB fur KLP 2oder unb

1: while ∃j ∈ [0..n] : T [m + 2, j ] < 0 do2: if ∃j ∈ [0..n]∀i ∈ [1..m] : T [i , j ] ≤ 0 ∧ T [m + 2, j ] < 0 then3: Return(unb) end if4: wahle s ∈ [0..n] \ j1, . . . , jm mit T [m + 2, s] < 0

5: wahle r ∈ [1..m] mit T [r ,n+1]T [r ,s] ≤ T [i,n+1]

T [i,s] fur alle i ∈ [1..m]

6: mit T [i , s] > 0 und T [r , s] > 07: setze T :=Pivotieren(T , r , s) und jr := s

8: end while9: Return(T , j1, . . . , jm)

301

Andreas Jakoby



14. Vorlesung, 6.2.2008

Terminierung

Aus unserer Analyse folgt bis jetzt nicht, ob die Suche nach eineroptimalen Losung jemals terminiert.

Die Terminierung hangt im wesentlichen von der Wahl desPivotelements in Zeile 4 (und 5) der AlgorithmenVerbessere-zulassige-Basislosung undVerbessere-zulassige-Basislosung-2 ab. Die Regel nach der diesesElement ausgewahlt wird nennen wir Pivotregel.

Wenden wir die smallest-index-Regel an, dann halt die Suche nacheiner optimalen Losung immer. Die smallest-index-Regel wahlt s, rwie folgt:

wahle s minimal, so dass T [m + 1, s] < 0 bzw. T [m + 2, s] < 0 istund

wahle r minimal, so dass T [r , s] > 0 und fur alle i ∈ [1..m] mitT [i , s] > 0

T [r , n + 1]

T [r , s]≤

T [i , n + 1]

T [i , s]

ist.

302

Andreas Jakoby



14. Vorlesung, 6.2.2008

Algorithmus Simplex-Algorithmus(A,~b,~c)Eingabe: kanonisches lineares Programm mit m × n-Matrix A,

m-dimensionalem Vektor ~b undn-dimensionalem Vektor ~c

Ergebnis: optimaler Losung ~x des kanonischen linearen Programms

1: generiere das Tableau T :=

[

A ~b~cT 0

]

2: H :=Finde-Basislosung(T )3: if H =infeasible then Return(infeasible) end if4: H :=Finde-zulassige-Basislosung(H)5: if H =infeasible then Return(infeasible) end if6: sei (T , j1, . . . , jm) = H

7: if ∃i ∈ [1..m] : ji = 0 then8: wahle k ∈ [1..n] \ j1, . . . , jm mit T [i , k] 6= 09: T := Pivotieren(T , i , k), ji := k

10: end if

303

Andreas Jakoby



14. Vorlesung, 6.2.2008

Simplex-Algorithmus (Teil 2):

11: H :=Verbessere-zulassige-Basislosung(T , j1, . . . , jm)12: if H =unbounded then Return(unbounded) end if13: sei (T , j1, . . . , jm) = H

14: for i := 1 to n by +1 do xi := 0 end for15: for i := 1 to m by +1 do xji := T [i , n + 1] end for16: Z := −T [m + 1, n + 1]17: Return(Z , x1, . . . , xn)

304

Andreas Jakoby



14. Vorlesung, 6.2.2008

Satz 17 Der Simplex-Algorithmus terminiert immer und bestimmt dieoptimale Losung fur ein kanonisches lineares Programm korrekt, wenn wirdie smallest-index-Regel anwenden.

305

Andreas Jakoby



14. Vorlesung, 6.2.2008

Analysieren wir die Losungen, die der Simplex-Algorithmus findet, soerkennen wir:

Beobachtung 16 Bestimmt der Simplex-Algorithmus eine optimaleLosung, dann ist diese Losung fur ein lineares Programme A ∈ Nm×n, einVektor ~b ∈ Nm und ein Vektor ~c ∈ Nn immer ein rationaler Vektor~x ∈ Qn.

Beobachtung 17 Fur die zulassigen Basislosungen ~x , die derSimplex-Algorithmus auf Eingabe eines linearen Programms A ∈ Nm×n,ein Vektor ~b ∈ Nm und ein Vektor ~c ∈ Nn bestimmt, gilt ~x ∈ Qn undsowohl die Betrage der Eintrage in ~x als auch deren Nenner sind durch 2L

beschrankt, wobeiL = m · n + ⌈log2 |P|⌉

und |P| das Produkt der Eintrage in A, ~b und ~c ist, die ungleich 0 sind.

306

Andreas Jakoby



14. Vorlesung, 6.2.2008

Lemma 19 Seien ~x und ~x ′ zwei zulassige Basislosungen eines linearenProgramms in kanonischer Form mit

k · 2−2L < ~cT · ~x , ~cT · ~x ′ ≤ (k + 1) · 2−2L

fur ein k ∈ N, dann ist ~cT · ~x = ~cT · ~x ′.Beweis von Lemma 19: Sei ~cT · ~x 6= ~cT · ~x ′.

Nach Beobachtung 17 sind dann ~cT · ~x und ~cT · ~x ′ zwei rationaleZahlen mit jeweils einem Nenner großer 2L.

Somit ist |~cT · ~x − ~cT · ~x ′| ≤ 2−2L.

Dieses stellt eine wesentliche Beobachtung auf dem Weg zu einempolynomial zeitbeschrankten Verfahren zur Losung linearer Algorithmendar, dem Ellipsoid-Algorithmus.

307

Andreas Jakoby



15. Vorlesung, 13.2.2008

10 Matching-Probleme10.1 Definition von Matching-Probleme

Definition 21 [2-dimensionales Matching]

Sei G = (V , E ) ein ungerichteter Graph und E ′ ⊆ E . E ′ ist einMatching, wenn fur alle Kantenpaare e1, e2 ∈ E ′ mit e1 6= e2 gilt,dass e1 ∩ e2 = ∅ ist, d.h. die beiden Kanten verbindenunterschiedliche disjunkte Knotenpaare.

Ein Matching E ′ nennen wir maximal, wenn es keine echteObermenge E ′′ ⊃ E ′ gibt, die die Matching-Bedingung erfullt.

E ′ heißt Maximum- oder optimales Matching, wenn die E ′ einMatching großtmoglicher Kardinalitat (in der Menge aller Matchingsvon G ) ist.

E ′ ist ein perfektes Matching, falls jeder Knoten von G mit einerKante aus E ′ inzident ist.

308

Andreas Jakoby



15. Vorlesung, 13.2.2008


Unter dem (2-dimensionalen) Matching-Problem verstehen wirdas Problem, fur einen ungerichteten Graphen zu entscheiden, ob furdiesen ein perfektes Matching existiert.

Ist zusatzlich zum Graphen G noch eine Kostenfunktion κ : E → R

auf den Kanten gegeben, so ergibt sich das gewichteteMatching-Problem. Hierbei unterscheiden wir zwei Varianten:

1. Gesucht ist ein Matching E ′ ⊆ E , welches den Wert desMatchings

W (E ′) :=∑

e∈E ′

κ(e)

maximiert.2. Gesucht ist ein optimales Matching E ′, so dass W (E ′) minimal

ist.

Leider konnen wir hier nur auf eine eingeschrankte Version weitereingehen.

309

Andreas Jakoby



15. Vorlesung, 13.2.2008

Eine fur viele Anwendungen interessante Variante des Matching-Problemserhalten wir, wenn wir uns auf bipartite Graphen einschranken:

Definition 22

Einen Graphen G = (V ,E ) nennen wir bipartit oder 2-farbbar, fallswir seine Knotenmenge in zwei Teilmengen V1,V2 partitionierenkonnen, so dass

V1 ∩ V2 = ∅, V1 ∪ V2 = V

und jede Kanten mit einem Knoten aus V1 und mit einem Knotenaus V2 inzident ist.

Das Matching-Problem fur bipartite Graphen nennen wir auchHeiratsproblem.

Anwendungen: Ressourcen optimal zuordnen, Prozesse zu Prozessorenzuordnen oder Clients zu Servern zuordnen.

310

Andreas Jakoby



15. Vorlesung, 13.2.2008

Definition 23 [3DM, 3-DIM-MATCHING]

Gegeben eine Menge M von Tripeln uber einer GrundmengeA× B × C paarweise disjunkter Komponentenmengen A, B,C . EinMatching von M ist eine Teilmenge M ′ ⊆ M, so dass jedes Elementaus A ∪ B ∪ C in hochstens einem Tripel aus M ′ vorkommt.

Ein Matching M ′, bei dem jedes Element aus A ∪ B ∪ C genaueinmal vertreten ist, ist ein perfektes 3-dimensionales Matching.

Das Entscheidungsproblem, ob fur eine Menge M ein perfektes3-dimensionales Matching existiert nennen wir 3-DIM-MATCHINGoder kurz 3DM.

Definition 24 [X3C, exakte 3-Uberdeckung]

Ist M eine Menge von 3-elementigen Mengen uber einer endlichenGrundmenge C , wird aus dem 3DM Problem das Problem fur eineMenge M zu entscheiden, ob eine exakte 3-Uberdeckung existiert.Wir nennen diese Problem X3C.

311

Andreas Jakoby



15. Vorlesung, 13.2.2008

10.2 Das Heiratsproblem

Satz 18 [Heiratssatz] Ein bipartiter Graph G = (V ,E ) mitKnotenpartitionierung V1, V2 besitzt genau dann ein perfektes Matching,wenn |V1| = |V2| ist und fur alle Teilmengen U1 ⊆ V1 und derenKorrespondenz auf der anderen Seite

Γ(U1) := v ∈ V2 | ∃u ∈ U1 : u, v ∈ E

die Ungleichung|U1| ≤ |Γ(U1)|

erfullt ist.

Bemerkung: Aus diesem Satz konnen wir keinen effizienten Algorithmusfur das Heiratsproblem herleiten, da es exponentiell viele Teilmengen vonV1 gibt.

312

Andreas Jakoby



15. Vorlesung, 13.2.2008

Beweis von Satz 18: Die Notwendigkeit der beiden Bedingungen, folgtunmittelbar aus der Definition des Heiratsproblems:

Sei E ′ ein perfektes Matching und U1 eine beliebige Teilmenge vonV1, dann ist jeder Knoten aus U1 uber E ′ mit genau einem Knotenaus V2 verbunden. Somit gilt |U1| ≤ |Γ(U1)|.

313

Andreas Jakoby



15. Vorlesung, 13.2.2008

Beweis von Satz 18 (Teil 2): Um zu zeigen, dass die Bedingungen desSatzes auch hinreichend sind, greifen wir auf Satz 14(MAXFLOW-MINCUT-Theorem auf Folie 208) zuruck. Es ist einfachmoglich, das Matching-Problem fur bipartite Graphen auf einFlußproblem zu reduzieren:

Fuge eine Quelle q und eine Senke s zu G hinzu und verbinde q mitalle Knoten aus V1 und alle Knoten aus V2 mit s.

Richte alle Kanten von q nach s. Insbesondere richte alle Kantenzwischen V1 und V2, so dass sie von V1 nach V2 verlaufen.

Gebe allen Kanten die Kapazitat 1.

Sei H das resultierende Netzwerk.

314

Andreas Jakoby



15. Vorlesung, 13.2.2008


sq

um

u1

V1 V2

v1

v2

vm

u2

Wie wir aus dem Algorithmus zur Bestimmung des maximalen Flusses(Algorithmus modify-flow auf Folie 202) erkennen konnen, existiert zujedem Graphen mit ganzzahliger Kapazitatsfunktion γ : E → N einmaximaler Fluss f , der ganzzahlig ist, d.h. ein Fluss der Form f : E → N.

315

Andreas Jakoby



15. Vorlesung, 13.2.2008

Beweis von Satz 18 (Teil 4): Wir erkennen:

Zu jedem Matching E ′ in G korrespondiert eindeutig ein Fluss f inH gleicher Große, wenn man uber die Kanten in H, deren Urbilder inG zu E ′ gehoren, jeweils eine Einheit fließen laßt.

Analoges gilt auch in umgekehrter Richtung, wenn wir einenganzzahligen Fluss betrachten.

316

Andreas Jakoby



15. Vorlesung, 13.2.2008


Angenommen, ein bipartiter Graph G mit |V1| = |V2| besitzt keinperfektes Matching.

Aus der letzten Beobachtung auf der Folie 316 konnen wir somitfolgern, dass der Wert des maximalen Flusses kleiner als |V1| ist.

Wir betrachten nun einen minimalen q|s-Schnitt (Q,S) in H.

Die Schnittkapazitat γ(Q,S) ist die Anzahl der Kanten, die von Q

nach S fuhren.

Sei Q ′ := Q ∩ V1.

317

Andreas Jakoby



15. Vorlesung, 13.2.2008


Da q mit jedem Knoten in V1 ∩ S = V1 \ Q ′ und jeder Knoten ausS ′ = Q ∩ V2 mit s verbunden ist, gilt

|V1| > MAXFLOW((H, γ))

= γ(Q,S) =∑

(u,v)∈E u∈Q,v∈S

γ((u, v))

≥ |V1 \ Q ′|+ |Γ(Q ′) ∩ S |+ |Γ(Q ′) ∩ Q|

= |V1| − |Q ′|+ |Γ(Q ′)| .

Dies impliziert |Q ′| > |Γ(Q ′)| und die zweite Bedingung ist verletzt.

Gibt es kein perfektes Matching fur einen bipartiten Graphen, so giltdie zweite Bedingung nicht.

318

Andreas Jakoby



15. Vorlesung, 13.2.2008


Γ(Q′) ∩ S

u2

u1

V1 V2

v1

v2

sq u3

u4

u5 v5

v4

v3

Q

Q′ = V1 ∩ Q Γ(Q′) ∩ V2

V1 ∩ S

319

Andreas Jakoby



15. Vorlesung, 13.2.2008

Wie wir schon angemerkt haben, konnen wir aus Satz 18 keineneffizienten Algorithmus zum Losen des Matching-Problems fur bipartiteGraphen herleiten. Unsere Uberlegungen aus dem Beweis von Satz 18zeigt jedoch, dass unser Algorithmus von Folie 211 das Matching-Problemfur bipartite Graphen zu finden. Einen zunehmenden Weg in dem von unskonstruierten Graphen konnen wir in H Zeit O(|E |) finden.Satz 19 Ein optimales Matching fur bipartite Graphen konnen wir in ZeitO(|V | · |E |) finden.Es kann sogar gezeigt werden, dass Matching-Problems fur bipartiteGraphen in Zeit O(|V |2,5) gelost werden kann. Fur das gewichteteMatching-Problem fur bipartite Graphen konnen wir nicht so einfacheinsehen, dass dieses Problem auch mit Hilfe des General-MAXFLOWAlgorithmus gelost werden kann.

320

Andreas Jakoby



15. Vorlesung, 13.2.2008

10.3 Heiratsproblem mit Kantenkosten

Unser Algorithmus basiert auf der Idee der zunehmenden Wegen ausKapitel 8.1. Wir gehen hierbei wie folgt vor:

Gegeben ist ein ungerichteter bipartiter Graph G = (V1 ∪ V2,E ) mit|V1| = |V2| = n und eine Gewichtsfunktion κ : E → R+.

Unser Algorithmus konstruiert iterativ Matchings Mi der Großei = 1, . . . , n. Hierbei soll Mn minimale Kosten haben, d.h.W (Mn) =

∑

e∈Mnκ(e) soll minimal unter allen perfekten Matchings

sein.

Wir gehen wie folgt vor: Sei Mi ein Matching mit minimalen Kostender Große i und Π ein zunehmender Weg mit minimalen Kosten. Wirverschmelzen nun Mi und Π zu einem Matching Mi+1 der Großei + 1 mit minimalen Kosten.

321

Andreas Jakoby



15. Vorlesung, 13.2.2008

Wir betrachten jedoch einen Restgraphen, der sich vom Restgraphvon Folie 200 unterscheidet. Wir definieren:

Fur G bezeichnen wir mit H = (VH , EH) den gewichteten Graphen,den wir analog zu H im Heiratssatzes konstruiert haben. Wir setzenjedoch fur alle e = (u, v) ∈ EH

γ((u, v)) =

0 fur u = q oder v = s

κ(u, v) fur u ∈ V1 und v ∈ V2 .

Fur ein Matching M in G bezeichnen wir mit HM = (VM , EM) dengewichteten Graphen mit VM := V1 ∪ V2 ∪ q, s,

EM := (q, u)|u ∈ V1 \S

e∈M e ∪ (v , s)|v ∈ V2 \S

e∈M e

∪(u, v) ∈ V1 × V2|u, v ∈ E \M

∪(v , u) ∈ V2 × V 1|u, v ∈ M

und wir setzen fur alle e = (u, v) ∈ EM

γ((u, v)) =

8

<

:

0 fur u = q oder v = s

κ(u, v) fur u ∈ V1, v ∈ V2 und u, v 6∈ M

−κ(u, v) fur u ∈ V1, v ∈ V2 und u, v ∈ M .

322

Andreas Jakoby



15. Vorlesung, 13.2.2008

Ein gerichteter Pfad von q nach s in HM ist ein alternierenderPfad:

V2

v1

v2

vm

M = u1, v2

M′ = u1, v1, um, v2

sq

um

u1

V1

u2

Sei M ein Matching in G und Π ein q-s-Pfad in HM , wirkonstruieren ein neues Matching M ′, indem wir alle Kanten von V1

nach V2 in Π zu M hinzufugen, und alle Kanten von V2 nach V1 inΠ aus M loschen. Wir erweitern M uber Π.

Fur einen q-s-Pfad Π = w0, . . . ,wt definieren wir die Kosten von Πals W (Π) :=

∑

i∈1,...,t−2 γ((wi , wi+1)).

323

Andreas Jakoby



15. Vorlesung, 13.2.2008

Aus der Definition von HM und dem erweiterten Matching M ′ bezuglicheines alternierenden Pfades Π folgt:Beobachtung 18 Sei M ein Matching und Π ein alternierenderq-s-Pfades in HM . Sei M ′ das uber Π erweiterte Matching, dann gilt

|M ′| = |M|+ 1 und W (M ′) = W (M) + W (Π) .

Beobachtung 19 M ist genau dann ein perfektes Matching, wenn es inHM keine Kante mehr gibt, die mit q oder s inzident ist.

324

Andreas Jakoby



15. Vorlesung, 13.2.2008

Wir nennen einen Kreis C = w1, . . . ,wt (mit w1 = wt) in HM negativ,wenn

W (C ) :=∑

i∈1,...,t−1

γ((wi ,wi+1)) < 0

ist. Modifizieren wir M uber einen Kreis C , analog wie wir eine Matchinguber einen q-s-Pfad erweitern, so erhalten wir:

Beobachtung 20 Sei M ein perfektes Matching und C ein negativerKreis in HM , dann gilt fur das uber C modifizierte Matching M ′: M ′ istein perfektes Matching und W (M ′) = W (M) + W (C ) < W (M). Somitsind die Kosten fur M nicht minimal.

Wir konnen sogar die Umkehrung dieser Beobachtung zeigen.

325

Andreas Jakoby



15. Vorlesung, 13.2.2008

Lemma 20 Sei M ein perfektes Matching, wobei es in HM keinennegativen Kreis gibt, dann ist M ein minimales Matching.

Beweis von Lemma 20: Sei M ein nicht minimales perfektes Matching,wobei es in HM keinen negativen Kreis gibt. Sei M ′ ein perfektesMatching mit minimalen Kosten.

Sei S die Menge der Kanten, die in einer der Mengen M oder M ′

enthalten sind, aber nicht in beiden.

Die Menge der Kanten in S formen eine Menge vonknotendisjunkten Kreisen C1, . . . ,Ck in HM .

Es gilt W (M ′) = W (M) +∑

i∈1,...,kW (Ci ).

Da W (M ′) < W (M) ist, gibt es einen Kreis Ci mit W (Ci ) < 0.

326

Andreas Jakoby



15. Vorlesung, 13.2.2008

Unser Ziel ist es nun die Matchings M1, . . . ,Mn so zu konstruieren, dass

wir Mi uber einen minimalen q-s-Pfad erweitern und

hierbei kein negativer Kreis in HMi+1entsteht.

Somit erhalten wir nach Lemma 20 ein perfektes Matching Mn mitminimalen Kosten.

327

Andreas Jakoby



15. Vorlesung, 13.2.2008

Um die Analyse zu vereinfachen, fuhren wir fur alle Knoten Gewichteδ : V → R+ ein. Wir nenne δ auf ein Matching abgestimmt, wenn

fur alle Knoten u ∈ V1, welche nicht mit einer Kante aus M inzidentsind, gilt δ(u) = 0,

fur alle u, v ∈ E mit u ∈ V1, v ∈ V2 gilt δ(u) + κ(u, v) ≥ δ(v)und

fur alle u, v ∈ E mit u ∈ V1, v ∈ V2 mit u, v ∈ M giltδ(u) + κ(u, v) = δ(v).

Fur jede Kante (x , y) ∈ EM mit x , y ∈ V1 ∪ V2 des Graphen HM

definieren wir

γδ((x , y)) := δ(x) + γ((x , y))− δ(y) .

328

Andreas Jakoby



15. Vorlesung, 13.2.2008

Beachte: Die Werte γ((x , y)) fur x , y ∈ M und (x , y) ∈ EM sindnegativ und zudem ist x ∈ V2 und y ∈ V1. Aus der Definition vonγδ((x , y)) folgt jedoch, dass fur solche Kanten γδ((x , y)) = 0 ist.

Beobachtung 21 Die Werte γδ((x , y)) sind fur alle Kanten (x , y) in HM

zwischen V1 und V2 bzw. V2 und V1 immer großer oder gleich 0.

Folgen wir nun einem Kreis C in HM , so gilt folglich:

Beobachtung 22 Fur alle Kreise C = w1, . . . ,wt mit w1 = wt in HM gilt

t−1∑

i=1

γδ((wi , wi+1)) =t−1∑

i=1

γ((wi ,wi+1)) ≥ 0 .

Beobachtung 23 Gibt es fur ein Matching M eine abgestimmteGewichtsfunktion δ, dann gibt es in HM keinen negativen Kreis.

329

Andreas Jakoby



15. Vorlesung, 13.2.2008

Betrachten wir nun das Problem einen q-s-Weg mit minimalen Kosten zufinden:

Fur einen Knoten v ∈ V1 ∪ V2 seien dδ,M(v) die minimalen Kosteneines Wegs von q nach v in HM bei Kostenfunktion γδ.

Sei v ∈ V2 ein Knoten, der nicht mit einer Kante des Matchings M

inzident ist, dann sind die minimalen Kosten eines q-v -Wegs in HM

bei Kostenfunktion γ durch dδ,M(v) + δ(v) gegeben.

Es gilt:

Lemma 21 Da die Kostenfunktion γδ positiv ist, konnen wir denkurzesten Weg von q zu jedem Knoten v ∈ V1 ∪ V2 bezuglich derKostenfunktion γδ mit Hilfe des Algorithmus von Dijkstra in ZeitO(|E | · log2 n) bestimmen. Um einen den kurzesten q-s-Pfad bezuglichder Kostenfunktion γ zu bestimmen benotigen wir zusatzliche KostenO(n).

330

Andreas Jakoby



15. Vorlesung, 13.2.2008

Betrachten wir nun die Funktion δ0(u) := 0 fur alle u ∈ V1 undδ0(v) := minu,v∈E κ(u, v) fur alle v ∈ V2, dann erkennen wir:

Beobachtung 24 δ0 ist eine mit M0 := ∅ abgestimmte Gewichtsfunktion.Wir mussen somit nur noch zeigen, dass wir uber unser Verfahren zumErweitern eines Matchings Mi immer garantieren konnen, dass eine furMi+1 abgestimmte Gewichtsfunktion existiert:

Lemma 22 M ein Matching und δ eine fur M abgestimmteGewichtsfunktion. Sei ferner M ′ das Matching, welches wir aus M

erhalten, indem wir dieses bezuglich eines q-s-Wegs mit minimalenKosten in HM erweitern, dann ist

δ′(v) := δ(v) + dδ,M(v)

eine fur M ′ abgestimmte Gewichtsfunktion.

331

Andreas Jakoby



15. Vorlesung, 13.2.2008


x , y ∈ M und x ∈ V1: Es gilt (y , x) ∈ EM ist die einzige mit der wir x betreten konnen. Es gilt dδ,M(x) = dδ,M(y) + γδ((y , x)) mit

γδ((y , x)) := δ(y) + γ((y , x))− δ(x) = 0. Somit erhohen wir sowohl δ′(x) als auch δ′(y) um den Wert dδ,M(y). Die Werte von δ′(x) und δ′(y) erfullen somit bezuglich der Kantex , y die Bedingungen einer fur M ′ abgestimmten Gewichtsfunktion.

332

Andreas Jakoby



15. Vorlesung, 13.2.2008


x , y ∈ M ′ \M und x ∈ V1: Die Kante (x , y) ∈ EM befindet sich auf dem q-y -Weg mit

minimalen Kosten. Es gilt dδ,M(y) = dδ,M(x) + γδ((x , y)) mit

γδ((x , y)) := δ(x) + γ((x , y))− δ(y). Wir erhalten

δ′(x) := δ(x) + dδ,M(x)

δ′(y) := δ(y) + dδ,M(y)

= δ(x) + dδ,M(x) + κ(x , y) .

Fur den neuen Graphen HM′ gilt ferner

γ((y , x)) := −κ(x , y) .

Die Werte von δ′(x) und δ′(y) erfullen somit bezuglich der Kantex , y die Bedingungen einer fur M ′ abgestimmten Gewichtsfunktion.

333

Andreas Jakoby



15. Vorlesung, 13.2.2008


x , y 6∈ M ′ ∪M und x ∈ V1: Der Konten y muss auf einem kurzeren Pfad ohne die Kante (x , y)

in HM von q erreichbar sein. Es gilt dδ,M(y) ≤ dδ,M(x) + γδ((x , y)) mit

γδ((x , y)) := δ(x) + γ((x , y))− δ(y). Wir erhalten

δ′(x) + γ((x , y))− δ′(y)= δ(x) + dδ,M(x) + γ((x , y))− δ(y)− dδ,M(y)≥ 0 .

Die Werte von δ′(x) und δ′(y) erfullen somit bezuglich der Kantex , y die Bedingungen einer fur M ′ abgestimmtenGewichtsfunktion.

334

Andreas Jakoby



15. Vorlesung, 13.2.2008

Algorithmus Bipartites-Matching(G , κ)Eingabe: ungerichteter bipartiter Graph G = (V1 ∪ V2,E ) und

Kostenfunktion κErgebnis: perfektes Matching M mit minimalen Kosten

1: Sei M = ∅ und initialisiere δ := δ0.2: while M ist kein perfektes Matching do3: Finde eine q-s-Weg Π mit minimalen Kosten in HM

4: bezuglich der Kostenfunktion γδ

5: Erweitere M bezuglich Π. Sei M ′ das neue Matching.6: Berechne eine fur M ′ abgestimmte Gewichtsfunktion δ′

7: Setze M := M ′ und δ := δ′.8: end while9: Return(M)

Satz 20 Bipartites-Matching findet ein perfektes Matching mitminimalen Kosten fur ungerichtete bipartite Graphen G = (V1 ∪ V2,E )mit |V1| = |V2| = n in Zeit O(|E | · n · log2 n).

335

Andreas Jakoby



15. Vorlesung, 13.2.2008

10.4 Die Komplexitat des Matching-Problems

Die folgenden Ergebnisse prasentieren wir wieder ohne Beweis:

Satz 21 3DM und X3C sind NP-vollstandig. Das Problem fur einenGraphen zu entscheiden, ob es fur diesen ein perfektes Matching gibt,kann in polynomieller Zeit gelost werden.

Der Beweis der NP-Vollstandigkeit von 3DM und somit auch fur X3Ckann in vielen Lehrbuchern der Komplexitatstheorie nachgelesen werden.Der Beweis, dass ein perfektes Matching in polynomieller Zeit generiertwerden kann, ist sehr aufwendig und ist daher nur in wenigenLehrbuchern zu finden.

336

Documents

1 Einleitung Algorithmik - tcs.uni-luebeck.de · AndreasJakoby UniversitätzuL übeck AlgorithmikWS07/08 1. Vorlesung,24.10.2006 Scheinvergabe: UmeinenScheinfürdieseVorlesungzuerhalten,istdieerfolgreiche