Czym jest algorytm zachłanny i jak jest stosowany…

Algorytm zachłanny jest heurystycznym podejściem, które na każdym kroku podejmuje decyzję lokalnie optymalną, mając nadzieję, że doprowadzi to do rozwiązania optymalnego globalnie.

Zastosowania:

Problem wyboru aktywności:

Problem: Wybrać maksymalną liczbę nie nakładających się na siebie przedziałów z danego zbioru.
Rozwiązanie zachłanne: Posortować przedziały według rosnącego czasu zakończenia. Na każdym kroku wybierać przedział z najmniejszym czasem zakończenia, który nie nakłada się na już wybrane.

# Przykład wyboru aktywności
# 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]) # Sortujemy po czasie zakończenia

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) ]

Problem wymiany monet (Coin Change Problem) dla kanonicznych zestawów monet:
- Problem: Wydać zadaną kwotę minimalną liczbą monet.
- Rozwiązanie zachłanne: Używać maksymalnej możliwej liczby największych nominałów monet, aż kwota zostanie wydana. Działa tylko dla określonych zestawów monet (np. 1, 5, 10, 25).
```
# Przykład wymiany monet (dla kanonicznych monet)
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}
```
Algorytm Kruskala do znajdowania minimalnego drzewa rozpinającego:
- Problem: Znaleźć podzbiór krawędzi grafu nieskierowanego ważonego, który łączy wszystkie wierzchołki z minimalną sumą wag.
- Rozwiązanie zachłanne: Posortować wszystkie krawędzie według wagi rosnąco. Dodawać je w kolejności, jeśli nie tworzą cyklu z już wybranymi krawędziami, aż do uzyskania n-1 krawędzi (gdzie n to liczba wierzchołków).

Algorytmy zachłanne są łatwe do implementacji, ale nie zawsze znajdują rozwiązanie globalnie optymalne dla dowolnych problemów. Dla niektórych problemów (np. wymiana monet z dowolnym zestawem monet, problem plecakowy w ogólności) podejście zachłanne nie jest optymalne. Aby zagwarantować optymalność lub lepsze przybliżenie, mogą być potrzebne metody takie jak programowanie dynamiczne lub inne. Przed zastosowaniem algorytmu zachłannego ważne jest, aby upewnić się, że jest on odpowiedni dla danego problemu.

Czym jest algorytm zachłanny i jak jest stosowany przy rozwiązywaniu problemów?