A3.1 Greedy

Autor: Urs Battaglia

Greedy-Algorithmen widerspiegeln in der Informatik den in der Wirtschaft häufig eingeschlagenen Weg der kurzfristigen Gewinnmaximierung.
Die gierigen Algorithmen zeichnen sich durch die Auswahl desjenigen Folgezustandes aus, der zum Zeitpunkt der Wahl den grössten Gewinn bzw. das beste Ergebnis verspricht. Dafür wird eine Bewertungsfunktion benötigt, welche die Folgezustände einordnet.

1. Greedy-Algorithmen sind meist schnell, lösen viele Probleme aber nicht optimal, da sie frühzeitig Wahlen treffen, welche später nicht mehr korrigiert werden können.
2. Im Gegensatz zu Backtracking (A2.2 Backtracking) schauen Greedy-Algorithmen nur nach vorn, die Vergangenheit ist vollkommen irrelevant.
3. Greedy-Algorithmen benötigen immer eine geeignete Bewertungsfunktion, welche starken Einfluss auf den Verlauf des Algorithmus hat.

1. Ich kenne die Eigenschaften, Vor- und Nachteile von Greedy-Algorithmen und kann diese anhand von Beispielen erläutern.
2. Ich kann erklären, weshalb Greedy-Algorithmen im Allgemeinen keine globale (optimale) sondern nur eine lokale Lösung finden.
3. Ich kenne Greedy-Algorithmen für ausgesuchte Probleme (z.B. TSP) und kann diese erklären.
4. Ich kann für ein gegebenes Problem selbst einen Greedy-Algorithmus entwerfen und als Fluss- oder Nassi-Shneidermann-Diagramm darstellen.

• Rückgeld mit möglichst wenig Münzen
• Rucksackproblem
• Traveling Salesman Problem
• Nullstellensuche mit Newtonverfahren
• Suche nach Lawinenverschütteten
• Monopoly und andere Brettspiele

• A2.2 Backtracking

• Leitprogramm "Greedy" und "Divide & Conquer"

• Manchmal bringt auch Gier weiter. — Paul Miotti 2008/06/24