Greedy- und Priority Algorithmen · Was ist ein Greedy-Algorithmus? (2/2) Wir benötigen den...

Greedy- und Priority Algorithmen

Priority-Algorithmen 1 / 80

Was ist ein Greedy-Algorithmus? (1/2)

Greedy-Algorithmen bestimmen eine Lösung iterativ, wobei- jedesmal eine Entscheidung getroffen wird, die „lokal“ am

vielversprechendsten ist.- Getroffene Entscheidungen werden nicht zurückgenommen.

„Definition“ ist nicht präzise.Wie soll man zeigen, dass ein Optimerungsproblem durchGreedy-Algorithmen nicht scharf approximiert werden kann?


Was ist ein Greedy-Algorithmus? (2/2)

Wir benötigen den Begriff eines Datenelements.- Beispiele sind Jobs mit Startzeiten, Verarbeitungszeiten, Fristen

und Strafen für Scheduling Probleme oder- Kanten und ihre Gewichte, bzw Knoten, ihre Gewichte und

Nachbarn für Graph Probleme.

Eine Eingabe besteht aus einer Menge von tatsächlichenDatenelementen.Bestimme in jedem Schritt eine vollständige Ordnung auf allenmöglichen Datenelementen ohne Kenntnis der Eingabe.Der Algorithmus erhält das Datenelement der Eingabe mithöchster Priorität und trifft eine nicht revidierbare Entscheidung.

Ein solcher Algorithmus heisst Priority-Algorithmus.Der Algorithmus heißt nicht-adaptiv, wenn nur eine einzige Ordnungbestimmt wird und ansonsten adaptiv.


Intervall Scheduling

Exakte Algorithmen Interval Scheduling 4 / 80

Beispiel: INTERVALL SCHEDULING

- Aufgaben A1, . . . ,An sind auf einem Prozessor auszuführen.Aufgabe Ai hat den Startpunkt si und den Endpunkt ei .

- Führe möglichst viele Aufgaben aus, ohne dass die Zeitintervalleverschiedener Aufgaben überlappen.

Sortiere die Aufgabe nach aufsteigendem Endpunkt („frühesterEndpunkt zuerst“).

I Diese Entscheidung ist optimal, da die Ausführung jeder anderenAufgabe höchstens weitere Aufgaben ausschließt.

Wir erhalten einen nicht-adaptiven Priority-Algorithmus.I Ein Datenelement ist eine Aufgabe, repräsentiert durch ihren Start-

und Endpunkt.I Der Priority-Algorithmus ordnet Aufgaben nach steigenden

Endpunkten.

Exakte Algorithmen Interval Scheduling 5 / 80

Die Berechnung des Huffman Code

Exakte Algorithmen Huffman Code 6 / 80

HUFFMAN CODE

- Eine Datei D ist aus Buchstaben eines Alphabets Σ aufgebaut.- Für jeden Buchstaben a ∈ Σ ist H(a) die Häufigkeit von a.- Bestimme einen Präfixcode, der D optimal komprimiert.

Huffman’s Algorithmus baut einen binären (Kodier-)Baum BBestimme die beiden Buchstaben a,b geringster Häufigkeit undmache sie zu Kindern eines neuen Knoten va,b.a und b werden entfernt und va,b wird als neuer Buchstabe mitHäufigkeit H(a) + H(b) hinzugenommen.Wiederhole solange, bis nur noch ein Buchstabe vorhanden ist.

- Die Blätter von B sind mit Buchstaben und die Kanten mit 0(Kante zum linken Kind) und 1 (Kante zum rechten Kind) markiert.

- Der Binärcode des Buchstabens a ist die Folge der Kanten-beschriftungen auf dem Weg von der Wurzel zum Blatt von a.


Huffman’s Algorithmus ist ein Priority Algorithmus

Das Datenelement von Buchstaben a besteht aus a undder Häufigkeit von a.

Huffman’s Algorithmus sortiert Buchstaben nach aufsteigendenHäufigkeiten.Die Entscheidungen des Algorithmus bestehen im Einfügen vonKanten zwischen dem Elternknoten va,b und den Kinderknoten aund b.Getroffene Entscheidungen werden nicht zurückgenommen.

Huffman’s Algorithmus ist ebenfalls nicht-adaptiv.


Kürzeste Wege

Exakte Algorithmen Kürzeste Wege 9 / 80

KÜRZESTE WEGE

- Sei G = (V ,E) ein gerichteter Graph mit Quelle s ∈ V undKantengewichtung Länge : E → R>0.

- Bestimme kürzeste Wege von s nach v für alle Knoten v ∈ V .

Setze S = {s}. In jedem Schritt berechnet Dijkstra’s Algorithmusein Array D mit

D[v ] = Länge eines kürzesten Weges von s nach v ,der bis auf v nur in S verläuft.

Wenn v ∈ V \ S den kleinsten D-Wert besitzt, dannI füge v zu S hinzuI und aktualisiere die D-Werte der Nachbarn von v .

Die Aktualisierung garantiert, dass D weiterhin die Länge „kürzesterS-Wege“ wiedergibt.


Dijkstra’s Algorithmus ist ein Priority-Algorithmus

Das Datenelement von Knoten v ist:v mitsamt seinen Nachbarn und den Distanzen zu den Nachbarn.

Zu Anfang:I In der ersten Ordnung erhalten alle möglichen Datenelemente von

s die höchste Priorität.I Der Algorithmus erhält das (tatsächliche) Datenelement von s und

initialisiert das Array D.Nach jedem weiteren Schritt:

I Dijkstra’s Algorithmus bestimmt den Knoten v ∈ V \S mit kleinstemD-Wert

I und berechnet eine Ordnung, die allen möglichen Datenelementenvon v die größte Priorität gibt.

Dijkstra’s Algorithmus ist ein adaptiver Priority-Algorithmus.


Die Berechnung minimaler Spannbäume

Exakte Algorithmen Minimale Spannbäume 12 / 80

MINIMALER SPANNBAUM

- G ist ein ungerichteter zusammenhängender Graph, dessenKanten Gewichte erhalten.

- Bestimme einen leichtesten Spannbaum für G.

Kruskal’s Algorithmussortiert die Kanten nach aufsteigendem Gewicht.Beginnend mit der leichtesten Kante e:

Füge Kante e ein, wenn kein Kreis geschlossen wird.

Kruskal’s Algorithmus ist ein nicht-adaptiver Priority Algorithmus:Die Datenelemente sind die Kanten und ihre Gewichte.

Exakte Algorithmen Minimale Spannbäume 13 / 80

Matroide

Exakte Algorithmen Matroide 14 / 80

Monotone Teilmengensysteme

(P,X ) ist ein monotones Teilmengensystem, falls- P eine Menge von Teilmengen von X ist und- aus Y1 ∈ P und Y2 ⊆ Y1 stets Y2 ∈ P folgt.

Wir nennen die Mengen Y ∈ P unabhängig.Im Optimierungsproblem für ein monotones Teilmengensystemerhält jedes Element x ∈ X ein Gewicht wx > 0. Das Ziel ist dieBestimmung einer schwersten unabhängigen Menge.

- MINIMLER SPANNBAUM wie auch INDEPEDENT SET sindOptimierungsprobleme für monotone Teilmengensysteme.

- Das erste Problem ist einfach, das zweite sehr schwer. Warum?


Der Greedy Algorithmus für Matroide

Was sollte der Greedy-Algorithmus für ein monotonesTeilmengensystem (P,X ) machen?

Anfänglich sei Y = ∅.Füge das schwerste Element x zu Y hinzu, so dass Y ∪ {x}unabhängig bleibt.Gib Y aus, wenn Y nicht erweitert werden kann.

Wir nennen (P,X ) ein Matroid, wenn der Greedy-Algorithmus für alleGewichtungen eine schwerste unabhängige Menge bestimmt.


Das Graph-Matroid


Das Graph-Matroid

Sei G = (V ,E) ein ungerichteter, zusammenhängender Graph.- Wir sagen, dass eine Menge E ′ ⊆ E unabhängig ist, wenn die

Kanten in E ′ einen Wald definieren.- Definiere P(E) als die Menge aller unabhängigen Mengen.- (P(E),E) ist ein monotones Teilmengensystem und wird das

Graph-Matroid genannt.

Der Greedy-Algorithmus versucht, einen schwersten Spannbaume zuberechnen. Betrachte deshalb die neuen Kantengewichte

w ′e := max{wf | f ∈ E} − we.

Kruskal’s Algorithmus für die Gewichtung we berechnet leichtesteSpannbäume.Der Greedy Algorithmus für die Gewichtung w ′e berechnetdenselben Baum wie Kruskals’s Algorithmus für we.Exakte Algorithmen Matroide 18 / 80

Weitere monotone Teilmengensysteme

Der Greedy-Algorithmus berechnet einen schwersten Spannbaum:Das Graph-Matroid (P(E),E) ist tatsächlich ein Matroid.

Sei G = (V ,E) ein ungerichteter Graph.I Nenne V ′ ⊆ V unabhängig, wenn keine zwei Knoten in V ′ durch

eine Kante verbunden sind.I Q(V ) ist die Klasse aller unabhängigen Mengen.I Ist (Q(V ),V ) ein Matroid?

Sei V = {v1, . . . , vm} eine Menge von Vektoren in einemVektorraum.

I Nenne V ′ ⊆ V unabhängig, wenn V ′ eine Menge von linearunabhängigen Vektoren ist.

I R(V ) ist die Klasse aller unabhängigen Mengen.I Ist (R(V ),V ) ein Matroid?

Ja! (R(V ),V ) wird Matrix-Matroid genannt.


Charakterisierungen von Matroiden

Für ein monotones Teilmengensystem (P,X ) sind äquivalent:(a) (P,X ) ist ein Matroid.(b) Die Ergänzungseigenschaft gilt: Für je zwei unabhängige

Mengen Y1,Y2 mit |Y1| = |Y2| − 1 gibt es ein x ∈ Y2 \ Y1, so dassY1 ∪ {x} unabhängig ist.

(c) Die Maximalitätseigenschaft gilt: Alle nicht vergrößerbarenunabhängigen Teilmengen einer beliebigen Menge Z ⊆ Xbesitzen dieselbe Größe.

Warum ist das Graph-Matroid ein Matroid?I Eigenschaft (c) gilt: Für jede Teilmenge Z von Kanten haben alle

nicht-vergrößerbaren Spannwälder dieselbe Kantenzahl.Warum ist das Matrix-Matroid ein Matroid?

I Eigenschaft (c) gilt: Die Dimension des von einer Teilmenge Zaufgespannten Raums stimmt überein mit der Mächtigkeitirgendeiner nicht-vergrößerbaren unabhängigen Teilmenge von Z .


Matroid-Eigenschaft⇒ Ergänzungseigenschaft

Sei (P,X ) ein Matroid.

Y1 und Y2 seien unabhängig mit p := |Y1| = |Y2| − 1, aberY1 ∪ {x} /∈ P für jedes x ∈ Y2 \ Y1.

Wir falsifizieren den Greedy-Algorithmus mit den Gewichten

wx :=

p + 2 falls x ∈ Y1p + 1 falls x ∈ Y2 \ Y10 sonst.

I Greedy wählt p Elemente aus Y1 und erreicht das Gesamtgewicht|Y1| · (p + 2) = p · (p + 2) = p2 + 2p,

I während die unabhängige Menge Y2 das größere Gewicht vonmindestens (p + 1)2 = p2 + 2p + 1 besitzt.


Ergänzungseigenschaft⇒ Maximalitätseigenschaft

Wenn die Maximalitätseigenschaft für Z ⊆ X nicht gilt, dann gibtes zwei größte, unabhängige Teilmengen Y1,Y2 ⊆ Z mit

|Y1| < |Y2|.

Sei Y ∗2 ⊆ Y2 eine beliebige Teilmenge mit der Eigenschaft

|Y1| = |Y ∗2 | − 1.

Mit der Ergänzungseigenschaft:I Wir können Y1 um ein Element aus Y ∗2 ⊆ Y2 vergrößern.I Y1 ist nicht größtmöglich — Widerspruch.


Maximalitätseigenschaft⇒ Matroideigenschaft (1/2)

Eine beliebige Gewichtung wx > 0 für x ∈ X ist gegeben.I Der Greedy-Algorithmus bestimmt eine nicht-vergrößerbare

unabhängige Menge Y .I Y ∗ sei eine schwerste unabhängige Menge.

Maximalitätseigenschaft: |Y | = |Y ∗| mit Z = X .Nummeriere die Elemente von Y und Y ∗ gemäß absteigendemGewicht:

Y = {y1, . . . , ym} , Y ∗ = {y∗1 , y∗2 , . . . , y∗m} .

Zeige: wyi > wy∗i für i = 1, . . .m.


Maximalitätseigenschaft⇒ Matroideigenschaft (2/2)

Warum gilt stets wyi > wy∗i ?

i = 1: Stimmt, denn Greedy wählt das schwerste Element.i − 1⇒ i : Wähle

Z ∗ := {x ∈ X | wx > wy∗i }.

I Wenn wyi < wy∗i, dann ist {y1, . . . , yi−1} eine nicht vergrößerbare

unabhängige Teilmenge von Z ∗,I aber {y∗1 , y∗2 , . . . , y∗i } ⊆ Z ∗ ist um ein Element größer.I Wir haben einen Widerspruch zur Maximalitätseigenschaft erhalten.


Matroid-Scheduling


MATROID SCHEDULING

- Die Aufgaben A1, . . . ,An sind auf einem Prozessor auszuführen.- Aufgabe Ai kann in einem Schritt ausgeführt werden. Wenn aber

keine Ausführung zur Frist fi gelingt, dann fällt die Strafe bi an.- Maximiere die Summe der „Nicht-Strafen“.

Sei X := {A1, . . .An} und P bestehe aus allen ohneFristüberschreitung ausführbaren Teilmengen von Aufgaben.

Wenn Y ∈ P, dann gibt es zu jeden Zeitpunkt t höchstens tAufgaben in Y mit Frist fi 6 t .

Zeige, dass (P,X ) die Ergänzungseigenschaft erfüllt.I Dann ist (P,X ) ein Matroid und der Greedy-Algorithmus löst das

Scheduling Problem optimal.I Entschuldigung, der Greedy Algorithmus bestimmt doch nur eine

schwerste Menge fristgerecht ausführbarer Aufgaben!? Und wassind denn überhaupt die Gewichte?


Wie erhalten wir ein Scheduling der Aufgaben?

Das Gewicht von Ai ist bi: Der Greedy-Algorithmus maximiert dieNicht-Strafe und minimiert damit die Strafe.

Aber der Greedy-Algorithmus bestimmt nur eine Teilmenge T vonfristgerecht ausführbaren Aufgaben. Wie erhält man ein Scheduling?

Führe die Aufgaben in T gemäß aufsteigender Frist aus.Alle nicht in T enthaltenen Aufgaben werden am Ende inbeliebiger Reihenfolge ausgeführt.


Wird die Ergänzungseigenschaft erfüllt?

Die Mengen Y1,Y2 ∈ P mit |Y1| = |Y2| − 1 seien beliebig.

Gibt es A ∈ Y2, so dass Y1 ∪ {A} ohne Fristüberschreitungausführbar ist?Wähle t > 0 maximal mit

|{Aj ∈ Y2 | fj 6 t}| 6 |{Aj ∈ Y1 | fj 6 t}|.

Ein solches maximales t existiert, da |Y2| > |Y1|.Es gibt also eine Aufgabe A ∈ Y2 \ Y1 mit Frist t + 1. Aber t istmaximal, also

∀s > t + 1 : |{Aj ∈ Y1 | fj 6 s}| < |{Aj ∈ Y2 | fj 6 s}| 6 s.

Die Aufgaben in Y1 ∪ {A} sind fristgerecht ausführbar:I Schiebe Aufgabe A zum Zeitpunkt t + 1 in die fristgerechte

Ausführung der Aufgaben in Y1 ein.I Verschiebe alle nach Zeit t ausgeführten Aufgaben um 1 Schritt.


k -Matroide

k -Matroide 29 / 80

k -Matroide (1/2)

Sei k ∈ REin monotones Teilmengensystem (P,X ) heißt ein

k−Matroid,

wenn der Greedy-Algorithmus für monotone Teilmengensystemek-approximative Lösungen für jede Gewichtung bestimmt.

1-Matroide sind Matroide.k muss keine natürliche Zahl sein.Lassen sich k -Matroide wieder über die Ergänzungs- undMaximalitätseigenschaft charakterisieren?

k -Matroide 30 / 80

k -Matroide (2/2)

Für ein monotones Teilmengensystem (P,X ) sind äquivalent:(a) (P,X ) ist ein k-Matroid.(b) Die k-Ergänzungseigenschaft gilt: Für je zwei unabhängige

Mengen Y1,Y2 mit |Y2| > k · |Y1| gibt es ein x ∈ Y2 \ Y1, so dassY1 ∪ {x} unabhängig ist.

(c) Die k-Maximalitätseigenschaft gilt: Für jede beliebige TeilmengeZ ⊆ X und je zwei nicht vergrößerbare unabhängige TeilmengenY1,Y2 ⊆ Z gilt |Y2| 6 k · |Y1|.

Die Argumentation ist ähnlich wie für die Charakterisierungen vonMatroiden.

k -Matroide 31 / 80

Eine hinreichende Bedingung (1/2)

Ein monotones Teilmengensystem (P,X ) heißt k-erweiterbar, wennfür je zwei unabhängige Mengen Y1 ⊂ Y2 und für jedes Elementx 6∈ Y2 gilt:

Wenn Y1 ∪ {x} unabhängig ist, dann gibt es eine TeilmengeT ⊆ Y2 \ Y1 von höchstens k Elementen, so dass (Y2 \ T ) ∪ {x}unabhängig ist.

Nach Herausnahme von bis zu k Elementen kann x auch zur größerenMenge Y2 hinzugefügt werden.

k -Matroide 32 / 80

Eine hinreichende Bedingung (2/2)

Wenn das monotone Teilmengensystem (P,X ) k-erweiterbar ist,dann ist (P,X ) ein k-Matroid.

Sei (P,X ) k -erweiterbar. Verifiziere die k -Ergänzungseigenschaft:Für unabhängige Mengen Y1 und Y2 mit |Y2| > k · |Y1| bestimmex ∈ Y2 \ Y1, so dass Y1 ∪ {x} unabhängig ist.

O.B.d.A gilt Y1 6⊂ Y2. Wähle ein beliebiges u ∈ Y1 \ Y2 undbetrachte die unabhängigen Mengen Z1 := Y1 ∩ Y2 und Z2 := Y2.

I (P,X ) ist k -erweiterbar. Also gibt es eine Teilmenge T ⊆ Z2 \ Z1= Y2 \ Y1 mit |T | 6 k , so dass Y ′2 = (Y2 \ T ) ∪ {u} unabhängig ist.

I Wenn Y1 noch keine Teilmenge von Y ′2 ist, dann wiederhole dasVorgehen mit den Mengen Y1 und Y ′2.

I Nur Elemente, die nicht zu Y1 gehören, werden aus Y2 entfernt:Nach höchstens |Y1 \ Y2| 6 |Y1| Schritten erhalten wir eineunabhängige Menge Y ′2 mit Y1 ⊆ Y ′2.

I Aber |Y2| > k · |Y1| und Y1 ist eine echte Untermenge von Y ′2.

k -Matroide 33 / 80

Der Durchschnitt von k Matroiden

k -Matroide 34 / 80

Der Durchschnitt von k Matroiden (1/2)

Ein Durchschnitt von k Matroiden ist k -erweiterbar und deshalb eink -Matroid.

k = 1: Warum ist ein Matroid 1-erweiterbar?

Für unabhängige Mengen Y1 ⊂ Y2 und x 6∈ Y2 sei Y1 ∪ {x}unabhängig.

Finde y ∈ Y2 \ Y1, so dass Y2 \ {y} ∪ {x} unabhängig ist.

Ergänzungseigenschaft für Matroide: Vergrößere die unabhängigeMenge Y1 ∪ {x} mit Elementen aus Y2 \ Y1.Wiederhole, bis wir eine unabhängige Teilmenge Y ′1 mitY1 ∪ {x} = Y ′1 ⊆ Y2 ∪ {x} und |Y ′1| = |Y2| erhalten.Da x 6∈ Y2, besteht Y2 \ Y ′1 aus genau einem Element y .

Aber dann ist Y2 \ {y} ∪ {x} = Y ′1 unabhängig und das war zuzeigen.

k -Matroide 35 / 80

Der Durchschnitt von k Matroiden (2/2)

Ein Durchschnitt von k Matroiden ist also ein Durchschnitt von k vielen1-erweiterbaren monotonen Mengensystemen.

Warum ist der Durchschnitt von k vielen 1-erweiterbarenmonotonen Mengensystemen k -erweiterbar?

I Für Teilmengen Y1 ⊂ Y2 und x 6∈ Y2 sei also Y1 ∪ {x} unabhängig.I Dann gibt es im i .ten monotonen Mengensystem ein Element

yi ∈ Y2 \Y1, so dass Y2 \ {yi} ∪ {x} im i .ten System unabhängig ist.I Aber dann ist Y2 \ {y1, . . . , yk} ∪ {x} eine unabhängige Menge des

Durchschnitts.

Und das war zu zeigen.

k -Matroide 36 / 80

Das f -Matching Problem

k -Matroide 37 / 80

f -MATCHING (1/2)

- G = (V ,E) sei ein ungerichteter Graph, dessen Kantennicht-negative Gewichte besitzen.

- Sei f : V → N eine Funktion. Ein f -Matching ist eineKantenmenge M ⊆ E , so dass die Anzahl mit v inzidenter Kantendurch f (v) für jeden Knoten v beschränkt ist.

- Bestimme ein schwerstes f -Matching.

Unser Mengensystem besteht also aus der Grundmenge E und allenTeilmengen von E , die f -Matchings entsprechen.

Zeige, dass das Mengensystem 2-erweiterbar ist: Der GreedyAlgorithmus ist also 2-approximativ.

k -Matroide 38 / 80

f -MATCHING (2/2)

Warum sind f -Matchings 2-erweiterbar?

Betrachte zwei f -Matchings Y1 ∪ {e},Y2 mit Y1 ⊂ Y2, wobei Kantee = {u, v} nicht in Y2 liege.Wenn Y2 ∪ {e} ein f -Matching ist, dann sind wir fertig.Ist Y2 ∪ {e} kein f -Matching,

I dann besitzt Y2 bereits f (u) Kanten, die inzident mit u, oder f (v)Kanten, die inzident mit v sind.

I Entferne eine mit u und eine mit v inzidente Kante aus Y2 undsetze e ein!

k -Matroide 39 / 80

MAX-TSP

k -Matroide 40 / 80

MAX-TSP (1/2)

- Ein vollständiger gerichteter Graph mit nicht-negativenKantengewichten ist gegeben.

- Bestimme eine Rundreise maximaler Länge. (Eine Rundreisebesucht jeden Knoten genau einmal.)

Die Grundmenge besteht aus allen Kanten. Eine Teilmenge derKanten ist unabhängig, wenn

I ihre Kanten Knoten-disjunkte Pfade oder eine Rundreise bilden.

Zeige, dass dieses Mengensystem 3-erweiterbar ist.Der Greedy-Algorithmus berechnet also eine 3-approximativeLösung. Der beste von effizienten Algorithmen erreichbareApproximationsfaktor ist 8/5.

k -Matroide 41 / 80

MAX TSP (2/2)

Warum sind Knoten-disjunkte Pfade 3-erweiterbar?

Y1 ∪ {e} und Y2 seien zwei unabhängige Mengen mit Y1 ⊂ Y2,wobei die Kante e = (u, v) nicht in der Menge Y2 liege.Entferne zuerst, falls vorhanden, die eine u verlassende und dieeine in in v eintreffende Kante aus Y2.Füge e zu Y2 hinzu und jeder Knoten hat höchstens eineeintreffende und eine ausgehende Kante.

Wenn die Hinzunahme von e unzulässig ist, dann muss es genaueinen Kreis geben, der keine Rundreise ist, aber e benutzt.

Aber dann hat dieser Kreis eine Kante e′, die nicht zur Menge Y1gehört.

Entfernen die Kante e′, der Kreis ist gebrochen, und wir haben eineunabhängige Menge erhalten.

k -Matroide 42 / 80

Sequenzierung

Shortest Common Superstring 43 / 80

Sequenzierung

Bestimme die Reihenfolge der Basenpaare für einen Strang einesDNA-Moleküls.

Direkte Sequenzierung:I Schneide iterativ kurze Präfixe von ungefähr 500 Basenpaaren aus

der DNA Sequenz undI sequenziere die kleinen Fragmente.

Extrem zeitaufwändiger Prozess, der nicht für die Sequenzierunglanger Sequenzen geeignet ist.

Shotgun Sequenzierung:I zerschneide die Sequenz parallel, an fast zufällig verteilten

Positionen und sequenziere die entstehenden Fragmente.I Leider geht die Reihenfolge der Fragmente verloren.I Führe den Prozess für genügend viele Kopien der Sequenz aus.

Bestimme die korrekte Reihenfolge algorithmisch.


Shotgun Sequenzierung und Fragment Assmenbly

(1) Führe das Shotgun-Verfahren durch.(2) Bestimme Reads für jedes Fragment, also die Folge der ungefähr

500 Basenpaare an einem Ende des Fragments.(3) Fragment-Assembly: Rekonstruiere die DNA-Sequenz aus den

Reads.

Die Aufgabenstellung der Informatik:

Fragment Assembly- Es gibt viele „Superstrings“, also Strings, die jeden Read als

Teilstring besitzen.- Sollten wir den kürzesten Superstring wählen?


Was so alles passieren kann

(1) Fehler beim Sequenzieren der Fragmente: Einige Basen werdenfalsch angegeben.

(2) Fehler beim Kopieren: Zum Beispiel können sich Fragmente einerWirt-DNA mit den Fragmenten der DNA-Sequenz vermischen.

(3) Fragmente von beiden Strängen des Moleküls tauchen auf.(4) Überdeckungslücken: Einige Regionen der DNA-Sequenz werden

möglicherweise nicht von Fragmenten überdeckt.(5) Lange Repeats tauchen auf:

I Repeats sind wiederholt in der DNA-Sequenz auftretendeTeilstrings.

I Beispielsweise gibt es ein 300 Basenpaare langes Segment, dasmit 5-15 prozentiger Variation mehr als 1 Million Mal immenschlichen Genom vorkommt:

Datenmüll pur!


Shortest Common Superstring


SHORTEST COMMON SUPERSTRING

- Eine Menge U von Strings ist gegeben.- Suche einen String S minimaler Länge, der alle Strings in U als

Teilstrings enthält.

Beachte, dass sich kürzeste Superstrings nicht unbedingt alsLösung des Fragment Assembly Problems aufdrängen.

Lange Repeats!SHORTEST COMMON SUPERSTRING ist deshalb eine sehroptimistische Abstraktion.

In praktischen Anwendungen werden Methoden für SHORTESTCOMMON SUPERSTRING mit anderen Verfahren kombiniert, umFehlertoleranz zu erreichen.


Overlaps

Wir können annehmen, dass kein String in U Teilstring eines anderenStrings in U ist.

overlap(u, v) die Länge des längsten Suffix von u, der auch Präfixvon v undpräfix(u, v) = |u| − overlap(u, v) ist die Länge des nichtüberdeckten Präfixes von u.Die Menge U bestehe aus k Strings. Für eine Bijektionπ : {1, . . . , k} → U erhalten wir den Superstring

S(π) = präfix(π(1), π(2)) · · · präfix(π(k − 1), π(k)) · π(k).

Wie lang ist S(π)?

|S(π)| =∑u∈U

|u| −k−1∑i=1

overlap(π(i), π(i + 1)).

Shortest Common Superstring Overlaps 49 / 80

Overlaps und Perioden

Es ist |S(π)| =∑

u∈U |u| −∑k−1

i=1 overlap(π(i), π(i + 1)).

Wir müssen also eine Permutation π mit einer möglichst großenOverlap-Summe bestimmen.Wie groß können Overlaps werden?

Das hängt sehr stark von den Perioden der Strings ab!

- Fasse einen String v als zyklischen String auf:Klebe die ersten und letzten Buchstaben von v aneinander.

- String u hat die Periode v , falls wir u vollständig um v wickelnkönnen.

- v ist die minimale Periode von u, falls u die Periode v hat und falls|v | die minimale Länge einer Periode von u ist.

Shortest Common Superstring Overlaps 50 / 80

Das Overlap Lemma

Shortest Common Superstring Das Overlap Lemma 51 / 80

Das Overlap Lemma

Für koperiodische Strings u1,u2, also Strings mit gleicher Periode,kann overlap(u1,u2) sehr gross werden.Und für aperiodische Strings, also Strings mit verschiedenenminimalen Perioden?

Das Overlap-Lemma (ohne Beweis)Für aperiodische Strings u1 und u2 mit Periodenlängen p1,p2 ist

overlap(u1,u2) < p1 + p2.

Ein Beispiel:I u1 = abk abk und u2 = bk abbk ab haben die Periodenlängen k + 1,

bzw. k + 2.I max{k + 1, k + 2} < overlap(u1,u2) = 2k + 1 < (k + 1) + (k + 2).


Das zyklische Überdeckungsproblem


Zyklische Überdeckungen

(a) Für einen String v sei v∞ der unendlich oft mit sich selbstkonkatenierte String v .

(b) Ein String v ist eine zyklische Überdeckung eines Strings u, wennu ein Teilstring des Strings v∞ ist.

(c) U und V sind Mengen von Strings:I V ist eine zyklische Überdeckung von U, wenn jedes u ∈ U von

mindestens einem String v ∈ V zyklisch überdeckt wird.I

∑v∈V |v | ist die Länge der Zyklus-Überdeckung V .

(d) ZYKLUS ÜBERDECKUNG: Bestimme eine Zyklus-Überdeckungminimaler Länge für eine Menge U von Strings.

Und wenn wir minimale Zyklusüberdeckungen effizient bestimmenkönnen?


Bestimmung kurzer Superstrings

(1) Eine Menge U von Strings ist gegeben.Kein String aus U ist Teilstring eines anderen Strings aus U.

(2) Bestimme eine minimale Zyklus-Überdeckung V von U.(3) Betrachte alle Zyklen v ∈ V nacheinander.

I Uv besteht aus allen von v zyklisch überdeckten Strings aus U.I Das erste Vorkommen der Strings aus Uv in v∞ definiert eine

Ordnung auf den Strings aus Uv .Bestimme den durch diese Ordnung induzierten Superstring Sv .

Kommentar: Wir erhalten Sv , wenn wir den Zyklus v „aufbrechen“,also die Strings in Uv gemäß ihrer Ordnung maximal übereinanderschieben, aber den letzten String nicht über den ersten schieben.

(4) Gib die Konkatenation Πv∈V Sv der Superstrings als Resultat aus.


Die Analyse (1/2)

Sei V eine minimale Zyklusüberdeckung von U.I Für v ∈ V sei uv der letzte von v zyklisch überdeckte String.I Wie lang ist Sv ?

|Sv | 6 |v |+ |uv |.

Wir berechnen einen Superstring der Länge L mit

L 6∑v∈V

(|v |+ |uv |).

Sei L∗ die Länge eines kürzesten Superstrings S∗ auf den Stringsuv für alle v ∈ V .

Die Strings u1, . . . ,ur mögen in dieser Reihenfolge in S∗

vorkommen. Dann ist

L∗ =r∑

i=1

|ui | −r−1∑i=1

overlap(ui ,ui+1) >r∑

i=1

|ui | −r−1∑i=1

(|vi |+ |vi+1|)


Die Analyse (2/2)

Wir wissen:(*) L 6

∑v∈V (|v |+ |uv |)

(*) und L∗ >∑r

i=1 |ui | −∑r−1

i=1 (|vi |+ |vi+1|) >∑r

i=1 |ui | − 2∑

v∈V |v |.

Als Konsequenz:

L 6∑v∈V

|v |+r∑

i=1

|ui | < L∗ + 3 ·∑v∈V

|v | 6 4 · Lopt,

denn die Länge Lopt eines kürzesten Superstrings ist mindestens sogroß wie L∗ und die Länge einer kürzesten Zyklusüberdeckung.

Unser Ansatz berechnet eine 4-approximative Lösung für SHORTESTCOMMON SUPERSTRING.


Wie berechnet man eine minimaleZyklusüberdeckung?

Shortest Common Superstring Zyklusüberdeckung 58 / 80

Die Monge Ungleichung

Übungsaufgabeu1,u2, v1, v2 sind vier beliebige Strings mit

overlap(u1, v1) = max { overlap(ui , vj) | 1 6 i , j 6 2}.

Dann gilt die Monge-Ungleichung (Gaspard Monge 1746-1818):

overlap(u1, v1) + overlap(u2, v2) > overlap(u1, v2) + overlap(u2, v1).


Bestimmung einer minimalen Zyklusüberdeckung

(1) Die Eingabe besteht aus einer Menge U von Strings.(2) Bestimme den gerichteten Graph G = (U,U × U) mit den

Kantengewichten overlap(u1,u2).(3) Sortiere die Kanten in E nach ihrem Gewicht. Setze E∗ = ∅.(4) Wiederhole, solange E 6= ∅:

(4a) Bestimme die Kante e = (u1,u2) ∈ E mit größtem Overlap.Füge e zu E∗ hinzu.

(4b) Entferne alle den Knoten u1 verlassenden und alle den Knoten u2erreichenden Kanten.

(5) Berechne eine Zyklus-Überdeckung aus den durch E∗ definiertenKreisen.


Der Greedy Superstring Algorithmus

Shortest Common Superstring Der Greedy Algorithmus 61 / 80

Der Greedy Superstring Algorithmus (1/2)

Der wahrscheinlich im Allgemeinen bessere Algorithmus:

(1) Gegeben ist eine Menge U von Strings, wobei keine zwei Stringsin U Teilstrings voneinander sind.

(2) Wiederhole, solange bis |U| = 1.

(2a) Bestimme zwei Strings u 6= v ∈ U mit overlap(u, v) größtmöglich.(2b) Ersetze U durch U \ {u, v} ∪ {w}, wobei w = praefix(u, v) · v .

Kommentar: Schiebe v weitestgehend über u, und wir erhalten w .

(3) Gib den verbleibenden String in U als Superstring aus.


Der Greedy Superstring Algorithmus (2/2)

Offene FrageWas ist der Approximationsfaktor des Greedy Algorithmus?

Was ist bekannt?Der Approximationsfaktor ist höchstens vier,aber mindestens zwei:

u1 = c(ab)n,

u2 = (ba)n,

u3 = (ab)nd .

I Die optimale Reihenfolge ist u1,u2,u3 mit Länge 2n + 4,I Greedy wählt die Reihenfolge u1,u3,u2 mit Länge 4n + 2.


Fazit

Wir haben eine minimale Zyklusüberdeckung mit einemnicht-adaptiven Priority Algorithmus exakt bestimmt.Der Greedy Superstring Algorithmus ist fast identisch, darf aberkeine Kreise schließen.

Eine der wichtigsten Probleme im Gebiet der String Algorithmen:Bestimme den Approximationsfaktor des Greedy SuperstringAlgorithmus.


Das Travelling Salesman Problem

Heuristiken für TSP 65 / 80

TSP

- Greedy-Algorithmen sind zu schwach, um schwierigeOptimierungsprobleme exakt zu lösen.

- Aber ihr Einsatzgebiet als Heuristiken für die approximativeLösung ist extrem breit.

- Wir betrachten exemplarisch das metrische Travelling SalesmanProblem (TSP).

n Orte v1, . . . , vn sowie Distanzen d(vi , vj) > 0 zwischen je zweiverschiedenen Orten sind gegeben.Eine Rundreise entspricht einer Permutation vπ(1), vπ(2), . . . , vπ(n)der Orte:

Wenn vπ(i) besucht wird, dann wird vπ(i+1) für i < n, bzw v1 für i = nals nächster Ort besucht.

Bestimme eine Rundreise minimaler Länge.


Wie schwierig ist TSP?

Das Sprachenproblem HAMILTONSCHER KREIS

Gibt es einen Hamiltonschen Kreis, also einen Kreis, der alleKnoten eines ungerichteten Graphen G = (V ,E) genaueinmal besucht?

ist NP-vollständig.

Sei G = ({1, . . . ,n},E) eine Eingabe für HAMILTONSCHERKREIS. Erfinde die Instanz T (G) für TSP:

- Die Orte entsprechen den Knoten von V .- Für alle Knoten u, v ∈ V : Wenn {u, v} eine Kante in G ist, dann

setzen wir d(u, v) = 1 und ansonsten d(u, v) = D.

G besitzt genau dann einen Hamiltonschen Kreis, wenn T (G)eine Rundreise der Länge höchstens n besitzt.Besitzt G hingegen keinen Hamiltonschen Kreis, dann hat jedeRundreise mindestens die Länge n − 1 + D.


Das metrische TSP


Das metrische TSP

Es gelte P 6= NP.- Setze D = n · 2n und der Approximationsfaktor effizienter

Algorithmen ist mindestens n−1+Dn > 2n.

- Es gibt keinen effizienten 2n-approximativen Algorithmus für TSP!

TSP ist viel zu schwierig.Wir betrachten das einfachere und glücklicherweiseinteressantere metrische TSP:

Wir verlangen, dass die Distanzen zwischen den Orten (oderPunkten) durch eine Metrik gegeben sind: d ist genau dann eineMetrik, wenn für alle Punkte u, v ,w gilt:

- d(u, u) = 0,- d(u, v) = d(v , u) und- d(u, v) + d(v ,w) 6 d(u,w).


Die Spannbaum Heuristik

- G ist der vollständige Graph mit allen Orten als Knoten(und Kanten zwischen je zwei Knoten).

- Die Kante {u, v} erhält das Gewicht d(u, v).

Die Spannbaum Heuristik:I Berechne einen minimalen Spannbaum B.I Besuche alle Orte gemäß einem Präorderdurchlauf von B.

Wie lang ist die Rundreise?I Irgendein Rücksprung während der Präorder-Traversierung ist nicht

länger als die Länge aller beteiligten Kanten⇒ Die Traversierungist also höchstens doppelt so lang wie das Gewicht von B.

I Andererseits ist jede Rundreise mindestens so lang wie dasGewicht von B.

Die Spannbaum Heuristik ist 2-approximativ.

Heuristiken für TSP Die Spannbaum Heuristik 70 / 80

Die Spannbaum Heuristik: Ein Beispiel

Durchlaufe den minimalen Spannbaum B in Präorder-Reihenfolge.

��

��

��

��

1

3

5

2

4

��

��

��

��

1

3

5

2

4

Wie lang ist unsere Rundreise höchstens?

d1,2 + (d2,1 + d1,3) + d3,4 + (d4,3 + d3,5) + (d5,3 + d3,1).

Alle Kanten des Spannbaums treten genau zweimal auf. Es ist

Gewicht(B) 6 minimale Länge einer Rundreise6 Länge unserer Rundreise 6 2Gewicht(B).

Heuristiken für TSP Die Spannbaum Heuristik 71 / 80

Der Algorithmus von Christofides

Heuristiken für TSP Der Algorithmus von Christofides 72 / 80

Der Algorithmus von Christofides (1/2)

Sei G ein ungerichteter, zusammenhängender Graph.G besitzt eine Euler-Tour –einen Kreis, der jede Kante genau einmaldurchläuft–⇔ Jeder Knoten besitzt eine gerade Anzahl von Nachbarn.

⇒ I Wenn es eine Euler-Tour gibt, betritt man auf einer solchen Tourjeden Knoten so oft, wie man ihn verlässt.

I Da jede Kante auf der Tour genau einmal besucht wird, besitztjeder Knoten eine gerade Anzahl von Nachbarn.

⇐ I Jeder Knoten besitzt eine gerade Anzahl von Nachbarn:Der Graph kann in kantendisjunkte Kreise zerlegt werden.

I Verschmelze zwei Kreise mit einem gemeinsamen Knoten zueinem Kreis.

I G ist zusammenhängend: Alle Kreise lassen sich zu einerEuler-Tour verschmelzen.


Der Algorithmus von Christofides (2/2)

(1) Die Eingabe besteht aus einer Menge V = {1, . . . ,n} von nPunkten und der Metrik d .

(2) Setze G := (V , {{v ,w} | v ,w ∈ V , v 6= w }) und weise der Kantee = {v ,w} die Distanz de = dv ,w zu.

(3) Berechne einen minimalen Spannbaum B für G.(4) Sei U die Menge der Knoten von B mit einer ungeraden Anzahl

von Nachbarn in B. Berechne ein minimales Matching M derGröße 1

2 · |U| auf den Knoten in U.(5) Füge die Kanten in M zu den Kanten in B hinzu und konstruiere

eine Euler-Tour E .(6) Berechne aus E eine Rundreise durch Abkürzungen.


Der Algorithmus von Christofides: Die Analyse

Jeder ungerichtete Graph G = (V ,E) besitzt eine gerade Anzahlvon Knoten mit einer ungeraden Anzahl von Nachbarn.

I In∑

v∈V |{w | {v ,w} ∈ E}| wird jede Kante zweimal gezählt.I Die Menge U hat eine gerade Anzahl von Elementen.I Lopt ist die Länge einer kürzesten Rundreise,I MSopt ist die Länge eines minimalen Spannbaumes undI Match das Gewicht eines minimalen Matchings auf U.

Es ist MSopt 6 Lopt.

Match 6 12 · Lopt:

I Die Länge einer kürzesten Rundreise auf den Punkten in U isthöchstens Lopt.

I Eine Rundreise auf den gerade vielen Punkten aus U zerlegt sichin zwei perfekte Matchings.

Die Länge der Rundreise ist höchstens MSopt + Match 6 32 · Lopt.


Der Algorithmus von Christofides:Eine Zusammenfassung

Der Algorithmus von Christofides ist ein 32 -approximativer Algorithmus.

Was war die Idee?I Verfolge weiterhin die Spannbaum Heuristik.I Ersetze aber einen Präorderdurchlauf durch eine Eulertour.

F Dazu muss gewährleistet sein, dass jeder Knoten des Spannbaumsgeraden Grad hat.

F Füge ein leichtestes Matching auf den Knoten mit ungeradem Gradzum Spannbaum hinzu.

Das metrische TSP besitzt eine Fülle weiterer Heuristiken.


Nearest Neighbor,Nearest und Farthest Insertion

Heuristiken für TSP Nearest Neighbor 77 / 80

Nearest Neighbor

Wenn Nearest Neighbor den Punkt v erreicht hat, dann wird alsNächster der Punkt w besucht, wobei w unter allen noch nichtbesuchten Knoten eine minimale Distanz zu v hat.

Der Approximationsfaktor von Nearest-Neighbor ist unbeschränkt,aber durch O(log2 n) für n Punkte beschränkt.

Heuristiken für TSP Nearest Neighbor 78 / 80

Nearest und Farthest Insertion

- Nearest Insertion beginnt mit einem Paar nächstliegenderPunkte.

- Wähle einen zur bisher gebauten partiellen Rundreisenächstliegenden Punkt.

- Füge den Punkt so hinzu, dass die Länge der Rundreisegeringstmöglich anwächst.

- Farthest Insertion beginnt mit einem Paar am weitestenvoneinander entfernter Punkte.

- Farthest Insertion verhält sich wie Nearest Insertion, aber- wählt den von der bisher gebauten partiellen Rundreise am

weitesten entfernten Punkt.

Nearest Insertion ist 2-approximativ,der Approximationsfaktor von Farthest Insertion ist unbekannt,aber durch O(log2 n) beschränkt.Heuristiken für TSP Einfüge-Heuristiken 79 / 80

Eine experimentelle Analyse

Bis zu 100.000 Punkte werden zufällig aus dem Quadrat [0,1]2

ausgewählt.

Der Algorithmus von Christofides ist der Gewinner, allerdingsmit geringem Abstand zu Farthest Insertion.Nearest-Insertion wird deutlich geschlagen und endet auf Platzdrei.Der klare Verlierer ist die Spannbaum Heuristik, die bis zu 40%über der optimalen Länge einer Rundreise liegt.Der Christofides Algorithmus und Farthest Insertion sindungefähr 10% über dem Wert einer optimalen Rundreise,während Nearest Insertion um bis zu 25% schwächer ist.

Heuristiken für TSP Einfüge-Heuristiken 80 / 80

Date post:	12-Aug-2019
Category:	Documents
Upload:	lykhue
View:	214 times
Download:	0 times

Greedy- und Priority Algorithmen · Was ist ein Greedy-Algorithmus? (2/2) Wir benötigen den...

Documents