INF.04 · C# · lekcja 25

Algorytmy zachłanne i heurystyki — problem komiwojażera

Porównaj decyzję lokalną z całą trasą

  • Zrozum
  • Sprawdź
  • Napisz sam

Po tej lekcji: porównaj decyzję lokalną z całą trasą

Dzisiaj zrobisz konkretną rzecz

Nie każdy problem da się rozwiązać "idealnie" w rozsądnym czasie — czasem jedyną realną opcją jest strategia, która w każdym kroku wybiera to, co wygląda najlepiej TERAZ, bez analizowania całości. To właśnie podejście zachłanne (greedy) i heurystyki — wymagane wprost w podstawie programowej (INF.04.3.3-4: "algorytmy zachłanne", "heurystyki, np. problem komiwojażera") i budujące ważną intuicję: szybkie, "wystarczająco dobre" rozwiązanie kontra wolne, ale gwarantowane najlepsze.

Kurier planujący trasę dostaw w ciągu dnia nie liczy WSZYSTKICH możliwych kolejności odwiedzenia klientów (dla 15 przystanków to ponad 43 biliardy permutacji) — używa uproszczonej strategii, np. "jedź zawsze do najbliższego kolejnego adresu". Nawigacje GPS przy wyznaczaniu tras z wieloma przystankami (np. Google Maps "zoptymalizuj kolejność") stosują właśnie heurystyki zbliżone do najbliższego sąsiąda, bo dokładne rozwiązanie TSP dla dużej liczby punktów jest obliczeniowo niewykonalne w rozsądnym czasie.

Sprawdź w działaniu

Porównaj decyzję lokalną z całą trasą

Najpierw przewidź wynik. Zmień dane w modelu i porównaj efekt. Spróbuj także przypadku granicznego, a nie tylko pierwszego poprawnego przykładu.

Ta interakcja wymaga włączonego JavaScriptu.

Model pokazuje wybraną zasadę. Nie uruchamia ani nie ocenia wklejonego kodu C#.

1. Przygotuj i uruchom własny projekt

2. Najpierw mały przykład

Wykonaj tę próbę przed dłuższym rozwiązaniem. Zachłanny wybór największej monety daje4+1+1, trzy monety. Lepsze3+3 używa dwóch. Ten kontrprzykład pokazuje, dlaczego lokalna decyzja nie gwarantuje optimum; podobnie testujemy trasę TSP w modelu.

Program.cscsharp
int kwota = 6;
int sztuki = 0;
foreach (int nominal in new[] { 4, 3, 1 })
{
    sztuki += kwota / nominal;
    kwota %= nominal;
}
Console.WriteLine(sztuki);
Wynik
3, choć optimum to2.
  1. Co sprawdzić? Zmień jedną wartość i przed uruchomieniem zapisz przewidywany rezultat. Porównaj go z opisem wyniku; przy błędzie wróć do konkretnej instrukcji.

Jak to działa — 1

Podejście zachłanne (ang. greedy) polega na tym, że w KAŻDYM kroku wybieramy najlepszą lokalnie dostępną opcję, licząc na to, że doprowadzi nas ona do dobrego rozwiązania globalnego. Algorytm NIE cofa się i NIE analizuje wszystkich możliwości — podejmuje decyzję i idzie dalej.

Klasyczny przykład — wydawanie reszty. Mając nominały 1, 2, 5, 10 zł i kwotę do wydania, algorytm zachłanny zawsze wybiera NAJWIĘKSZY nominał, który nie przekracza pozostałej reszty, odejmuje go i powtarza, aż reszta wyniesie 0. Dla dobrze dobranego zestawu nominałów (jak polskie monety) ta strategia daje OPTYMALNY wynik — najmniejszą możliwą liczbę monet.

Problem plecakowy (wersja ułamkowa/zachłanna). Mając plecak o ograniczonej pojemności i przedmioty o różnej wadze i wartości, algorytm zachłanny sortuje przedmioty według STOSUNKU wartość/waga (od najlepszego) i pakuje je po kolei, dopóki starcza miejsca. To NIE zawsze daje optymalny wynik dla wersji "0/1" (bierzesz cały przedmiot albo wcale) — ale jest szybkie i często "wystarczająco dobre".

Jak to działa — 2

Kiedy zachłanność DZIAŁA dobrze — gdy problem ma tzw. "własność zachłanności": najlepszy lokalny wybór faktycznie prowadzi do najlepszego globalnego wyniku. Przykłady: wydawanie reszty (dla typowych nominałów), znajdowanie minimalnego drzewa rozpinającego (algorytmy Kruskala, Prima), planowanie zadań o najkrótszym czasie wykonania.

Kiedy zachłanność ZAWODZI — problem plecakowy 0/1 (czasem trzeba zrezygnować z pozornie najlepszego przedmiotu, żeby zmieścić lepszy zestaw pozostałych), niektóre sieci dróg (skręt w "najkrótszą" ulicę teraz nie zawsze skraca całą trasę). W takich przypadkach zachłanność daje rozwiązanie SZYBKIE, ale niekoniecznie NAJLEPSZE.

Heurystyka to ogólniejsze pojęcie niż zachłanność — to każda metoda, która NIE gwarantuje znalezienia rozwiązania optymalnego, ale w rozsądnym czasie znajduje rozwiązanie "wystarczająco dobre". Heurystyki stosuje się tam, gdzie dokładne rozwiązanie wymagałoby sprawdzenia astronomicznej liczby możliwości.

Jak to działa — 3

Problem komiwojażera (TSP, Travelling Salesman Problem) — klasyczny przykład problemu, dla którego pełne przeglądanie permutacji szybko staje się niepraktyczne; istnieją jednak dokładne algorytmy lepsze od takiego przeglądania (dla n miast trzeba by sprawdzić aż (n-1)!/2 tras — dla20miast daje to60 822 550 204 416 000kolejności w symetrycznym TSP przy ustalonym starcie). Zadanie: komiwojażer ma odwiedzić wszystkie miasta z listy DOKŁADNIE RAZ i wrócić do punktu startu, pokonując jak najkrótszy łączny dystans.

Heurystyka "najbliższego sąsiada" dla TSP — prosta, zachłanna strategia: startujesz z dowolnego miasta, w każdym kroku jedziesz do NAJBLIŻSZEGO jeszcze nieodwiedzonego miasta, aż odwiedzisz wszystkie, po czym wracasz do startu. To NIE gwarantuje najkrótszej możliwej trasy (czasem "zapędzasz się" w odległy zakątek i musisz długo wracać), ale w ułamku sekundy daje rozsądny wynik, podczas gdy dokładne rozwiązanie mogłoby liczyć się latami.

3. Pełny przykład — czytaj od Main

Teraz zastąp Program.cs tym programem. Zanim uruchomisz, znajdź dane wejściowe, operację i miejsce prezentacji wyniku. W tym wariancie zachowujemy jawny Main. Nie wklejaj kilku pełnych programów do jednego pliku.

Program.cs — osobne uruchomieniecsharp
using System;
using System.Collections.Generic;
using System.Linq;

class AlgorytmyZachlanne
{
    // Zachłanne wydawanie reszty
    static List<int> WydajReszte(int kwota, int[] nominaly)
    {
        var wynik = new List<int>();
        // nominaly muszą być posortowane malejąco
        foreach (int nominal in nominaly)
        {
            while (kwota >= nominal)
            {
                kwota -= nominal;
                wynik.Add(nominal);
            }
        }
        return wynik;
    }

    // Heurystyka najbliższego sąsiada dla uproszczonego problemu komiwojażera
    static List<int> NajblizszySasiad(double[,] odleglosci, int start)
    {
        int n = odleglosci.GetLength(0);
        var odwiedzone = new bool[n];
        var trasa = new List<int> { start };
        odwiedzone[start] = true;
        int aktualne = start;

        for (int krok = 1; krok < n; krok++)
        {
            int najblizsze = -1;
            double minOdleglosc = double.MaxValue;

            for (int miasto = 0; miasto < n; miasto++)
            {
                if (!odwiedzone[miasto] && odleglosci[aktualne, miasto] < minOdleglosc)
                {
                    minOdleglosc = odleglosci[aktualne, miasto];
                    najblizsze = miasto;
                }
            }

            trasa.Add(najblizsze);
            odwiedzone[najblizsze] = true;
            aktualne = najblizsze;
        }

        trasa.Add(start); // powrót do punktu startowego
        return trasa;
    }

    static void Main()
    {
        int[] nominaly = { 10, 5, 2, 1 }; // od największego do najmniejszego
        var monety = WydajReszte(47, nominaly);
        Console.WriteLine($"Reszta z 47 zł: {string.Join(" + ", monety)} zł ({monety.Count} monet)");

        // Macierz odległości między 4 miastami (symetryczna)
        double[,] odleglosci = {
            { 0,  10, 15, 20 },
            { 10, 0,  35, 25 },
            { 15, 35, 0,  30 },
            { 20, 25, 30, 0  }
        };

        var trasa = NajblizszySasiad(odleglosci, start: 0);
        Console.WriteLine($"Trasa komiwojażera (najbliższy sąsiad): {string.Join(" -> ", trasa)}");
    }
}
  1. Prześledź kod WydajReszte zakłada, że tablica nominaly jest już posortowana MALEJĄCO — to ISTOTNE założenie algorytmu zachłannego: musimy zawsze próbować najpierw największy możliwy nominał, inaczej strategia przestaje być "zachłanna" i wynik może być gorszy. NajblizszySasiad w każdej iteracji pętli for (krok...) przeszukuje WSZYSTKIE jeszcze nieodwiedzone miasta i wybiera to o najmniejszej odległości od aktualnego — to jest właśnie decyzja "zachłanna": patrzymy tylko na NAJBLIŻSZY następny krok, nie na całą resztę trasy. Złożoność NajblizszySasiad to O(n²) (dla każdego z n kroków przeszukujemy do n miast) — DUŻO szybciej niż dokładne rozwiązanie TSP, które ma złożoność silniową O(n!) i staje się niewykonalne już dla ok. 15-20 miast.

Sprawdź, zanim przepiszesz cały program

Zakładanie, że algorytm zachłanny ZAWSZE daje optymalny wynik — to prawda tylko dla problemów mających "własność zachłanności" (jak dobrze dobrane nominały monet). Dla problemu plecakowego 0/1 czy ogólnego TSP zachłanność daje rozwiązanie DOBRE, ale nie zawsze NAJLEPSZE — trzeba to jasno rozróżniać.

Zapominanie o posortowaniu danych przed zastosowaniem strategii zachłannej — algorytm wydawania reszty bez posortowanych malejąco nominałów przestaje działać poprawnie; podobnie w plecaku zachłannym brak sortowania po stosunku wartość/waga daje przypadkowy, gorszy wynik.

Mylenie "heurystyki" z "błędnym algorytmem" — heurystyka CELOWO rezygnuje z gwarancji optymalności na rzecz szybkości. To nie jest błąd czy niedopracowanie, tylko świadomy wybór inżynierski, gdy dokładne rozwiązanie jest obliczeniowo niewykonalne w rozsądnym czasie.

Ćwiczenie z pomocą · samodzielna praca

4. Teraz Twoja zmiana

Uruchom program i sprawdź wynik dla różnych kwot w WydajReszte. Następnie dodaj piąte miasto do macierzy odległości w NajblizszySasiad i prześledź, czy heurystyka wybiera trasę, która "na oko" wygląda na najkrótszą, czy może zapędza się w niekorzystny zakątek.

Oczekiwany rezultat
Spełnij warunki polecenia. Zapisz wejście, otrzymany wynik i wyjaśnij, która część kodu za niego odpowiada.
Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź

Wróć do podstawowej formy oraz objaśnienia: Zachłanny wybór największej monety daje4+1+1, trzy monety. Lepsze3+3 używa dwóch. Ten kontrprzykład pokazuje, dlaczego lokalna decyzja nie gwarantuje optimum; podobnie testujemy trasę TSP w modelu.

Krok 2 — pokaż podpowiedź

Zmień tylko część potrzebną do polecenia. Zachowaj działającą wersję przed zmianą i uruchamiaj po każdym małym etapie.

Krok 3 — pokaż podpowiedź

Sprawdź przypadek zwykły i graniczny; porównaj z regułą: 3, choć optimum to2.

Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.

5. Sprawdź rozumienie, nie tylko uruchomienie

Dalej na swoim koncie

Rozgrzewki, quiz i zadania są w biurku ucznia.

Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.

Zaloguj się →
Źródła i dalsza nauka