Was ist ein greedy Algorithmus und wie wird er bei…

Der greedy-Algorithmus ist ein heuristischer Ansatz, der bei jedem Schritt die lokal optimale Entscheidung trifft in der Hoffnung, dass dies zu einer global optimalen Lösung führt.

Anwendungen:

Aktivitätsauswahlproblem:

Problem: Wählen Sie die maximale Anzahl nicht überlappender Intervalle aus einem gegebenen Satz.
Greedy-Lösung: Sortieren Sie die Intervalle nach aufsteigender Endzeit. Wählen Sie bei jedem Schritt das Intervall mit der kleinsten Endzeit, das sich nicht mit den bereits gewählten überschneidet.

# Beispiel für Aktivitätsauswahl
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Nach Endzeit sortieren

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Münzwechselproblem (Coin Change Problem) für kanonische Münzsets:
- Problem: Geben Sie einen bestimmten Betrag mit der minimalen Anzahl von Münzen aus.
- Greedy-Lösung: Verwenden Sie die größtmögliche Anzahl der größten Münzdenominationen, bis die Summe ausgegeben ist. Funktioniert nur für bestimmte Münzsets (z.B. 1, 5, 10, 25).
```
# Beispiel für Münzwechsel (für kanonische Münzen)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Kruskal-Algorithmus zur Bestimmung des minimalen Spannbaums:
- Problem: Finden Sie eine Teilmenge von Kanten eines zusammenhängenden gewichteten ungerichteten Graphen, die alle Knoten mit minimalem Gesamtkantengewicht verbindet.
- Greedy-Lösung: Sortieren Sie alle Kanten nach Gewicht in aufsteigender Reihenfolge. Fügen Sie Kanten in Reihenfolge hinzu, wenn sie keinen Kreis mit den bereits gewählten Kanten bilden, bis n-1 Kanten erreicht sind (wobei n die Anzahl der Knoten ist).

Greedy-Algorithmen sind einfach zu implementieren, aber finden nicht immer die global optimale Lösung für beliebige Probleme. Für einige Probleme (z.B. Münzwechsel mit beliebigen Münzsets, das allgemeine Rucksackproblem) ist der greedy-Ansatz nicht optimal. Um die Optimalität oder eine bessere Annäherung zu gewährleisten, sind dynamische Programmierung oder andere Methoden erforderlich. Vor der Anwendung eines greedy-Algorithmus sollte sichergestellt werden, dass er für das jeweilige Problem geeignet ist.

Was ist ein greedy Algorithmus und wie wird er bei der Lösung von Problemen angewendet?