Greedyalgorithmen und -heuristiken

Wiki-Quelltext dieser Seite.

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
<h1><font color="green">Greedy-Algorithmen</font color></span></h1>

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>


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

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>


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