Wprowadzenie do strategii zachłannej

Wprowadzenie

Strategia zachłanna (ang. greedy algorithm) to podejście do rozwiązywania problemów optymalizacyjnych, w którym dokonujemy lokalnie optymalnych wyborów w każdym kroku, mając nadzieję, że doprowadzi to do globalnie optymalnego rozwiązania.

Idea: "Zawsze wybieraj to, co wygląda najlepiej w danym momencie."

Algorytmy zachłanne są wykorzystywane w:

Planowaniu zadań (scheduling, zarządzanie procesami)
Kompresji danych (Huffman, LZW)
Algorytmach grafowych (najkrótsza ścieżka, minimalne drzewo rozpinające)
Problemach plecakowych (fractional knapsack)
Systemach operacyjnych (alokacja zasobów, szeregowanie)
Sieciach komputerowych (routing, przepływ)

Kluczowa cecha: Raz podjęta decyzja nigdy nie jest cofana.

Podstawowe cechy strategii zachłannej

Definicja formalna

Algorytm zachłanny dla problemu optymalizacyjnego:

1. Buduj rozwiązanie krok po kroku
2. W każdym kroku:
   - Wybierz element, który wygląda "najlepiej" lokalnie
   - Nie analizuj przyszłych konsekwencji
   - Nie cofaj wcześniejszych wyborów
3. Kontynuuj aż do uzyskania kompletnego rozwiązania

Pytanie kluczowe: Kiedy strategia zachłanna działa?

Właściwości problemów zachłannych

Aby problem można było rozwiązać zachłannie, musi posiadać dwie właściwości:

1. Greedy Choice Property (Własność wyboru zachłannego)

Globalnie optymalne rozwiązanie można uzyskać poprzez dokonywanie lokalnie optymalnych wyborów.

Przykład: Wydawanie reszty - zawsze wybieramy największą możliwą monetę.

2. Optimal Substructure (Optymalna podstruktura)

Optymalne rozwiązanie problemu zawiera optymalne rozwiązania podproblemów.

Przykład: Najkrótsza ścieżka z A do C przez B składa się z najkrótszych ścieżek A→B i B→C.

Strategia zachłanna vs programowanie dynamiczne

Kluczowe różnice

Aspekt	Strategia zachłanna	Programowanie dynamiczne
Wybór	Lokalnie optymalny (zachłanny)	Rozważa wszystkie możliwości
Decyzje	Nieodwracalne	Można "cofnąć" przez memoizację
Podproblemy	Rozwiązuje jeden podproblem	Rozwiązuje wszystkie podproblemy
Złożoność	Zazwyczaj O(n) lub O(n log n)	Zazwyczaj O(n²) lub więcej
Poprawność	Wymaga dowodu	Zawsze poprawne (jeśli dobrze zaimplementowane)

Wizualizacja różnic

Wyjście:

=== Porównanie podejść ===

Problem: Wydaj resztę 63 zł używając monet: 50, 20, 10, 5, 1

PODEJŚCIE ZACHŁANNE:
Krok 1: Wybierz 50 zł (największa ≤ 63) → reszta: 13 zł
Krok 2: Wybierz 10 zł (największa ≤ 13) → reszta: 3 zł
Krok 3: Wybierz 1 zł (największa ≤ 3) → reszta: 2 zł
Krok 4: Wybierz 1 zł (największa ≤ 2) → reszta: 1 zł
Krok 5: Wybierz 1 zł (największa ≤ 1) → reszta: 0 zł
Wynik: 5 monet [50, 10, 1, 1, 1]
Decyzja: NATYCHMIASTOWA w każdym kroku

PROGRAMOWANIE DYNAMICZNE:
Rozważa WSZYSTKIE kombinacje:
  - 1×50 + ... (co z resztą 13?)
  - 0×50 + 3×20 + ... (co z resztą 3?)
  - 0×50 + 0×20 + 6×10 + ... (co z resztą 3?)
  - ...
Buduje tabelę dla wszystkich kwot od 0 do 63
Wybiera rozwiązanie minimalne
Decyzja: PO ROZWAŻENIU wszystkich możliwości

Klasyczne przykłady algorytmów zachłannych

1. Problem wydawania reszty (kanoniczne systemy monet)

Problem: Wydaj kwotę n używając minimalnej liczby monet.

Strategia zachłanna: Zawsze wybieraj największą możliwą monetę.

Wyjście:

=== Wydawanie reszty - system kanoniczny ===

Reszta: 63 zł
  Monety: [50, 10, 1, 1, 1]
  Liczba: 5

Reszta: 77 zł
  Monety: [50, 20, 5, 1, 1]
  Liczba: 5

Reszta: 99 zł
  Monety: [50, 20, 20, 5, 1, 1, 1, 1]
  Liczba: 8

Reszta: 142 zł
  Monety: [50, 50, 20, 20, 1, 1]
  Liczba: 6

2. Problem wyboru aktywności (Activity Selection)

Problem: Masz n aktywności z czasami rozpoczęcia i zakończenia. Wybierz maksymalną liczbę nienakładających się aktywności.

Strategia zachłanna: Zawsze wybieraj aktywność kończącą się najwcześniej.

Wyjście:

=== Problem wyboru aktywności ===

Dostępne aktywności:
  A1: [ 1,  4]
  A2: [ 3,  5]
  A3: [ 0,  6]
  A5: [ 3,  9]
  A4: [ 5,  7]
  A6: [ 5,  9]
  A7: [ 6, 10]
  A8: [ 8, 11]
  A9: [ 8, 12]
  A10: [ 2, 14]
  A11: [12, 16]

Wybrane aktywności (maksymalna liczba: 4):
  A1: [ 1,  4]
  A4: [ 5,  7]
  A8: [ 8, 11]
  A11: [12, 16]

Wizualizacja na osi czasu:
     0    5    10   15
     |----|----|----|----|
      ─────── A1
                ────── A4
                         ───────── A8
                                     ──────────── A11

Dowód poprawności: Dlaczego "najwcześniejsze zakończenie" działa?

3. Problem plecakowy ułamkowy (Fractional Knapsack)

Problem: Masz plecak o pojemności W i przedmioty o wagach wᵢ i wartościach vᵢ. Można brać ułamki przedmiotów. Maksymalizuj wartość.

Strategia zachłanna: Sortuj przedmioty po wartości/waga i bierz w kolejności od najlepszego.

Wyjście:

=== Problem plecakowy ułamkowy ===

Pojemność plecaka: 50 kg

Dostępne przedmioty:
Nazwa      Waga (kg)    Wartość    Wartość/kg
--------------------------------------------------
Złoto      10           60         6.00
Srebro     20           100        5.00
Brąz       30           120        4.00
Miedź      15           45         3.00

==================================================
Maksymalna wartość: 240.00
==================================================

Wzięte przedmioty:
Nazwa      Ułamek     Waga         Wartość
--------------------------------------------------
Złoto      100%       10.0         60.00
Srebro     100%       20.0         100.00
Brąz       67%        20.0         80.00

Uwaga: To NIE działa dla 0/1 Knapsack (gdzie nie można brać ułamków)!

Kiedy strategia zachłanna NIE działa

Przykład 1: Problem 0/1 Knapsack

Wyjście:

=== Gdy strategia zachłanna ZAWODZI ===

Problem: 0/1 Knapsack (NIE można brać ułamków)
Pojemność: 50 kg

Przedmioty:
  A: waga=10 kg, wartość=60, ratio=6.0
  B: waga=20 kg, wartość=100, ratio=5.0
  C: waga=30 kg, wartość=120, ratio=4.0

STRATEGIA ZACHŁANNA (sortuj po ratio):
  1. Weź A (ratio=6.0): waga=10, wartość=60, pozostało=40
  2. Weź B (ratio=5.0): waga=20, wartość=100, pozostało=20
  3. C nie mieści się (waga=30 > 20)
  Suma: wartość=160, waga=30

ROZWIĄZANIE OPTYMALNE:
  1. Weź B: waga=20, wartość=100
  2. Weź C: waga=30, wartość=120
  Suma: wartość=220, waga=50

✗ Strategia zachłanna dała 160, optimum to 220!
✗ Zachłanna strategia NIE działa dla 0/1 Knapsack!

Przykład 2: Niekanoniczne systemy monet

Wyjście:

=== Niekanoniczny system monet ===

System monet: [25, 10, 1]
Kwota do wydania: 30

STRATEGIA ZACHŁANNA:
  1. Weź 25 (największa ≤ 30) → reszta: 5
  2. Weź 1 (największa ≤ 5) → reszta: 4
  3. Weź 1 (największa ≤ 4) → reszta: 3
  4. Weź 1 (największa ≤ 3) → reszta: 2
  5. Weź 1 (największa ≤ 2) → reszta: 1
  6. Weź 1 (największa ≤ 1) → reszta: 0
  Wynik: 6 monet [25, 1, 1, 1, 1, 1]

ROZWIĄZANIE OPTYMALNE:
  1. Weź 10
  2. Weź 10
  3. Weź 10
  Wynik: 3 monety [10, 10, 10]

✗ Zachłanna: 6 monet, Optimum: 3 monety
✗ Strategia zachłanna ZAWODZI!

Techniki dowodzenia poprawności

Metoda 1: Greedy Stays Ahead

Idea: Pokaż, że w każdym kroku rozwiązanie zachłanne jest "nie gorsze" niż optymalne.

Metoda 2: Exchange Argument

Idea: Pokaż, że zamiana elementu z rozwiązania optymalnego na zachłanny nie pogarsza wyniku.

Schemat projektowania algorytmu zachłannego

Praktyczne zastosowania

1. Szeregowanie zadań (Job Scheduling)

Wyjście:

=== Szeregowanie zadań (minimize lateness) ===

Zadania:
Nazwa    Czas trwania    Deadline
----------------------------------------
J1       3               6
J2       2               8
J3       1               9
J4       4               9
J5       3               14
J6       2               15

Harmonogram (Earliest Deadline First):
Zadanie  Start    Koniec   Deadline   Opóźnienie
--------------------------------------------------
J1       0        3        6          0
J2       3        5        8          0
J3       5        6        9          0
J4       6        10       9          1
J5       10       13       14         0
J6       13       15       15         0

Maksymalne opóźnienie: 1

Złożoność obliczeniowa

Typowe złożoności algorytmów zachłannych

Problem	Złożoność	Operacja dominująca
Activity Selection	O(n log n)	Sortowanie
Fractional Knapsack	O(n log n)	Sortowanie
Huffman Coding	O(n log n)	Operacje na kopcu
Coin Change (kanoniczny)	O(n)	Iteracja przez nominały
Job Scheduling	O(n log n)	Sortowanie
Dijkstra	O(E log V)	Kolejka priorytetowa
Prim/Kruskal	O(E log E)	Sortowanie krawędzi

Podsumowanie

Kluczowe koncepcje

Pojęcie	Definicja
Strategia zachłanna	Podejmowanie lokalnie optymalnych decyzji
Greedy Choice Property	Lokalnie optymalny wybór prowadzi do globalnego optimum
Optimal Substructure	Optimum zawiera optima podproblemów
Nieodwracalność	Decyzje nigdy nie są cofane

Kiedy używać strategii zachłannej?

✅ Działa gdy: - Problem ma własność wyboru zachłannego - Problem ma optymalną podstrukturę - Można udowodnić poprawność

✅ Zalety: - Proste w implementacji - Szybkie (zazwyczaj O(n log n) lub lepsze) - Efektywne pamięciowo

❌ NIE działa gdy: - Lokalne optimum ≠ globalne optimum - Potrzeba rozważyć wszystkie możliwości - Problem wymaga cofania decyzji

Techniki dowodzenia

Greedy Stays Ahead: Pokaż że zachłanne jest zawsze "przed" optymalnym
Exchange Argument: Zamień element optymalnego na zachłanny bez pogorszenia

Co dalej?

Po opanowaniu wprowadzenia do strategii zachłannej, następne kroki to:

Lekcja 74: Problem wydawania reszty
Zachłanny algorytm wydawania reszty
Kanoniczne systemy monet
Porównanie z programowaniem dynamicznym
Lekcja 75: Problem planowania zadań
Activity selection
Interval scheduling
Weighted job scheduling
Lekcja 76: Kompresja Huffmana
Drzewo Huffmana
Kodowanie i dekodowanie
Zastosowania w kompresji danych
Algorytmy grafowe:
Dijkstra (najkrótsza ścieżka)
Prim i Kruskal (MST)

Zadania praktyczne

Zadanie 1: Minimalna liczba paliw

Samochód jedzie autostradą z n stacjami paliw. Zbiornik mieści L litrów. Zaprojektuj zachłanny algorytm minimalizujący liczbę tankowań.

Zadanie 2: Problem przedziałów

Masz n przedziałów [start, end]. Znajdź minimalną liczbę punktów takich, że każdy przedział zawiera co najmniej jeden punkt.

Zadanie 3: Load balancing

Masz n zadań o czasach wykonania t₁, t₂, ..., tₙ i m procesorów. Przydziel zadania aby zminimalizować maksymalny czas pracy procesora.

Zadanie 4: Udowodnij poprawność

Udowodnij lub obal: algorytm zachłanny dla problemu wydawania reszty działa dla systemu monet {1, 5, 10, 25}.

Zadanie 5: Egipskie ułamki

Przedstaw ułamek p/q jako sumę różnych ułamków jednostkowych (postaci 1/n) używając strategii zachłannej.

Następna lekcja: Problem wydawania reszty - analiza zachłannego podejścia