AuK/Greedy-Algorithmen SS11

Wiki-Quelltext dieser Seite.

Autoren:
* Stefan Brandt ([mailto:s3stbran@stud.hs-zigr.de s3stbran@stud.hs-zigr.de]) 
* Sascha Demuth ([mailto:s3sademu@stud.hs-zigr.de s3sademu@stud.hs-zigr.de])


== Idee ==

Bei vielen Optimierungsproblemen ist eine Verwendung der [[dynamischen Programmierung]] zur Bestimmung der besten Wahl übertrieben. Dann genügen einfachere, effizientere Greedy-Algorithmen.
Greedy bedeutet ''gefräßig'' - eine gefräßige Strategie, die nach der Methode "Nimm immer den besten Happen, den du kriegen kannst." arbeitet.

Diese Methode ist recht leistungsfähig und deshalb arbeiten Greedy-Algorithmen für einen großen Bereich von Problemen gut.

Aber was ist nun der beste "Happen"? Greedy-Algorithmen treffen die Entscheidung rechnerisch auf der Basis ''lokaler'' Information, d.h. ''ohne'' Rückgriff auf Werte, die für frühere Situationen ermittelt wurden. Dadurch resultiert, dass keine Tabelle, die alle Teilproblemlösungen bereithält, mitgeführt wird, wie das beim [[dynamischen Programmieren]] der Fall ist.

Außerdem wird eine einmal getroffene Entscheidung nicht korrigiert. Es gibt kein Zurücknehmen und Erproben von Alternativen wie beim [[systematischen Probieren mit Backtracking]].

Der Aufwand eines solchen Verfahrens ist sicher nicht exponentiell. Allerdings stellen wir die universelle Anwendbarkeit dieses "Superverfahrens" stark in Frage, da wir uns um effiziente Algorithmen bemühen.

Greedy-Algorithmen brauchen für die Auswahl des besten "Happens" eine vorsortierte Kandidatenliste. Neu aufzunehmende Elemente werden immer gleich an der richtigen Stelle eingefügt, so dass die Sortierung erhalten bleibt.

Der zugehörige Datentyp ist eine Prioritätswarteschlange (priority queue), die wir bereits bei [[Verzweigen und Beschränken]] behandelt haben.


== Bruchteilrucksackproblem ==


== Aufbau von Greedy-Algorithmen ==

Im Allgemeinen bestehen Greedy-Algorithmen aus den folgenden Bestandteilen:

* eine (sich verbrauchende) Kandidatenliste
* eine (sich aufbauende) Resultatliste
* eine Funktion ''loesung?'', die überprüft, ob die aktuelle Resultatliste eine (nicht unbedingt optimale) Lösung des Problems darstellt
* eine Funktion ''okay?'', die überprüft, ob die Erweiterung einer Resultatliste durch den nächsten Kandidaten zulässig ist
* eine Auswahlfunktion ''naechster'', die aus der Kandidatenliste den jeweils besten "Happen" auswählt
* eine Modifikationsfunktion ''modify+'', die die Kandidatenliste im positiven Fall verändert, demzufolge wenn die Erweiterung zu einer zulässigen Liste führt
* eine Modifikationsfunktion ''modify-'', die die Kandidatenliste im negativen Fall verändert, also wenn die Erweiterung zu einer unzulässigen Liste führt
* eine Funktion ''ziel'', die den Wert einer Lösung angibt

In SCHEME können wir eine Prozedur angeben, die eine Struktur aufweist, die für alle Greedy-Algorithmen unverändert übernommen werden kann. An den durch Punkte gekennzeichneten Stellen werden die Werte eingefügt, die dann den jeweils entsprechenden Algorithmus spezifizieren. Eine solche Prozedur wird demnach wie eine Schablone, ein sog. Template, benutzt.


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

<language>Scheme</language>
=== Beispiel Geldwechsel ===

Die Verwendung dieser Greedy-Schablone illustrieren wir am folgenden Beispiel der Prozedur ''geldwechsel''.

Einem Kunden wird Wechselgeld herausgegeben, wobei möglichst wenige Münzen verwendet werden sollen.

* Die ''Kandidatenliste'' besteht aus allen verfügbaren Euro-Münzen (1-, 2-, 5-, 10-, 20-, 50-Cent und 1- und 2-Euro-Münzen), die wir seit 01.01.2002 zusammen mit den Euro-Scheinen in Europa als Zahlungsmittel benutzen. Die Münzen werden mit absteigendem Cent-Wert vorsortiert.
* ''loesung?'' gibt #t zurück, wenn die Summe der verwendeten Münzen genau den auszuzahlenden Betrag ergibt.
* ''okay?'' gibt an, wenn eine Menge ausgewählter Münzen okay ist, wenn deren Summe höchstens dem zu zahlenden Betrag entspricht.
* Ist dies nicht der Fall, wird dieser Wert aus der Liste der (aussichtsreichen) Kandidaten entfernt. Dies erledigt die Prozedur ''modify-''.
* ''modify+'' lässt die Kandidatenliste unverändert. Dadurch wird erreicht, dass sich potenziell unendlich viele Münzen jeden Wertes in der ''Kandidatenliste'' befinden, so dass jeder beliebige Restbetrag immer ausgezahlt werden kann.
* Die Prozedur ''naechster'' wählt unter den verbleibenden Münzen die jenige mit dem jeweils höchsten Wert aus, ganz gleich, ob damit der zu zahlende Betrag überschritten wird oder nicht. (Dafür gibt es ja ''okay?'') Es wird immer das erste Element zurückgegeben, da zu jedem Zeitpunkt die Kandidatenliste absteigend sortiert ist.
* Die Funktion ''ziel'' gibt die Liste der verwendeten Münzen zurück.

<code id="4db593cd31be4" 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="4db593cd31c61">(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>


Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben.
<run id="4db593cd31d1e">
(geldwechsel 1293)
</run>

== Verschiedene Greedy-Algorithmen ==

===Allgemeines zur Graphentheorie===

Ein '''Graph''' ist eine mathematische Struktur, die aus '''Knoten''' und '''Kanten''' besteht. Diese Knoten können durch Kanten verbunden werden. Jede '''Kante''' verbindet in der Regel zwei '''Knoten''' miteinander. Die '''Kanten''' können, je nach Problemstellung, ''gerichtet'' oder ''ungerichtet'', ''bewertet'' (gewichtet) oder ''unbewertet'' (ungewichtet) sein.

[[Bild:S3sademu_Bewerteter_ungerichteter_Graph.png|thumb|295px|left|'''Bild 4.1:''' Bewerteter ungerichteter Graph mit 7 Knoten]]


'''Eigenschaften des Graphen''':                 
*'''gerichtet''' -  wenn die Kanten einseitig gerichtete Pfeile sind
*'''ungerichtet''' - wenn die Kanten in beide Richtungen gelten
*'''bewertet''' - ist wenn jeder Kante ein Wert zu geordnet wird
*'''unbewertet''' - ist wenn keiner Kante ein Wert zu geordnet wird
* '''zusammenhängend''' - ist, wenn von jedem Knoten zu jedem anderen Knoten ein Weg vorhanden ist
* Ein Graph ohne Zyklen entspricht einem Baum.
* Ein aufspannender Baum ist ein Teil des Graphen, der alle Knoten enthält, aber nur so viele Kanten besitzt, dass er einen Baum bildet.

=== Dijkstra-Algorithmus ===

[[Bild:Dijksta_Anim.gif|thumb|284px|'''Bild 4.2:''' Dijkstras Algorithmus<br />(Quelle: [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Wikipedia])]]

[http://de.wikipedia.org/wiki/Edsger_Wybe_Dijkstra Edsger W. Dijkstra auf Wikipedia]

'''Kürzeste Wege in Graphen'''

Die Suche nach der kürzesten Rundreise, die ''n'' gegebene Städte genau einmal besucht, gehört zu den schwierigsten Problemen, für die bisher nur Lösungsverfahren mit exponentieller Rechenzeit bekannt sind (siehe: [[Verzweigen_und_beschränken#Das_Rundreiseproblem|Verzweigen und beschränken: Das Rundreiseproblem]]).

Das folgende Problem klingt noch schwieriger. Gesucht ist der kürzeste Weg von Stadt ''A'' zu Stadt ''B'', wobei für die ''n'' betrachteten Städte eine Entfernungsmatrix gegeben ist. Man muss ''alle'' Zwischenstädtefolgen (Wege) betrachten, auch solche, die nicht alle Städte enthalten.

Edsger W. Dijkstra fand 1959 einen Algorithmus zur Lösung des Kürzeste-Wege-Problems dessen Rechenzeit in <math>\mathcal{O}(n^2)</math> liegt. Ein nach [http://de.wikipedia.org/wiki/Algorithmus_von_Floyd_und_Warshall Robert Floyd und Stephen Warshall] benanntes Verfahren löst eine etwas weiter gehende fragestellung in <math>\mathcal{O}(n^3)</math>. Dabei werden die kürzesten Wege für ''alle'' Städtpaare bestimmt.

Das Problem ist, mathematisch gesehen, eine Sache der [http://de.wikipedia.org/wiki/Graphentheorie Graphentheorie].

Unter einem endlichen Graph ''G'' versteht man ein Paar ''(V, E)'', wobei ''V'' eine endliche ''Knoten''menge (Knoten = vertex) und ''E'' eine endliche Menge von Kanten (edges) bezeichnet. Eine Kante verbindet genau zwei Knoten. Es ist nicht verlangt, dass alle Knotenpaare durch je eine Kante verbunden sind. Es kann auch Mehrfachkanten geben.

Zur Speicherung von Graphen verwendet man Matrizen. Eine gängige Form sind sog. ''Adjazenmatrizen'', die für jedes Knotenpaar vermerken, ob die durch die aktuelle Zeile bzw. Spalte bestimmten Knoten durch eine Kante verbunden sind.

Handelt es sich um einen ''gewichteten Graph'', dessen Kanten z.B. mit je einer Zahl für eine bestimmte Länge, Masse oder einen Euro-Betrag markiert sind, werden diese ''Gewichte'' in der Adjazenmatrix angegeben. Nicht vorhandene Kanten werden durch einen vereinbarten Wert, meist 0, x oder eine sehr große Zahl, beschrieben. Die folgende Matrix zu dem Graphen aus '''Bild 4.1''' ist ein solches Beispiel.


[[Bild:S3sademu_Entfernungsmatrix.png|'''Bild 4.3:''' Entfernungsmatrix]]


Die englische Bezeichnung für gerichtete Graphen ist ''directed graph'', woraus sich der häufig verwendete Begriff Digraph erklärt.

=== Kruskal-Algorithmus ===

[http://de.wikipedia.org/wiki/Joseph_Kruskal Joseph Kruskal auf Wikipedia]

=== Prim-Algorithmus ===

== Literatur und andere Quellen ==

* Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: ''Algorithmen - Eine Einführung'', 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8

* Volker Heun: ''Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen'', 2. Auflage, Vieweg+Teubner Verlag 2003, ISBN 978-3528131401

* Ch. Wagenknecht: ''Algorithmen und Komplexität'', 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2