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:'''

# eine sich verbrauchende '''Kandidatenliste'''
# eine sich aufbauende '''Resultatliste''' 
#'''Funktionen''' 
#*''loesung?'', die kontrolliert, ob die aktuelle Resultatliste eine Lösung des Problems darstellt
#*''okay?'', die kontrolliert, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
#*''ziel'', die den Wert einer Lösung angibt
#'''Auswahlfunktion'''
#*''nächster'', die aus der Kandidatenliste den jeweils besten "Happen" auswählt
#'''Modifikationsfunktionen'''
#* ''modify+'', die die Kandidatenliste im positiven Fall, also wenn die Erweiterung zu einer zulässigen Liste führt, modifiziert
#* ''modify-'', die die Kandidatenliste im negativen Fall, also wenn die Erweiterung nicht zu einer zulässigen Liste führen würde, modifiziert

<h2><font color="green">Greedy Template</font color></h2>

Bestandteile des Algorithmus:
* eine (sich verbrauchende) Kandidatenliste,
* eine (sich aufbauende) Resultatliste,
* Funktionen:
** ''loesung?'', die überprüft, ob die aktuelle Resultatliste eine Lösung des Problems darstellt,
** ''okay?'', die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist,
** ''naechster'', die den besten Kandidaten aus der Liste auswählt,
** ''modify+'', die die Kandidatenliste im positiven Fall modifiziert,
** ''modify-'', die die Kandidatenliste im negativen Fall modifiziert,
** ''ziel'', die die Lösung angibt.

 (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 '())))))

===Anwendungsbeispiel Geldwechsel===

====Scheme====
Als Beispiel für eine gierige Strategie betrachten wir nun die Herausgabe von Wechselgeld mit möglichst wenig Münzen. Es soll auf Geldbeträge Wechselgeld herausgegeben werden. Die dementsprechende Kandidatenliste besteht aus allen verfügbaren Münzen, mit denn Werten '''1, 2, 5, 10, 20, 50''' für Cent-Münzen und '''1''' und '''2''' für Euro Münzen. Die Münzen werden mit absteigendem Cent-Wert vor sortiert. 

<code id="4bd5b13f4d971" hidden>
 (define delete
  (lambda (item ls)
    (cond
      ((null? ls) '())
      ((eqv? (car ls) item) (cdr ls))
      (else
       (cons (car ls) (delete item (cdr ls)))))))</code>

<code id="4bd5b13f4e158">(define geldwechsel
  (lambda (restbetrag)
    (let ((kandidatenliste '(200 100 50 20 10 5 2 1))
          (loesung? (lambda (ls) (= restbetrag (apply + ls))))
          (okay? (lambda (ls) (<= (apply + ls) restbetrag)))
          (naechster car)
          (modify+ (lambda (x ls) ls))
          (modify- (lambda (x ls) (delete x ls)))
          (ziel (lambda (ls) (cons (reverse ls) (list (length 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>
Das Resultat wird als Liste mit dem Wechselgeld und der Anzahl der verwendeten Münzen ausgegeben.
<run id="4bd45ddfec40a">(geldwechsel 1293)</run>





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