Deutsch
Menü

Was ist Greedy-Algorithmus?

Methode des Algorithmenentwurfs, die eine Lösung aufbaut, indem sie wiederholt die im Moment am besten erscheinende Möglichkeit wählt, ohne frühere Entscheidungen zu überprüfen. Sie ist schnell und einfach, liefert aber nur dann eine optimale Lösung, wenn das Problem besondere Eigenschaften hat, wie bei Münzsystemen wie dem japanischen oder beim Kruskal-Algorithmus für minimale Spannbäume.

Japanische Bezeichnung: 貪欲法

„Greedy-Algorithmus“ kommt in 2 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Jetzt üben: Fragen zu Greedy-Algorithmus

8 Yen sollen mit Münzen zu 1 Yen, 4 Yen und 6 Yen bezahlt werden. Welche Aussage über die Zahl der Münzen, die ein Greedy-Algorithmus wählt (der zuerst so viele der größten Münze wie möglich verwendet), im Verhältnis zur kleinstmöglichen Münzzahl ist richtig?

  1. AAuch der Greedy-Algorithmus erreicht das Minimum von 2 Münzen
  2. BDer Greedy-Algorithmus verwendet 3 Münzen und verfehlt das Minimum von 2
  3. CDer Greedy-Algorithmus verwendet 3 Münzen, und das ist das Minimum
Antwort und Erläuterung anzeigen

Antwort: B. Der Greedy-Algorithmus verwendet 3 Münzen und verfehlt das Minimum von 2

Der Greedy-Algorithmus nimmt zuerst eine 6-Yen-Münze und zahlt die restlichen 2 Yen mit zwei 1-Yen-Münzen, insgesamt also 3 Münzen. Mit zwei 4-Yen-Münzen geht es aber mit nur 2. Weil ein Greedy-Algorithmus nur die jeweils im Moment beste Wahl aneinanderreiht, ist er bei manchen Münzsystemen nicht optimal. Die dynamische Programmierung, die eine Tabelle der kleinsten Münzzahl für jeden Betrag von 0 bis 8 Yen in aufsteigender Reihenfolge füllt, findet immer das Minimum. Bei Münzsystemen wie dem japanischen mit 1, 5, 10, 50, 100 und 500 Yen liefert der Greedy-Algorithmus stets das Minimum.

„Greedy-Algorithmus“ in den Erläuterungen

Fragen mit „Greedy-Algorithmus“ (2)

  1. 8 Yen sollen mit Münzen zu 1 Yen, 4 Yen und 6 Yen bezahlt werden. Welche Aussage über die Zahl der Münzen, die ein Greedy-Algorithmus wählt (der zuerst so viele der größten Münze wie möglich verwendet), im Verhältnis zur kleinstmöglichen Münzzahl ist richtig?
  2. Ein Rucksack mit der Kapazität 8 wird mit Gegenständen aus vier Gegenständen mit (Gewicht, Wert) (2, 3), (3, 4), (4, 5) und (5, 6) gefüllt. Jeden Gegenstand gibt es nur einmal, und Gegenstände lassen sich nicht teilen. Wie groß ist der höchste Gesamtwert bei einem Gesamtgewicht von höchstens 8?

Verwandte Begriffe

Dynamische Programmierung Binäre Suche (Binary Search) Binärer Heap (Binary Heap) Binärer Suchbaum (Binary Search Tree) Breitensuche (Breadth-First Search) Dijkstra-Algorithmus Hashtabelle (Hash Table) Rekursion Stabiles Sortierverfahren (Stable Sort) Stack (Stapelspeicher)

Zur Glossarübersicht