Greedy-Algorithmen und Dynamische Programmierung: Difference between revisions
(4 intermediate revisions by 3 users not shown) | |||
Line 42: | Line 42: | ||
== Dynamische Programmierung == | == Dynamische Programmierung == | ||
(''Programmierung'' | (''Programmierung'' bezieht sich hier nicht auf spezielle Programmiersprachen, sondern meint vielmehr die Optimierung des Programmablaufs) | ||
:Oft ist dasselbe Teilproblem in mehreren Pfaden vorhanden. | :Oft ist dasselbe Teilproblem in mehreren Pfaden vorhanden. | ||
Line 156: | Line 156: | ||
::Wegen Kompatibilität gilt: | ::Wegen Kompatibilität gilt: | ||
::<math>f(j_{r-1})\leq s(j_r)</math> | ::<math>f(j_{r-1})\leq s(j_r)</math> | ||
::=> <math>f(i_{r-1})\leq s( | ::=> <math>f(i_{r-1})\leq s(j_r)</math> | ||
::=> Die Greedy Strategie ''kann'' Aktivität <math>j_r</math> wählen, denn sie ist kompatibel mit <math>i_{r-1}</math> | ::=> Die Greedy Strategie ''kann'' Aktivität <math>j_r</math> wählen, denn sie ist kompatibel mit <math>i_{r-1}</math> | ||
::* Wenn die Greedy Strategie tatsächlich <math>j_r</math> wählt, folgt daraus: | ::* Wenn die Greedy Strategie tatsächlich <math>j_r</math> wählt, folgt daraus: | ||
Line 179: | Line 179: | ||
:-> m=k ist richtig | :-> m=k ist richtig | ||
=== Beispiel zur Dynamischen Programmierung: | === Beispiel zur Dynamischen Programmierung: Weighted Intervall Scheduling === | ||
:Die Problemstellung ähnelt dem des normalen Intervall Scheduling, hier haben die Aktivitäten aber Gewichte <math>w_i</math> | :Die Problemstellung ähnelt dem des normalen Intervall Scheduling, hier haben die Aktivitäten aber Gewichte <math>w_i</math> | ||
:(z.B. Bringt eine längere Aufgabe in einem Übunsgzettel in der Regel auch mehr Punkte, d.h. sie hat eine hohe Gewichtung) | :(z.B. Bringt eine längere Aufgabe in einem Übunsgzettel in der Regel auch mehr Punkte, d.h. sie hat eine hohe Gewichtung) | ||
Line 209: | Line 209: | ||
:Ansonsten wird <math>OPT(a_{n-1})</math> angewandt. | :Ansonsten wird <math>OPT(a_{n-1})</math> angewandt. | ||
== Erinnerung: Intervalle == | == Erinnerung: Intervalle == | ||
Line 290: | Line 289: | ||
=> effizient | => effizient | ||
* bei vielen Problemen ist keine Möglichkeit bekannt, das vollständige Durchlaufen des Entscheidungsbaumes zu vermeiden, z.B. [[Problem des Handlungsreisenden]] (TSP), 3-SAT | * bei vielen Problemen ist keine Möglichkeit bekannt, das vollständige Durchlaufen des Entscheidungsbaumes zu vermeiden, z.B. [[Graphen_und_Graphenalgorithmen#Problem_des_Handlungsreisenden | Problem des Handlungsreisenden]] (TSP), 3-SAT | ||
* Frage: Gibt es prinzipiell keinen effizienten Algorithmus, oder sind wir nur zu blöd? | * Frage: Gibt es prinzipiell keinen effizienten Algorithmus, oder sind wir nur zu blöd? | ||
* Derzeitiger Stand: viele dieser Probleme sind fundamental äquivalent „NP complete problems“ – „NP vollständig“ (NP = "nicht-deterministisch polynomiell") | * Derzeitiger Stand: viele dieser Probleme sind fundamental äquivalent „NP complete problems“ – „NP vollständig“ (NP = "nicht-deterministisch polynomiell") | ||
[[NP-Vollständigkeit|Nächstes Thema]] |
Latest revision as of 10:53, 20 August 2009
Einführung
- Viele Probleme sind durch einen Entscheidungsbaum systematisch lösbar.
- Dabei wird die zu suchende Lösung auf den optimalen Weg durch den Entscheidungsbaum reduziert.
Beispiel
- Erklärung des Algorithmus ist zu finden in Graphen und Graphenalgorithmen
- Traveling Salesman Problem mit 4 Knoten
- Dabei entsteht folgender Entscheidungsbaum:
- Vorteil des Entscheidungsbaums: Lösungsmöglichkeiten werden nicht übersehen
- Nachteil: Eventuell muss der gesamte Baum durchsucht werden (exponentielle Komplexität)
- Um diesen Nachteil auszugleichen gibt es verschiedene Verfahren:
- Divide & Conquer (Problem auf triviale Teilprobleme zurückführen, welche jeweils einfach zu lösen sind)
- Greedy Algorithmen
- Dynamische Programmierung
Greedy Algorithmen
- Greedy (dt. "Gierig") Algorithmen entscheiden an jedem Knoten lokal über die beste Fortsetzung der Suche,
- d.h. es wird jeweils die beste Entscheidung im Kleinen getroffen - ohne Rücksicht auf Konsequenzen für den gesamten Suchverlauf.
Beispiele
Anwendung beim Traveling Salesman Problem
- Erklärung des Algorithmus ist zu finden in Graphen und Graphenalgorithmen
- Reise immer zum nächstgelegenen, noch nicht besuchten Knoten:
- In diesem Beispiel wurde eine optimale Lösung gefunden. Dies muss im Allgemeinen aber nicht immer der Fall sein!
Anwendung beim Algorithmus von Kruskal für Minium Spanning Tree
- Erklärung des Algorithmus ist zu finden in Graphen und Graphenalgorithmen
- Sortiere die Kanten nach Gewicht
- Wähle stets die Kante mit niedrigstem Gewicht (d.h. im Allgemeinen die nächsgelegene), die keinen Zyklus verursacht
- Hierbei wird der Minimum Spanning Tree stets gefunden.
Dynamische Programmierung
(Programmierung bezieht sich hier nicht auf spezielle Programmiersprachen, sondern meint vielmehr die Optimierung des Programmablaufs)
- Oft ist dasselbe Teilproblem in mehreren Pfaden vorhanden.
Beispiel
- Im Beispiel mit Fibonacci-Zahlen wird Fib(2) gleich dreimal benötigt.
- Zur Erinnerung: Die Fibonacci-Folge <math>(f_0, f_1,\ldots)</math> ist durch das rekursive Bildungsgesetz
- <math> f_n = f_{n-1} + f_{n-2}\ </math> für <math>n\geq 2</math>
- mit den Anfangswerten
- <math>f_0=0\ </math> und <math>f_1=1\ </math>
- definiert.
Konzept der Dynamische Programmierung
- Jedes Teilproblem soll nur einmal gelöst werden, d.h. einige Knoten werden mehrmals genutzt:
- Wie im Beispiel erkennbar, hat sich die Zahl der Knoten drastisch reduziert (von 9 auf 5).
- Allerdings müssen die Graphen jetzt gerichtet sein.
- Wenn der neue Graph azyklisch ist, kann man die Teilprobleme so anordnen, dass jedes
- nur einmal gelöst wird
- nur von bereits gelösten Teilproblemen abhängt
- Wenn der Graph nicht azyklisch ist (weil z.B. Teilproblem A die Lösung von Teilproblem B erfordert und umgekehrt),
- ist die Dynamische Programmierung auf dieses Problem nicht anwendbar.
Dynamisch programmierter Dijkstra Alrogithmus
- Erklärung des Algorithmus ist zu finden in Graphen und Graphenalgorithmen
- Löse Teilprobleme entsprechend ihrer Priorität, d.h. Priorität definiert die Ordnung
- Problem: Der Suchbaum ist bei diesem Algorithmus ungerichtet
- Lösung: Die Richtung der Kanten wird festgelegt, wenn man die Nachbarn eines Knotens in die Queue eingefügt
- Wenn man den Abstand vom Start bestimmt (Teilproblem), ist der Abstand von allen näher gelegenen bereits bekannt.
Greedy oder Dynamische Programmierung?
- Für viele Probleme gibt es unterschiedliche Entscheidungsräume und/oder unterschiedliche Entscheidungskriterien.
- Ein und dasselbe Problem kann also mit einer der Darstellungen (Greedy, Dynamische Programmierung, weitere...) effizient lösbar sein, mit anderen eventuell nicht.
- Das finden einer geeigneten Darstellung ist also eine zentrale Herausforderung.
Anwendungsbeispiel: Interval Scheduling
- gegeben:
- Mehrere Aufgaben mit unterschiedlichen Anfangszeiten <math>s_i</math> und Endzeiten <math>f_i</math>.
- Es kann immer nur eine Aufgabe gleichzeitig bearbeitet werden: zwei Aktivitäten sind kompatibel, wenn deren Zeiten sich nicht überlappen.
- <math>a_k\,\text{komp}\, a_j \Leftrightarrow s_k\geq f_j\, \or \, s_j\geq f_k</math>
- gesucht:
- Arbeitsplan um möglichst viele Aufgaben nacheinander abzuarbeiten.
- Dabei haben alle Aufgaben dieselbe Priorität, obwohl die Dauer oft unterschiedlich ist.
Mögliche Lösungsansätze für einen Greedy Algorithmus
- Wähle (unter kompatiblen) die Aktivität, die als erste startet
- Wähle (unter kompatiblen) die Aktivität, die als erste endet (oder: die als letzte startet)
- Wähle (unter kompatiblen) die Aktivität, die am kürzesten dauert
- Wähle (unter kompatiblen) die Aktivität, die die wenigsten Inkompatibilitäten (überlappungen mit anderen Aktivitäten) hat
Ungünstige Ansätze:
- In den folgenden Beispielen werden die Aktivitäten mit | als Anfangs- bzw Endzeit markiert, --- steht für den Verlauf einer Aktivität.
- Weiter rechts bedeutet später in der Zeit.
- Gegenbeispiel zu 1.
<math>L_1=</math> |--| |--| |--| |--| <math>L_2=</math>|---------------------| <math>|L_1|</math>=4 <math>|L_2|</math>=1
- Der Ansatz würde Lösung 2 wählen, da die lange Aktivität am frühesten beginnt. Es wird dann nur 1 statt der optimalen 4 abgearbeitet.
- Gegenbeispiel zu 3.
<math>L_1=</math>|---------| |---------| <math>L_2=</math> |----| <math>|L_1|</math>=2 <math>|L_2|</math>=1
- Der Ansatz würde Lösung 2 wählen, da die mittlere Aktivität am kürzesten dauert. Es wird dann nur 1 statt der optimalen 2 abgearbeitet.
- Gegenbeispiel zu 4. (Anzahl der Inkompatibilitäten stehen jeweils in der Mitte der Aktivität)
|-3-| |-4-| |-4-| |-3-| |-4-| |-2-| |-4-| |-4-| |-4-| |-4-| |-4-|
- Der Ansatz würde erst die mit 2, dann die beiden mit 3 Inkompatibilitäten wählen. Es werden dann nur 3 statt der optimalen 4 (obere Zeile) abgearbeitet.
Es verbleibt der 2. Ansatz, dessen Optimalität noch zu beweisen ist...
Greedy Stays Ahead
Idee der Beweismethode
Es genügt zu zeigen:
- die Greedy-Lösung ist nicht schlechter als die optimale Lösung
Beweis der Optimalität des 2. Ansatzes mit Greedy Stays Ahead
Ansatz
- Wähle (unter kompatiblen) die Aktivität, die als erste endet (oder: die als letzte startet)
- Die Wahl dieses Ansatzes sei <math>U={i_1,...,i_k}</math>.
- Eine (unbekannte) optimale Lösung sei <math>O={j_1,...,j_m}</math>.
Ziel
- Die Lösung des Ansatzes soll genausoviele Aktivitäten schaffen wie die optimale Lösung (d.h. k=m)
Voraussetzungen
- Sortiere <math>i_1,...,i_k</math> nach aufsteigender Endzeit <math>f_i</math>
- Sortiere <math>j_1,...,j_m</math> nach aufsteigender Endzeit <math>f_j</math>
(Da die Aktivitäten kompatibel sind, werden die Anfangszeiten automatisch auch sortiert)
Schritt 1
- Für die Indizes <math>p\leq r</math> (inbesondere <math>p=r</math>) gilt: <math>f(i_p)\leq f(j_r)</math>
Beweis durch vollständige Induktion
- Induktions-Anfang:
- <math>f(i_1)\leq f(j_1)</math>, da <math>i_1</math> die erste Aktivität ist, die überhaupt endet
- Induktions-Voraussetzung:
- <math>f(i_{r-1})\leq f(j_{r-1})</math>
- Induktions-Schritt:
- Wegen Kompatibilität gilt:
- <math>f(j_{r-1})\leq s(j_r)</math>
- => <math>f(i_{r-1})\leq s(j_r)</math>
- => Die Greedy Strategie kann Aktivität <math>j_r</math> wählen, denn sie ist kompatibel mit <math>i_{r-1}</math>
- Wenn die Greedy Strategie tatsächlich <math>j_r</math> wählt, folgt daraus:
- <math>f(i_r)=f(j_r)</math>
- Wenn nicht, kann nur gelten:
- <math>f(i_r)\leq f(j_r)</math>
Schritt 2
- Zu zeigen: <math>k=m</math>
Beweis durch Widerspruchsannahme
- Falls <math>m<k</math>, wäre die Lösung der Strategie besser als die optimale.
- Angenommen <math>m>k</math>, dann enthält <math>O</math> eine Aktivität <math>j_{k+1}</math>.
- Nach Schritt 1 gilt:
- <math>f(i_k)\leq f(j_k)\leq f(j_{k+1})</math>
- Wegen Kompatibilität gilt aber:
- <math>s(j_{k+1})\geq f(j_k)\geq f(i_k)</math>
- -> Die Greedy Strategie hätte also noch die Aktivität <math>j_{k+1}</math> wählen können.
- -> Widerspruch zur Annahme, dass die Greedy Strategie durchgelaufen ist, bis keine Aktivität mehr hinzugefügt werden kann
- -> m>k ist falsch
- -> m=k ist richtig
Beispiel zur Dynamischen Programmierung: Weighted Intervall Scheduling
- Die Problemstellung ähnelt dem des normalen Intervall Scheduling, hier haben die Aktivitäten aber Gewichte <math>w_i</math>
- (z.B. Bringt eine längere Aufgabe in einem Übunsgzettel in der Regel auch mehr Punkte, d.h. sie hat eine hohe Gewichtung)
Ziel
- Wähle die Aktivitäten so, dass der Gewinn (Summe der Gewichtungen der bearbeiteten Aktivitäten) maximal wird.
Ansatz
- Sortiere Aktivitäten nach ihrer Endzeit.
- Definiere eine Funktion <math>p(i)</math>, welche für die Aktivität steht, die vor <math>a_i</math> endet, mit <math>a_i</math> kompatibel ist, unter allen Aktivitäten mit diesen Eigenschaften die letzte (d.h. mit der spätesten Endzeit) ist.
In folgendem Beispiel wird die Aktivität <math>a_i</math> mit der Symbolik |-!-| betrachtet um deren p-Funktion zu evaluieren.
Für die p-Funktion kommen lediglich die Funktionen mit der Symbolik |===| und |====| in Frage, die untere der beiden ist die gesuchte Aktivität.
|====| |-!-| |--| |===| |-----| |----|
- Trivial ist, dass <math>a_n</math> entweder zur Lösung gehört, oder nicht:
- Dadurch ergibt sich folgende Funktion:
- <math>OPT(n)=\begin{cases}
\ \;\, \{a_n\}\cup OPT(p(n))\\ \ \;\, OPT(a_{n-1}) \end{cases} </math>
- Um den höchstmöglichen Gewinn zu erzielen, wird <math>\{a_n\}\cup OPT(p(n))</math> verwendet falls gilt:
- <math>w_n + Gewinn(OPT(p(n))\leq Gewinn(OPT(n-1))</math>
- Ansonsten wird <math>OPT(a_{n-1})</math> angewandt.
Erinnerung: Intervalle
Sortiere Intervalle nach aufsteigender <math> f_{i} </math>:
- Gewinn <math>(a_{n})</math> = max <math>(w_{n})</math> + Gewinn (p(n)), Gewinn <math> (a_{n-1})</math>
- Gewinn <math> (a_{n-1})</math> = max (<math>w_{n-1}</math> + Gewinn <math>(p(n-1)</math>), Gewinn <math> (a_{n-2})</math>
- usw.
Bearbeite Teilprobleme in Reihenfolge der Sortierung
- => azyklischer Graph
- (a2 hängt von a1 ab, a3 von a2, a4 von a2 und a3 usw.)
Wie erkennt man, ob der Graph azyklisch ist, und wie fndet man die Reihenfolge?
- azyklischer, gerichteter Graph: „directed acyclic graph“ – DAG
- Ein Graph ist genau dann ein DAG, wenn es eine topologische Sortierung der Knoten gibt.
- Def.: Zeichne die Knoten so auf eine Gerade, dass alle Kanten nach rechts/in dieselbe Richtung zeigen
- => arbeite topologische Sortierung von rechts nach links ab.
Beispiel
Wie erklärt man einem zerstreuten Professor, wie er sich morgens anziehen soll?
- => Die topologische Sortierung ist hier nicht eindeutig, z.B. ist nicht klar, ob zuerst die Strümpfe angezogen werden sollen oder die Unterhose. Wann die Uhr angelegt werden soll, ist überhaupt nicht festgelegt. Mit dieser Beschreibung käme der arme Professor wohl kaum zurecht.
Zwei Algorithmen zum Finden der topologischen Sortierung
Algorithmus 1
- Suche einen Knoten mit Eingangsgrad 0 (ohne eingehende Pfeile), => in einem gerichteten azyklischen Graphen gibt es immer einen solchen Knoten
- Platziere diesen Knoten auf der Geraden (beliebig)
- Entferne den Knoten aus dem Graphen zusammen mit den ausgehenden Kanten
- Gehe zu 1., aber platziere in 2. immer rechts der vorhandenen Knoten (also der Knoten, die schon auf der Geraden vorhanden sind)
- => Wenn noch Knoten übrig sind, aber keiner Eingangsgrad 0 hat, muss der Graph zyklisch sein.
Bild: Ein zyklischer Graph
Algorithmus 2
Verwende Tiefensuche, um die Finishing Time zu bestimmen
- => zeichne Knoten nach abnehmender Finishing Time auf die Gerade
Anwendung: Sequence Alignment / Edit Distance
- gegeben: zwei Wörter (allgemein: beliebige Zeichenfolgen)
- gesucht: Wie kann man die Buchstaben am besten in Übereinstimmung bringen?
- Beispiel: worte – norden
Fälle:
- Matche a[i] mit b[j]. Falls a[i] == b[j], ist das gut. Andernfalls entstehen Kosten <math>K_{a[i], b[j]}</math>
- Wir überspringen a[i] oder b[j], => Kosten L
- gesucht: Alignment mit minimalen Kosten
Lösung:
- Suche kürzesten Pfad von links oben nach rechts unten (z.B. mit dem Algorithmus von Dijkstra)
- In unserem Beispiel von oben:
Problemlösung durch einen Entscheidungsbaum
Greedy Algorithm und dynamische Programmierung: Transformationen des Problems, sodass nicht der ganze Entscheidungsbaum durchlaufen werden muss. => effizient
- bei vielen Problemen ist keine Möglichkeit bekannt, das vollständige Durchlaufen des Entscheidungsbaumes zu vermeiden, z.B. Problem des Handlungsreisenden (TSP), 3-SAT
- Frage: Gibt es prinzipiell keinen effizienten Algorithmus, oder sind wir nur zu blöd?
- Derzeitiger Stand: viele dieser Probleme sind fundamental äquivalent „NP complete problems“ – „NP vollständig“ (NP = "nicht-deterministisch polynomiell")