vorige nächste

Die Vor - und Nachteile der greedy strategy


Erledigt man immer als nächstes den noch nicht bearbeiteten "fettesten Teilbrocken" des Problems, dann muss das nicht der für das Problem günstigste sein ( siehe das vorige Beispiel ). Daher führt die gierige Strategie in vielen Fällen zu recht guten, aber nicht unbedingt optimalen Lösungen. Warum kann diese "gierige" Auswahl zu negativen Effekten führen ?

Der Grund ist für die Frage der Einordnung in die Suchverfahren von zentraler Bedeutung: Eine einmal bei einer Verzweigung gefällte Entscheidung wird später nicht wieder rückgängig gemacht. So können Entscheidungen, die lokal günstig erschienen, die aus Sicht einer optimalen Lösung [ die man ja nicht kennt ] aber tatsächlich ungünstig waren, später nicht wieder rückgängig gemacht werden. Es ist nicht einmal so, dass bei späteren Entscheidungen auf mögliche frühere Fehlentscheidungen hin untersucht wird! Gerade hierin, in diesem "bedenkenlos" Vorwärtsgehen, liegt der besondere Vorteil von greedy - Verfahren.

Untersuchen wir dafür einmal das Beispiel der Labyrinthe. Man müsste so etwas wie eine Zielheuristik haben, beispielsweise die Annahme, alle Wege mit möglichst langen Gängen seien die besten. Es zeigt sich nun sehr schnell, dass solche Heuristiken so willkürlich sind, dass ein Erfolg auf diesem Wege vernachlässigbar unwahrscheinlich ist. Die Suche des Ausgangs in einem Labyrinth ist also sicher ein Problem, dass sich für greedy nicht eignet.

Um beim Bild zu bleiben: Greedy kann ich in einem Labyrinth versuchen, bei dem es von jedem Ort zu jedem anderen viele verschiedene Wege gibt ( viele Zyklen ) und ich beispielsweise nicht den Ausgang, sondern das Ungeheuer suche und sozusagen "immer dem Geruch nachgehe". Dann kann es mir passieren, dass ich vielleicht an der einen oder anderen Stelle eine falsche Entscheidung treffe, diese aber ohne Folgen bleibt, da ich auf einem späteren kleinen Umweg immer noch das Ziel erreichen kann: Der Weg ist dann sicher nicht optimal, das Verfahren liefert aber immer noch ein akzeptables Ergebnis bei einem vermutlich sehr viel geringeren Aufwand, als bei einer systematischen Suche.

Aber: In welcher Richtung stinkts ?

Bei der Entscheidung für eine Lösung mit greedy muss man vorher abklären, ob das Problem diesen Kriterien entspricht. Wenn ja, liegt man mit den Ergebnissen meistens recht gut.