Czym są algorytmy zachłanne?

Algorytmy zachłanne to odmiana algorytmów, które na każdym kroku podejmują decyzję lokalnie optymalną, mając nadzieję, że doprowadzi to do rozwiązania optymalnego globalnie.

Kluczowe cechy:

• Optimum lokalne: Na każdym kroku wybierane jest rozwiązanie, które wydaje się najlepsze w danym momencie, bez uwzględniania przyszłych konsekwencji.
• Brak cofania: Podjęte decyzje nie mogą być później zmienione.
• Wydajność: Często są proste w implementacji i mają stosunkowo wysoką efektywność w porównaniu do bardziej złożonych metod.

Przykłady problemów, dla których odpowiednie są algorytmy zachłanne:

• Problem wymiany (monety)
• Problem wyboru zgłoszeń (Interval Scheduling)
• Niektóre problemy minimalnego drzewa rozpinającego (np. algorytm Prima lub Kruskala)

Przykład podejścia zachłannego do problemu wymiany (wymiana 100 rublów na monety 50, 10, 5, 1):

1. Wziąć maksymalną możliwą liczbę monet 50 rublów (2 * 50 = 100).
2. Reszta: 0. Rozwiązanie znalezione.

Przykład, gdy algorytm zachłanny nie daje rozwiązania optymalnego (wymiana 82 rublów na monety 50, 25, 10):

Podejście zachłanne:

1. 1 * 50 = 50. Reszta: 32.
2. 1 * 25 = 25. Reszta: 7.
3. 0 * 10 = 0. Reszta: 7. Rozwiązanie: 1 moneta 50, 1 moneta 25, 0 monet 10 (niepełny wymiana)

Podejście optymalne:

1. 0 * 50 = 0. Reszta: 82.
2. 3 * 25 = 75. Reszta: 7.
3. 0 * 10 = 0. Reszta: 7. Rozwiązanie: 3 monety 25 (niepełny wymiana)

W tym przypadku rozwiązanie optymalne może istnieć, ale algorytm zachłanny go nie znajdzie.

Algorytmy zachłanne działają poprawnie tylko dla problemów zachłannych, które posiadają następujące właściwości:

• Właściwość optymalnej podstruktury: Optymalne rozwiązanie problemu zawiera optymalne rozwiązania jego podproblemów.
• Właściwość zachłannego wyboru: Lokalnie optymalny wybór na każdym kroku prowadzi do rozwiązania globalnie optymalnego.

# Przykład zachłannego podejścia do problemu wymiany
def greedy_change(amount, coins):
    result = {}
    sorted_coins = sorted(coins, reverse=True) # Sortujemy monety malejąco
    remaining_amount = amount

    for coin in sorted_coins:
        count = remaining_amount // coin # Ile monet tego nominału można wziąć
        if count > 0:
            result[coin] = count
            remaining_amount -= count * coin # Zmniejszamy resztę

    return result, remaining_amount

# Przykład użycia
amount = 100
coins = [50, 10, 5, 1]
change, remaining = greedy_change(amount, coins)
print(f"Dla sumy {amount} z monetami {coins}: Wymiana = {change}, Reszta = {remaining}")

amount_bad = 82
coins_bad = [50, 25, 10] # Przykład, w którym algorytm zachłanny może nie działać
change_bad, remaining_bad = greedy_change(amount_bad, coins_bad)
print(f"Dla sumy {amount_bad} z monetami {coins_bad}: Wymiana = {change_bad}, Reszta = {remaining_bad}")