Greedy-Algorithmen SS11

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2011-04-07T11:49:56+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren:


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


Beispiel Geldwechsel


Verschiedene Greedy-Algorithmen

Dijkstra-Algorithmus

Kruskal-Algorithmus

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