Greedyalgorithmen und -heuristiken
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
<!-- Einführende Beispiele / Rückführung auf Bekanntes: Florian Haje -->
== Beispiele ==
ca 15-20min
---Algorithmen aus vorangegangenen Vorträgen vorstellen und erklären warum das ergebnis ein globales Optimum ist
---evtl weitere übungen um in kleineren graphen zu erkennen ob greedy ein lokales oder globales optimum liefern wird
<ul>
<li>Algorithmus von Kruskal für die Suche nach einem minimalen Spannbaum</li>
<li>Algorithmus von Prim für die Suche nach einem minimalen Spannbaum (das zugrundeliegende Mengensystem – die Menge der Bäume – ist aber kein Unabhängigkeitssystem)</li>
<li>Algorithmus von Dijkstra zur Suche eines kürzesten Weges</li>
<li>Färbungsalgorithmus usw</li>
</ul>
==== Kruskal-Algorithmus ====
Der Mathematiker Joseph Kruskal entwickelte einen Algorithmus zur Suche nach einem minimalen Spannbaum. Durch seine Effizienz arbeitet der Algorithmus in $\mathcal{O}\left( m \log n\right)$, wobei $m$ die Anzahl der Kanten und $n$ die Anzahl der Knoten darstellen. Sollte $m \leq n$ gelten, so arbeitet der Algorithmus in $\mathcal{O}\left( n \log n\right)$, für sehr wenige $m$, d. h. $m \leq \frac{n}{2}\left( n-1\right)$, in $\mathcal{O}\left( n^2 \log n\right)$.
Der Algorithmus lässt sich wie folgt beschreiben:
* Alle Kanten werden in aufsteigender Länge in einer Liste sortiert.
* Die erste Kante bildet mit ihren anschließenden Knoten den Startgraphen. Existeren mehrere Kanten gleicher Länge, werden alle verwendet.
* Solange noch nicht alle Knoten verbunden sind, wird dieses Verfahren wiederholt.
* Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Am Beispiel wird der Algorithmus deutlich. Als Basis dient wieder der bereits weiter oben verwendete Graph.
<gallery widths="400" heights="300" perrow="2">
Bild:S3dafran_S3dafran_dijkstra_1.png|Wir suchen uns die Kanten mit den geringsten Werten. Dies wären $\overline{BC}$, $\overline{DE}$ und $\overline{DG}$. Welche wir wählen, ist egal.
Bild:S3dafran_Kruskal_2.png|Wir wählen die Kante $\overline{BC}$ mit ihren zugehörigen Knoten als Startgraph.
Bild:S3dafran_Kruskal_3.png|Die beiden anderen Favoriten kommen ebenfalls hinzu.
Bild:S3dafran_Kruskal_4.png|Die nun kürzeste Strecke ist die Strecke $\overline{AB}$, die nun an den Graphen "angeschlossen" wird.
Bild:S3dafran_Kruskal_5.png|Mit der Strecke $\overline{BG}$ sind nun fast alle Knoten verbunden.
Bild:S3dafran_Kruskal_6.png|Als letzte noch fehlende Strecke kommt die Strecke $\overline{AF}$ hinzu und vervollständigt den minimalen Spannbaum.
</gallery>
==== Prim-Algorithmus ====
Ein weiterer Algorithmus zur Ermittlung des minimalen Spannbaums wurde 1930 vom Mathematiker Vojtěch Jarník entwickelt, 1957 von Robert Prim und 1959 von Edsger Dijkstra wiederentdeckt. Auf Basis des Dijkstra-Algorithmus arbeitet dieser Algorithmus in $\mathcal{O}\left( n^2\right)$.
Die Funktionsweise des Algorithmus lässt sich wie folgt beschreiben:
* Ein beliebiger Knoten eines Graphen wird gewählt.
* Nun wird die angrenzende Kante mit dem geringsten Wert gewählt und der angrenzende Knoten verbunden.
* Dieses Verfahren wird so lange wiederholt, bis alle Knoten verbunden sind. Es werden nun aber alle Kanten an allen verbundenen Knoten betrachtet.
* Würde durch die Hinzunahme einer Kante ein Kreis entstehen, wird diese Kante aus der Liste gestrichen und mit der nächsten fortgefahren.
Die Erweiterung der Dijkstra-Algorithmus ergibt sich dann wie folgt:
/*
* S: Lösungsmenge
* s: Startknoten
* V: Menge aller Knoten des Graphen
*/
S := {s};
Distanz(s) := 0;
for all $v \in V\backslash \lbrace s\rbrace$ do {
Distanz(v) := Kante(s, v);
Vorgänger(v) := s;
}
while $S \neq V$ do {
Finde $u \in V\backslash S$ mit Distanz(u) = min{Distanz(v) | $v \in V\backslash S$};
S := $S \cup \lbrace u\rbrace$;
for all $v \in V\backslash S$ do {
if Kante(u, v) < Distanz(v)
then {
Distanz(v) := Kante(u, v);
Vorgänger(v) := u;
}
}
}
Auch hier soll wieder ein Beispiel des Algorithmus verdeutlichen.
<gallery widths="400" heights="300" perrow="2">
Bild:S3dafran_S3dafran_dijkstra_1.png|Wir starten wieder mit dem bereits oben verwendeten Graphen und suchen einen Startknoten.
Bild:S3dafran_Prim_2.png|In diesem Beispiel wählen wir den Knoten ''A'' als Startknoten und betrachten die an ''A'' angrenzenden Kanten.
Bild:S3dafran_Prim_3.png|Die Strecke $\overline{AB}$ ist die kürzeste und folglich wird ''B'' in den Graphen eingebunden. Zur Menge der nun in Frage kommenden Strecken kommen die an ''B'' angrenzenden Strecken hinzu.
Bild:S3dafran_Prim_4.png|Aus der Menge der an ''A'' oder ''B'' angrenzenden (noch nicht verwendeten) Kanten ist die Strecke $\overline{BC}$ am kürzesten und wird hinzugefügt. Ebenso sind nun die an ''C'' angrenzenden Kanten zu mit betrachten.
Bild:S3dafran_Prim_5.png|Die nun kürzeste Strecke ist die Strecke $\overline{BG}$ und folglich wird ''G'' hinzugefügt.
Bild:S3dafran_Prim_6.png|Die nächste kürzeste angrenzende Strecke ist $\overline{GD}$ und wird hinzugefügt.
Bild:S3dafran_Prim_7.png|Fast vollständig ist der Spannbaum, wenn die jetzt kürzeste Strecke $\overline{DE}$ hinzugefügt wird.
Bild:S3dafran_Prim_8.png|Als letzte noch fehlende Strecke kommt die Strecke $\overline{AF}$ hinzu und vervollständigt den minimalen Spannbaum.
</gallery>
<!-- Theoretische Grundlagen: Erik Bothe -->
== Greedy-Verfahren ==
=== Grundlegender Gedanke ===
Ein Verfahren, welches sich "Greedy" nennt, bearbeitet schrittweise ein Problem, indem es eine Teillösung ermittelt und diese kontinuierlich erweitert. Bei der Erweiterung der Teillösung wird typischerweise immer der am naheliegendste oder günstigste mögliche "Happen" gewählt, der noch nicht Bestandteil der Teillösung ist. Das Verfahren endet, wenn kein weiterer "Happen" vorhanden ist, um die Teillösung zu erweitern. Dann wird aus der Teillösung die Gesamtlösung.
=== Greedy-Heuristiken ===
;Heuristik
:Eine Heuristik (altgriech. εὑρίσκω, heurísko: "ich finde") ist ein analytisches Verfahren, bei dem Aussagen über ein System getroffen werden, die ausschließlich auf Vermutungen basieren.
<br>
<i>Wie würde eine Greedy-Heuristik in der Graphentheorie aussehen?</i>
Eine Greedy-Heuristik wäre ein simpler Ablaufplan, mit dem ein Problem in einem Graph schrittweise abgearbeitet wird. Dabei wird, wie charakteristisch für die Heuristik, immer eine Vermutung zugrunde gelegt, bei der davon ausgegangen wird, dass sie zur bestmöglichen Lösung führt.
# Ein beliebig gewählter Startpunkt (-knoten, -kante) wird der zunächst leeren Teillösung hinzugefügt.
# Von dort aus wird der nächste Problemteil (Knoten, Kante) gesucht, der am günstigsten erscheint <b>und</b> zur Teillösung hinzugefügt werden darf. -> Daraus folgt: heuristische Vermutung = günstigster "Happen" führt zur besten Lösung.
# Der neu hinzugefügte Problemteil ist der Ausgangspunkt, um Schritt 2 zu wiederholen, es sei denn, es kann kein Problemteil mehr der Teillösung hinzugefügt werden. In letzterem Fall endet die Heuristik, die gefundene Teillösung ist eine gültige Lösung für das zugrunde liegende Problem.
Welcher "Happen" der günstigste ist, ist vom zugrundeliegenden Problem und dem verwendeten Graphen abhängig.
<b>Beispiele:</b>
* In einem Graphen mit bewerteten Elementen wird die kleinste/größte Bewertung gewählt, je nachdem, was vom Problem verlangt wird.
* In unbewerteten Graphen ist das nächste Element zufällig wählbar.
* In gerichteten Graphen können (bei Knotenproblemen) nur Knoten gewählt werden, die auch erreichbar sind.
=== Greedy-Algorithmen ===
Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie schrittweise und ohne zurückzusetzen, eine Lösung aufbauen indem sie
anhand lokaler Informationen den Folgezustand auswählen, welcher zum Zeitpunkt der Wahl das beste Ergebnis verspricht.
Es werden dabei nicht mehr Teillösungen konstruiert als unbedingt nötig.
Die Basis eines Greedy-Algorithmus ist eine bereits (absteigend) vorsortierte Liste. Wird diese erweitert, werden die entsprechenden Elemente direkt an die richtige Stelle einsortiert.
#*'''Vorteil:''' meist schnell, liefert zumindest gute Lösungen
#*'''Nachteil:''' keine Berücksichtigung früherer Lösungen, keine Revision einmal getroffener Entscheidungen, selten optimale Lösungen
==== Aufbau ====
Im Allgemeinen besteht ein Greedy-Algorithmus aus folgenden Bestandteilen:
# eine sich verbrauchende <b>Kandidatenliste</b>
# eine sich aufbauende <b>Resultatliste</b>
#<b>Kontrollstrukturen</b>
#*<i>istLösung()</i>, die kontrolliert, ob die aktuelle Resultatliste eine Lösung des Problems darstellt
#*<i>okay()</i>, die kontrolliert, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
#*<i>ziel</i>, die den Wert einer Lösung angibt
#<b>Auswahlfunktion</b>
#* <i>nächster()</i>, die aus der Kandidatenliste den jeweils besten "Happen" auswählt
#<b>Modifikationsfunktionen</b>
#* <i>modify+</i>, die die Kandidatenliste im positiven Fall, also wenn die Erweiterung zu einer zulässigen Liste führt, modifiziert
#* <i>modify-</i>, die die Kandidatenliste im negativen Fall, also wenn die Erweiterung nicht zu einer zulässigen Liste führen würde, modifiziert
<code id="56905c4837a7e">
(define greedy
(lambda (vorgabewert) ; z.B.: Kapazitaet der Rucksacks
(let
((kandidatenliste '(......))
(loesung? (lambda (ls) ... ))
(okay? (lambda (ls) ... ))
(naechster (lambda (ls) ... ))
(modify+ (lambda (x ls) ... ))
(modify- (lambda (x ls) ... ))
(ziel (lambda (ls) ... ))
(letrec
((helfer
(lambda (kandidaten resultat)
(cond
((loesung? resultat)(ziel resultat))
((and (null? kandidaten)(not (loesung? resultat)))
(error 'greedy "Es gibt keine Loesung."))
(else
(let* ((neuer-kandidat (naechster kandidaten))
(neues-resultat (cons neuer-kandidat resultat)))
(if (okay? neues-resultat)
(helfer (modify+ neuer-kandidat kandidaten) neues-resultat)
(helfer (modify- neuer-kandidat kandidaten) resultat))))))))
(helfer kandidatenliste '())))))
</code>
===Anwendungsbeispiel===
<!-- Matroide: Maik Geier -->
= Matroide, die Theorie der Unabhängigkeitsysteme =
<ul>
<li>'''Motivation:''' Ein Greedy-Algorithmus findet für ein Optimierungsproblem auf '''''Unabhängigkeitssystemen''''' genau dann die optimale Lösung, wenn die zulässigen Lösungen die unabhängigen Mengen eines '''''Matroids''''' sind.
Sonst führt der Algorithmus lediglich zu einem lokalen Optimum. Ein Unabhängigskeitssystem ist umgekehrt genau dann ein Matroid, wenn ein Greedy-Algorithmus zu jeder Gewichtsfunktion immer Basen mit minimalen/maximalen Gewicht berechnen kann.</li><br>
<li>'''Herkunft:''' Der Begriff Matroid entstammt der Untersuchung der Unabhängigkeit der Spaltenvektoren einer Matrix. Er ist eine Verschmelzung der Wörter "Matrix" und "Oides"(griech. ~ Ähnlichkeit).</li>
Ein Unabhängigkeitssystem ist in der Kombinatorik eine '''Verallgemeinerung der mathematische Struktur des Matroides'''.
<div style= "background-color:#D6D6C2; padding:10px">
== '''Definition: Unabhängigkeitssystem''' ==
Sei $E$ eine beliebige endliche Grundmenge und $\mathcal I$ ein System von Teilmengen von $E$ (also $\mathcal I\subseteq \mathcal{P} (E)$ ), dann ist das Paar $(E,\mathcal{I})$ ein Unabhängigkeitssystem, wenn die folgenden Bedingungen erfüllt sind:
# $\emptyset \in \mathcal{I}$ (Nicht zu verwechseln mit $\emptyset \subseteq \mathcal{I}$, was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
# $A \subseteq B, B\in \mathcal{I} \Rightarrow A\in \mathcal{I}$ ($\mathcal{I}$ ist nach unten $\subseteq$-abgeschlossen.)
1. ist äquivalent zu der Forderung dass $\mathcal{I}$ nicht leer ist.<br>
<ul>
<li>'''Lineare Unabhängigkeit'''<br>
In der linearen Algebra wird eine Familie von Vektoren eines Vektorraums linear unabhängig genannt, wenn sich der Nullvektor nur durch eine Linearkombination der Vektoren erzeugen lässt, in der alle Koeffizienten der Kombination auf den Wert null gesetzt werden. Äquivalent dazu ist, dass sich keiner der Vektoren als Linearkombination der anderen darstellen lässt.</li><br>
<li>'''Unabhängigkeit für Bipartites Matching'''<br>
Die Elemente einer Menge in einem Matchingsystem sind Unabhängig wenn diese gleichzeitig gematcht werden können.</li><br>
<li>'''Unabhängigkeit von Gleichungen'''<br>
Eine Menge von Gleichungen ist unabhängig wenn sich aus der Kombination dieser kein Ergebnis herleiten lässt.</li><br>
<li>'''Unabhängigkeit von gerichteten Kanten'''<br>
???</li><br>
</ul>
</div>
<br>
Durch Hinzufügen der sogenannten ''Austauscheigenschaft'' entsteht aus einem Unabhängigkeitssystem ein ''Matroid''.
<div style= "background-color:#D6D6C2; padding:10px">
== '''Definition: Matroid''' ==
Sei $E$ eine endliche Menge und $\mathcal I$ eine Teilmenge von $\mathcal P(E)$. Ein Matroid ist ein Paar $(E;\mathcal I)$ für welches folgende Bedingungen erfüllt sind:
:1. $\emptyset \in \mathcal I$
:2. $\forall A \in \mathcal I\, \forall B \in \mathcal P(E) \colon B \subseteq A \Rightarrow B \in \mathcal I$
:3. $\forall A; B \in \mathcal I \colon \left| B \right| < \left| A\right| \Rightarrow (\exists x \in A \setminus B \colon B \cup \{x\} \in \mathcal I)$
Dabei ist $\left| A \right|$ die ''Kardinalität'' der Menge $A$.
Die Elemente von $E$ bilden die Grundmenge. Die Elemente von $\mathcal I$ bilden die unabhängigen Teilmengen, auch ''Set´s'' genannt, aus $E$.
</div><br>
<div style= "background-color:#D6D6C2; padding:10px">
=== Definition: Basis ===
Als Basis wird eine unabhängige Menge bezeichnet, welche in ihrer Kardinalität nicht weiter vergrößert werden kann.
<ul>
<li>Für endlichdimensionale Vektorräume entspricht die Kardinalität der Basen der Anzahl der Dimensionen.</li>
<li>Für Gleichungen entspricht die Kardinalität der Basen der Anzahl der unbekannten Variablen</li>
<!--
<li>Für entspricht </li>
<li>Für entspricht </li>
-->
</ul>
</div>
<br>
== Beispiele ==
<table border="4" width="100%">
<tr>
<td width="40%"><center>'''Aufgaben/Beispiele'''</center></td>
<td width="15%"><center>'''Matrix'''</center></td>
<td width="20%"><center>'''Fragen'''</center></td>
<td width="20%"><center>'''Antworten'''</center></td>
</tr>
<tr>
<td height="250">Bilde die Menge der unabhägigen Vektoren! [[Bild:Basch_Vektorbsp.JPG]]
</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1/2 & 1 & 0 \\
0 & 0 & 1 & 1/2 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welcher Vektor ist nicht wie die anderen?</li><br>
<li>Welcher andere Vektor ist nicht wie die anderen?</li><br>
<li>Welches Vektorenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, immer wählbar ohne Abhängige Sets zu erzeugen</li><br>
<li>F, da 0-Vektor, kein "Ortswechsel" mit ihm möglich</li><br>
<li>DE, zeigen in die selbe Richtung / erfüllen den selben Zweck</li><br>
</ul></td>
</tr>
<tr>
<td height="250">Welche Kantenzüge sind unabhängig? [[Bild:Basch_Ungraphbsp.JPG]]
</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welche Kante ist nicht wie die anderen?</li><br>
<li>Welche andere Kante ist nicht wie die anderen?</li><br>
<li>Welches Kantenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, da ohne ihn der Graph in 2 Teile zerfällt</li><br>
<li>F, da kein "Ortswechsel" mit ihm möglich</li><br>
<li>DE, haben die selbe Funktion(Zwillinge)</li><br>
</ul></td>
</tr>
<tr>
<td height="250">Bilde die Menge aller möglichen Matchings! [[Bild:Basch_Matchingbsp.JPG]]
</td>
<td><center><math>
\left(
\begin{array}{cccccc}
1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 0 \\
\end{array}
\right)
</math></center></td>
<td><ul>
<li>Welcher Knoten ist nicht wie die anderen?</li><br>
<li>Welcher andere Knoten ist nicht wie die anderen?</li><br>
<li>Welches Knotenpaar ist nicht wie die anderen?</li><br>
</ul></td>
<td><ul>
<li>A, da er immer Wählbar ist</li><br><br>
<li>F, da er niemals Wählbar ist</li><br><br>
<li>DE, sind niemals gleichzeitig Wählbar</li><br>
</ul></td>
</tr>
</table>
<table border="4" width="100%">
<tr>
<td width="55%"><center>'''Ergebnis'''</center></td>
<td width="20%"><center>'''Frage'''</center></td>
<td width="20%"><center>'''Antwort'''</center></td>
</tr>
<tr>
<td><center>
<ul>
<li>${leere Menge}$</li>
<li>${a,b,c,d,e}$</li>
<li>${ab,ac,ad,ae,bc.bd,be,cd,ce}$</li>
<li>${abc,ace,abe,abd,acd}$</li>
<li> $->$ letzteres = Basen = unabhängige Mengen welche in ihrer Kardinalität nicht weiter wachsen können</li>
</ul></center></td>
<td><center>
<ul>
<li> Handelt es sich bei der Ergebnismenge um ein Matroid?</li>
</ul></center></td>
<td><center>
<ul>
<li> Ja. Es gibt zb. für jede Menge mit einer Kardinalität von 2 mindestens ein Element aus den Mengen mit einer Kardinalität von 3 welches noch hinzugefügt werden kann, sodass die Unabhängigkeit weiterhin besteht</li>
</ul></center></td>
</tr>
</table>
<!--
Evtl weglassen oder als zusatzaufgabe.
Aufgabe/Beispiel: Gleichungen
<ul>
<li>$a=z^3$</li>
<li>$b=x+y$</li>
<li>$c=x-y$</li>
<li>$d=xy$</li>
<li>$e=x^2y^2$</li>
<li>$f=1$</li>
</ul>
-->
== Anwendbarkeit ==
Nun wissen wir zwar wie wir das Ergebnis eines Greedy-Algorithmus bewerten können - allerdings ist der Aufwand, welcher bei der Überprüfung der gegebenen Datenstruktur auf Unabhängigkeit/Matroide entsteht, exponentiell und gehört somit in die Komplexitätsklasse der NP-schweren Probleme!
<br>