Greedyalgorithmen und -heuristiken

Wiki-Quelltext dieser Seite.

<h3>09.01.16 - hab mal versucht nen roten faden für die aufteilung zu finden - es muss alles noch bearbeitet werden - müssen die nächsten tage mal wegen der Vortragsaufteilung/Gliederung sprechen - evtl habt ihr ja noch ideen was noch rein kann/muss - ich würde gern den abschnitt matroide/unabhängigkeitssysteme machen</h3>

<h1><font color="green">Greedy-Algorithmen</font color></h1>
ca 15min-20min
---was sind greedy algorithmen?
---Wie ist der allgemeine Aufbau?
---Template zeigen und auf Bsp anwenden
---evtl Beispiele für extremfälle vorstellen-globales optimum, lokales optimum, fall in dem der greedy algorithmus versagt

Greedy-Algorithmen oder auch 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.

Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal.

<h2><font color="green">Aufbau</font color></h2>
Im Allgemeinen besteht ein Greedy-Algorithmus aus folgenden Bestandteilen:
<ul>
<li>eine sich verbrauchende Kandidatenliste,</li>
<li>eine sich aufbauende Resultatenliste</li>
<li>eine Funktion Loesung?, welche überprüft,ob die aktuelle Resultatenliste eine (nicht unbediingt optimale) Lösung des Problems darstellt</li>
<li>eine Funktion OK?, welche überprüft, ob die Erweiterung einer Resultatenliste durch den nächsten Kandidaten zulässig ist.</li>
<li>eine Auswahlfunktion NEXT, die aus der Kandidatenliste den jeweils besten "Happen" auswählt.</li>
<li>eine Modifikationsfunktion MOD+, die die KAndidatenliste im positiven Fall, also wenn eine Erweiterung zulässig ist, modifizert.</li>
<li>eine Modifikationsfunktion MOD-, die die KAndidatenliste im negativen Fall, also wenn eine Erweiterung nicht zulässig ist, modifizert.</li>
<li>eine Funktion ZIEL, die den Wert einer Lösung ausgibt.</li>
</ul>

<h2><font color="green">Greedy Template</font color></h2>
<ul>
<li>(define greedy</li>
<li>(lambda (vorgabewert) ; zB Kapazität des Rucksacks</li>
<li>(let</li>
<li>((Kandidatenliste '(....))</li>
<li>(loesung? (lambda (ls) ...)</li>
<li>(okey? (lambda (ls) ...)</li>
<li>(naechster (lambda (ls)...)</li>
<li>(mod+ (lambda (x ls)...)</li>
<li>(mod- (lambda (x ls)...)</li>
<li>(ziel (lambda (ls)...)))</li>

<li>(letrec</li>
<li>((helfer</li>
<li>(lambda (kandidaten resultat)</li>
<li>(cond</li>
<li>((loesung? resultat)(ziel resultat)</li>
<li>((and (null? Kandidaten)(not(loesung? resultat)))</li>
<li>(error 'greedy "es gibt keine Lösung"))</li>
<li>(else</li>
<li>let* ((neuer-Kandidat (nächster Kandidat))</li>
<li>(neues resultat (cons neuer-kandidat resultat))</li>
<li>(if(okay? neues-resultat)</li>
<li>(helfer (mod+ neuer-kandidat kandidaten) neues-resultat)</li>
<li>(helfer (mod- neuer-kandidat kandidaten) resultat))))))</li>
<li>(helfer kandidatenliste '())))))</li>

</ul>



<h1><font color="green">Globales und lokales Optimum</font color></h1>
ca 20-25min
---Warum funktioniert der allgorithmus nur manchmal?
---Lokales Globales Optimum
---Matroide erklären

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.

<h2><font color="green">Matroide</font color></h2>
<h3><font color="green">Unabhängigkeit</font color></h3>
<h3><font color="green">erklärung an graph, bipartitem matching, vektoren</font color></h3>
<h3><font color="green">heranführung an definition...</font color></h3>



<h1><font color="green">Beispiele</font color></h1>
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>