Greedy-Algorithmen SS11

Autoren:

• Stefan Brandt (s3stbran@stud.hs-zigr.de)
• Sascha Demuth (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

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 ausgezahlten (verwendeten) Münzen zurück.

Die Prozedur wird benutzt um 12,93 Euro (1293 Euro-Cent) herauszugeben.

Verschiedene Greedy-Algorithmen

Dijkstra-Algorithmus

Edsger W. Dijkstra auf Wikipedia

Kruskal-Algorithmus

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