Greedy-Algorithmen SS11
Inhaltsverzeichnis |
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.