Algorytmy zachłanne i heurystyki — problem komiwojażera

Po co się tego uczymy?

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.

Teoria

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".

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.

Problem komiwojażera (TSP, Travelling Salesman Problem) — klasyczny przykład problemu, dla którego dokładne rozwiązanie jest praktycznie niemożliwe do policzenia dla większej liczby miast (dla n miast trzeba by sprawdzić aż (n-1)!/2 tras — dla zaledwie 20 miast to więcej możliwości niż atomów w części widzialnego wszechświata). 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.

Schemat

PODEJŚCIE ZACHŁANNE — schemat ogólny
START
  │
  ▼
Wybierz najlepszą LOKALNIE dostępną opcję
  │
  ▼
Zaktualizuj dane (problem się zmniejsza)
  │
  ▼
Czy zostało coś do zrobienia? ──TAK──┐
  │NIE                                │
  ▼                                   │
KONIEC                    powrót do "Wybierz..." ◄┘

PROBLEM KOMIWOJAŻERA — heurystyka najbliższego sąsiada
Start: miasto A
  A → (najbliższe nieodwiedzone: B) → B
  B → (najbliższe nieodwiedzone: D) → D
  D → (najbliższe nieodwiedzone: C) → C
  C → powrót do A
Trasa: A → B → D → C → A  (dobra, ale niekoniecznie NAJKRÓTSZA z możliwych)

Przykład z życia

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.

Program.cs

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();
        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 = ; 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 = {
            { ,  10, 15, 20 },
            { 10, ,  35, 25 },
            { 15, 35, ,  30 },
            { 20, 25, 30,   }
        };

        var trasa = NajblizszySasiad(odleglosci, start: );
        Console.WriteLine($"Trasa komiwojażera (najbliższy sąsiad): {string.Join(" -> ", trasa)}");
    }
}

Komentarz i wyjaśnienie kodu

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.

Ćwiczenie samodzielne

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.

Zadania do pracy własnej

Zmodyfikuj WydajReszte, żeby oprócz listy monet wypisywała też, ile SZTUK każdego nominału użyto (np. "10 zł: 4 szt., 5 zł: 1 szt., 2 zł: 1 szt.").
Napisz zachłanny algorytm pakowania plecaka: mając tablicę przedmiotów (nazwa, waga, wartość) i maksymalną pojemność plecaka, posortuj przedmioty według stosunku wartość/waga (malejąco) i pakuj je po kolei, dopóki się mieszczą. Wypisz wybrane przedmioty i sumaryczną wartość.
Rozbuduj przykład z problemem komiwojażera: policz DOKŁADNE rozwiązanie dla macierzy z 4-5 miast metodą "sprawdź wszystkie permutacje" (możesz użyć rekurencji z lekcji 20) i porównaj długość trasy z wynikiem heurystyki najbliższego sąsiada. Dla ilu miast dokładna metoda staje się zauważalnie wolna na Twoim komputerze?

Typowe błędy

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.

Nawiązanie do egzaminu zawodowego

To bezpośrednie pokrycie INF.04.3.3-4: "stosuje metody rozwiązywania problemów... heurystyki (problem komiwojażera)" oraz "stosuje algorytmy sortowania i wyszukiwania... zachłanne". Razem ze złożonością obliczeniową (lekcja 24, notacja Big O) ten temat tłumaczy, DLACZEGO w ogóle potrzebujemy heurystyk — bo niektórych problemów po prostu nie da się rozwiązać dokładnie w akceptowalnym czasie, nawet na najszybszym komputerze.