Greedy-Algorithmen und Dynamische Programmierung

From Alda
Jump to: navigation, search

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

Tsm points.JPG

Dabei entsteht folgender Entscheidungsbaum:

Tsm4.JPG

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:

Tsm greedyb.JPG

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

Fib1.JPG

Im Beispiel mit Fibonacci-Zahlen wird Fib(2) gleich dreimal benötigt.


Zur Erinnerung: Die Fibonacci-Folge (f_0, f_1,\ldots) ist durch das rekursive Bildungsgesetz
 f_n = f_{n-1} + f_{n-2}\   für n\geq 2
mit den Anfangswerten
f_0=0\   und   f_1=1\
definiert.

Konzept der Dynamische Programmierung

Jedes Teilproblem soll nur einmal gelöst werden, d.h. einige Knoten werden mehrmals genutzt:

Fib2.JPG

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.

Dijkstra.JPG

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 s_i und Endzeiten f_i.
Es kann immer nur eine Aufgabe gleichzeitig bearbeitet werden: zwei Aktivitäten sind kompatibel, wenn deren Zeiten sich nicht überlappen.
a_k\,\text{komp}\, a_j  \Leftrightarrow  s_k\geq f_j\, \or \, s_j\geq f_k
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

  1. Wähle (unter kompatiblen) die Aktivität, die als erste startet
  2. Wähle (unter kompatiblen) die Aktivität, die als erste endet (oder: die als letzte startet)
  3. Wähle (unter kompatiblen) die Aktivität, die am kürzesten dauert
  4. 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.
    L_1=  |--| |--| |--| |--|
    L_2=|---------------------|
    |L_1|=4 |L_2|=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.
    L_1=|---------| |---------|
    L_2=        |----|
    |L_1|=2 |L_2|=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 U={i_1,...,i_k}.
Eine (unbekannte) optimale Lösung sei O={j_1,...,j_m}.

Ziel

Die Lösung des Ansatzes soll genausoviele Aktivitäten schaffen wie die optimale Lösung (d.h. k=m)

Voraussetzungen

  • Sortiere i_1,...,i_k nach aufsteigender Endzeit f_i
  • Sortiere j_1,...,j_m nach aufsteigender Endzeit f_j

(Da die Aktivitäten kompatibel sind, werden die Anfangszeiten automatisch auch sortiert)

Schritt 1

Für die Indizes p\leq r (inbesondere p=r) gilt: f(i_p)\leq f(j_r)

Beweis durch vollständige Induktion

Induktions-Anfang:
f(i_1)\leq f(j_1), da i_1 die erste Aktivität ist, die überhaupt endet
Induktions-Voraussetzung:
f(i_{r-1})\leq f(j_{r-1})
Induktions-Schritt:
Wegen Kompatibilität gilt:
f(j_{r-1})\leq s(j_r)
=> f(i_{r-1})\leq s(j_r)
=> Die Greedy Strategie kann Aktivität j_r wählen, denn sie ist kompatibel mit i_{r-1}
  • Wenn die Greedy Strategie tatsächlich j_r wählt, folgt daraus:
f(i_r)=f(j_r)
  • Wenn nicht, kann nur gelten:
f(i_r)\leq f(j_r)

Schritt 2

Zu zeigen: k=m

Beweis durch Widerspruchsannahme

  • Falls m<k, wäre die Lösung der Strategie besser als die optimale.
  • Angenommen m>k, dann enthält O eine Aktivität j_{k+1}.
Nach Schritt 1 gilt:
f(i_k)\leq f(j_k)\leq f(j_{k+1})
Wegen Kompatibilität gilt aber:
s(j_{k+1})\geq f(j_k)\geq f(i_k)
-> Die Greedy Strategie hätte also noch die Aktivität j_{k+1} 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 w_i
(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 p(i), welche für die Aktivität steht, die vor a_i endet, mit a_i 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 a_i 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 a_n entweder zur Lösung gehört, oder nicht:

Wis1.JPG

Dadurch ergibt sich folgende Funktion:
OPT(n)=\begin{cases}
\ \;\, \{a_n\}\cup OPT(p(n))\\
\ \;\, OPT(a_{n-1})
\end{cases}
Um den höchstmöglichen Gewinn zu erzielen, wird \{a_n\}\cup OPT(p(n)) verwendet falls gilt:
w_n + Gewinn(OPT(p(n))\leq Gewinn(OPT(n-1))
Ansonsten wird OPT(a_{n-1}) angewandt.

Erinnerung: Intervalle

Bild1.JPG

Sortiere Intervalle nach aufsteigender  f_{i} :

Gewinn (a_{n}) = max (w_{n}) + Gewinn (p(n)), Gewinn  (a_{n-1})
Gewinn  (a_{n-1}) = max (w_{n-1} + Gewinn (p(n-1)), Gewinn  (a_{n-2})
usw.

Bild2.JPG

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

Bild3.JPG

=> arbeite topologische Sortierung von rechts nach links ab.

Beispiel

Wie erklärt man einem zerstreuten Professor, wie er sich morgens anziehen soll?

Bild4.JPG

=> 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.

Bild5.JPG

Zwei Algorithmen zum Finden der topologischen Sortierung

Algorithmus 1

  1. Suche einen Knoten mit Eingangsgrad 0 (ohne eingehende Pfeile), => in einem gerichteten azyklischen Graphen gibt es immer einen solchen Knoten
  2. Platziere diesen Knoten auf der Geraden (beliebig)
  3. Entferne den Knoten aus dem Graphen zusammen mit den ausgehenden Kanten
  4. 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.

Bild6.JPG

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

Bild7.JPG

Fälle:

  1. Matche a[i] mit b[j]. Falls a[i] == b[j], ist das gut. Andernfalls entstehen Kosten K_{a[i], b[j]}
  2. Wir überspringen a[i] oder b[j], => Kosten L
gesucht: Alignment mit minimalen Kosten

Bild8.JPG

Lösung:

Suche kürzesten Pfad von links oben nach rechts unten (z.B. mit dem Algorithmus von Dijkstra)
In unserem Beispiel von oben:

Bild9.JPG

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")

Nächstes Thema