Czym jest algorytm zachłanny i w jakich przypadkach jest stosowany?

Algorytm zachłanny to podejście do rozwiązywania problemów optymalizacyjnych, które w każdym kroku wybiera najlepsze rozwiązanie lokalne (najkorzystniejszą opcję z punktu widzenia aktualnego momentu) z nadzieją, że ta sekwencja optymalnych rozwiązań lokalnych doprowadzi do rozwiązania globalnie optymalnego. Nie bierze pod uwagę możliwych konsekwencji obecnego wyboru na przyszłe kroki.

Charakterystyki:

• Prostota: Zazwyczaj łatwiejszy do implementacji niż programowanie dynamiczne czy inne metody optymalizacji.
• Szybkość: Często ma mniejszą złożoność obliczeniową.
• Gwarancja optymalności: Nie zawsze gwarantuje znalezienie rozwiązania globalnie optymalnego. Gwarancja dotyczy tylko określonych klas problemów.

Stosuje się go w problemach, dla których udowodniono, że lokalnie optymalny wybór na każdym kroku prowadzi do rozwiązania globalnie optymalnego. Przykłady:

• Problem wyboru aktywności: Wybór maksymalnej liczby aktywności nie nakładających się czasowo.
• Problem plecaka (przy frakcjonowaniu przedmiotów): Gdy przedmioty można dzielić. W przeciwnym razie jest to problem programowania dynamicznego.
• Algorytm Prima i Kruskala: Do znajdowania minimalnego drzewa rozpinającego w grafie.
• Algorytm Dijkstry: Do znajdowania najkrótszej ścieżki w grafie z nieujemnymi wagami krawędzi.
• Kod Huffmana: Do tworzenia optymalnego kodu prefiksowego.

Przykład pseudokodu dla algorytmu wyboru aktywności:

Funkcja WybierzAktywnosci(aktywnosci):
  Posortuj aktywności według czasu zakończenia
  wybrane_aktywnosci = pusta lista
  ostatni_czas_zakonczenia = 0

  Dla każdej aktywności w aktywnościach:
    Jeśli czas_rozpoczęcia >= ostatni_czas_zakonczenia:
      Dodaj aktywność do wybranych
      ostatni_czas_zakonczenia = czas_zakonczenia

  Zwróć wybrane_aktywnosci

Ważne jest, aby sprawdzić, czy algorytm zachłanny jest odpowiedni dla konkretnego problemu, ponieważ w przeciwnym razie może dać rozwiązanie suboptymalne.