Algorytmy zachłanne

Algorytmy zachłanne (greedy algorithms) to grupa algorytmów, w których rozwiązujemy problem krok po kroku, zawsze wybierając w danym momencie to, co wydaje się najlepsze „tu i teraz”. Nie analizujemy wszystkich możliwych kombinacji – ufamy, że lokalnie najlepsza decyzja doprowadzi nas do dobrego (czasem optymalnego) rozwiązania globalnego.

Zaletą takiego podejścia jest prostota i szybkość działania. Wadą – to, że nie zawsze gwarantuje rozwiązanie optymalne, zależy to od konkretnego problemu.

---

1. Kolorowanie mapy metodą zachłanną

Rozważmy mapę Polski podzieloną na województwa. Chcemy ją pokolorować tak, aby dwa sąsiadujące województwa miały różne kolory, używając możliwie małej liczby kolorów.

Idea algorytmu zachłannego

1. Wybierz pierwsze województwo i pokoloruj je kolorem nr 1.
2. Przechodź kolejno przez następne województwa.
3. Dla każdego z nich wybierz najmniejszy numer koloru, który nie pojawia się u jego sąsiadów.

Okazuje się, że każdą taką mapę można pokolorować maksymalnie 4 kolorami. Pokazany algorytm jest zachłanny: dla każdego województwa wybieramy natychmiast pierwszy możliwy (najmniejszy) kolor.

---

2. Wydawanie reszty metodą zachłanną

Kolejny klasyczny przykład to problem wydawania reszty: jak wydać daną kwotę za pomocą monet tak, aby liczba monet była jak najmniejsza?

Przykład

Dostępne nominały monet: 5 zł, 2 zł, 1 zł, 50 gr, 20 gr, 10 gr, 5 gr, 2 gr, 1 gr.
Mamy wydać 4,78 zł.

Algorytm zachłanny (algorytm kasjera)

1. Wybierz największy nominał, który nie przekracza pozostałej kwoty reszty.
2. Odejmij jego wartość od reszty.
3. Powtarzaj czynności 1–2, aż reszta będzie równa 0.

Działanie na przykładzie 4,78 zł

• 2 zł → zostaje 2,78 zł
• 2 zł → zostaje 0,78 zł
• 50 gr → zostaje 0,28 zł
• 20 gr → zostaje 0,08 zł
• 5 gr → zostaje 0,03 zł
• 2 gr → zostaje 0,01 zł
• 1 gr → zostaje 0,00 zł

Otrzymaliśmy rozwiązanie z minimalną liczbą monet – w typowym systemie monetarnym (takim jak polski) algorytm zachłanny daje wynik optymalny.

Kiedy zachłanność nie jest optymalna?

Jeśli nominały są „dziwne”, algorytm zachłanny może się mylić. Przykład: nominały 25, 10, 1, a reszta 30.

• Algorytm zachłanny: 25 + 1 + 1 + 1 + 1 + 1 = 30 (6 monet).
• Rozwiązanie optymalne: 10 + 10 + 10 = 30 (3 monety).

Wniosek: przy problemie wydawania reszty skuteczność metody zachłannej zależy od tego, jak wygląda zbiór nominałów.

Wyjaśnienie działania programu

---

3. Problem kinomana

Wyobraźmy sobie, że pewien miłośnik filmów uczestniczy w jednodniowym festiwalu filmowym. Ma listę seansów z podanymi godzinami:

• czas rozpoczęcia filmu,
• czas zakończenia filmu,
• identyfikator filmu (np. F1, F2, ...).

Cel: obejrzeć możliwie jak najwięcej filmów, pamiętając, że:

• nie można oglądać dwóch filmów jednocześnie,
• nie można jednego filmu opuścić przed końcem, aby wejść na inny,
• na kolejny seans można pójść dopiero po zakończeniu poprzedniego.

Specyfikacja problemu

• Dane: liczba filmów N, trzy listy:
  • P – godziny rozpoczęcia kolejnych filmów,
  • K – godziny zakończenia kolejnych filmów,
  • IDEN – identyfikatory filmów.
• Wynik: lista identyfikatorów filmów tworzących harmonogram, w którym kinoman obejrzy maksymalną liczbę filmów.

Strategie zachłanne

Możemy rozważyć różne kryteria wyboru kolejnego filmu:

• kryterium 1 – filmy zaczynające się najwcześniej,
• kryterium 2 – filmy najkrótsze,
• kryterium 3 – filmy kończące się najwcześniej.

Okazuje się, że tylko kryterium 3 (najwcześniej kończący się film) gwarantuje rozwiązanie optymalne.

Algorytm kinomana (kryterium 3 – kończy się najwcześniej)

1. Wczytaj dane do list P, K i IDEN.
2. Posortuj filmy według rosnącego czasu zakończenia (listy traktujemy jako tzw. listy równoległe).
3. Wybierz pierwszy film z posortowanej listy – to film, który kończy się najwcześniej.
4. Zapamiętaj jego czas zakończenia w zmiennej koniec_poprzedniego.
5. Przejdź po kolejnych filmach:
   • jeśli czas rozpoczęcia obecnego filmu > koniec_poprzedniego, dodaj film do harmonogramu i zaktualizuj koniec_poprzedniego,
   • w przeciwnym razie – pomiń film.

Taki algorytm jest zachłanny: w każdej chwili wybieramy ten film, który kończy się najwcześniej z dostępnych. Można matematycznie wykazać, że dla tego problemu daje on zawsze rozwiązanie optymalne.

---

4. Funkcje w kodzie programu „Problem kinomana”

Funkcja sortująca Sortuj

Do uporządkowania filmów według czasu zakończenia użyto sortowania przez wstawianie. Funkcja przyjmuje trzy listy: koniec, poczatek oraz iden.

Podczas przesuwania elementów w liście koniec odpowiednio przesuwane są elementy w listach poczatek i iden. Dzięki temu wszystkie trzy listy nadal opisują te same filmy. Takie listy nazywamy listami równoległymi.

Funkcja Wypisz

Funkcja Wypisz wypisuje informacje o jednym filmie: jego identyfikator, godzinę rozpoczęcia i zakończenia.

Funkcja Wybierz

Funkcja Wybierz realizuje zachłanny wybór filmów:

1. Najpierw wypisuje film o indeksie 0 (czyli ten, który kończy się najwcześniej).
2. Zapamiętuje jego czas zakończenia.
3. Przechodzi przez kolejne filmy i wybiera te, których początek jest późniejszy niż zakończenie ostatnio wybranego filmu.

Główna część programu:

• wypisuje harmonogram wszystkich filmów,
• sortuje je,
• wypisuje filmy po sortowaniu,
• wywołuje funkcję Wybierz, aby pokazać listę filmów wybranych przez kinomana.

Wyjaśnienie działania programu

---

5. Dlaczego warto znać algorytmy zachłanne?

• Są zwykle szybkie – często mają złożoność liniową lub logarytmiczną.
• Są proste do zaimplementowania w językach programowania (np. Python).
• Pojawiają się w wielu zadaniach maturalnych i konkursowych.
• Są używane w praktyce, m.in.:
  • w kompresji danych (np. kodowanie Huffmana),
  • w grafach (minimalne drzewo rozpinające),
  • w planowaniu zadań i tworzeniu harmonogramów.

Podstawowa zasada, którą warto zapamiętać:

Algorytm zachłanny w każdej chwili wybiera lokalnie najlepszą opcję, licząc na to, że doprowadzi ona do dobrego (czasem optymalnego) rozwiązania całego problemu.