4.1 Definition der Gierigen Algorithmen.
Gierige Algorithmen (Greedy Algorithms) sind eine Klasse von Algorithmen, die eine Lösung durch das Treffen von lokal optimalen Entscheidungen in jedem Schritt aufbauen. Diese Entscheidungen werden basierend auf dem aktuellen Zustand getroffen und in der Zukunft nicht überdacht.
Gierige Algorithmen werden oft verwendet, um Optimierungsprobleme zu lösen, wo das Ziel ist, eine bestimmte Größe zu maximieren oder zu minimieren.
Grundlegende Prinzipien der gierigen Algorithmen
- Gierige Wahl: In jedem Schritt wählt der Algorithmus die beste lokale Option, von der er glaubt, dass sie zur global optimalen Lösung führt.
- Optimale Teilstruktur: Das Problem sollte die Eigenschaft haben, dass lokal optimale Lösungen kombiniert werden können, um eine global optimale Lösung zu erhalten.
- Monotonie: Nach der Wahl des nächsten lokal optimalen Schritts sollte die Lösung nicht durch nachfolgende Entscheidungen verschlechtert werden.
Vorteile und Nachteile der gierigen Algorithmen
Vorteile:
- Einfachheit der Implementierung: Gierige Algorithmen sind oft einfach zu verstehen und zu implementieren.
- Effizienz: Sie sind in der Regel schneller als komplexere Algorithmen wie dynamische Programmierung.
Nachteile:
- Fehlen globaler Optimalität: Gierige Algorithmen führen nicht immer zu einer global optimalen Lösung.
- Nicht alle Probleme sind geeignet: Nur bestimmte Probleme können durch gierige Algorithmen gelöst werden.
Es gibt eine ganze Klasse von Problemen, bei denen die beste Lösung durch einen gierigen Algorithmus erreicht wird. Es wird nützlich für dich sein, über solche zu lernen.
4.2 Das Münzwechselproblem.
Problem:
Wir haben Münzen unterschiedlicher Nennwerte. Es ist nötig, die minimale Anzahl von Münzen für den Wechsel eines gegebenen Betrages zu finden.
Lösung:
Man nimmt immer die Münze mit dem höchsten Nennwert, die den verbleibenden Betrag nicht überschreitet.
Zeitkomplexität: O(n), wobei n die Anzahl der Münztypen ist.
Beispielcode in Python:
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Das Rucksackproblem
Problem:
Wir haben Gegenstände mit bekanntem Wert und Gewicht. Wir wollen so viele Gegenstände wie möglich in einen Rucksack von fester Größe packen.
In dieser Variante des Problems kann man Gegenstände in Teile teilen. Zum Beispiel wollen wir verschiedene Getreidesorten kaufen und können sowohl 1000 Gramm als auch 512 Gramm nehmen.
Lösung:
Sortiere die Gegenstände nach spezifischem Wert (Wert/Gewicht) und wähle die höchsten spezifischen Werte bis der Rucksack voll ist.
Zeitkomplexität: O(n log n), wobei n die Anzahl der Gegenstände ist.
Beispielcode in Python:
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Das Segmentabdeckungsproblem
Problem:
Es gibt Segmente auf einer geraden Linie, die durch ihre Enden (x1, x2) definiert sind, und ein Zielsegment. Es ist nötig, die minimale Anzahl von Segmenten zu finden, die alle Punkte des Zielsegments abdecken.
Lösung:
Sortiere die Segmente nach dem rechten Ende und wähle das kleinste Segment, das den aktuellen Punkt abdeckt.
Zeitkomplexität: O(n log n), wobei n die Anzahl der Segmente ist.
Beispielcode in Python:
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION