Algorytmy i złożoność obliczeniowa — sortowanie, wyszukiwanie ścieżek i problemy NP-trudne

Dlaczego złożoność to właściwa abstrakcja

Algorytmy to precyzyjne przepisy: mając takie dane wejściowe, wykonaj te konkretne kroki. Ale dwa algorytmy mogą obliczać tę samą odpowiedź, zużywając drastycznie różne ilości czasu lub pamięci. Mierzenie tej różnicy w sekundach zegarowych jest bezużyteczne — zależy od sprzętu, kompilatora, tego, jakie inne procesy działają w tle. Potrzebujemy miary, która oddaje istotną trudność problemu, niezależną od sprzętu.

Notacja Big-O daje dokładnie to. O(n²) oznacza: jeśli podwoisz rozmiar danych wejściowych, czas działania mniej więcej się poczwori. O(n log n) oznacza, że podwojenie danych wejściowych nieznacznie więcej niż podwaja pracę. O(2ⁿ) oznacza, że każdy dodatkowy element wejściowy podwaja czas działania — wyrok śmierci dla dużych danych wejściowych. Te tempa wzrostu dzielą algorytmy na praktyczne kategorie, a różnica między algorytmem klasy 1 a klasy 3 może oznaczać różnicę między responsywną aplikacją a taką, która zawiesza przeglądarkę.

Sześć poniższych symulacji sprawia, że złożoność staje się widoczna: obserwujesz, jak algorytmy O(n²) tracą oddech wraz ze wzrostem n, i widzisz, jak sprytne struktury danych redukują przeszukiwanie grafu O(n²) do O((V + E) log V), wcale nie zmieniając odpowiedzi.

Część 1: Algorytmy sortowania

Symulacja sortowania — obserwacja O(n²) kontra O(n log n) na żywo

Sortowanie to pierwszy algorytm, który poznaje większość programistów, i najdokładniej przeanalizowany w informatyce. Jego prostota czyni go idealnym laboratorium do porównywania klas złożoności: sortowanie bąbelkowe i przez wstawianie mają w najgorszym przypadku złożoność O(n²); sortowanie przez scalanie i sortowanie kopcowe zawsze mają O(n log n); szybkie sortowanie ma średnio O(n log n), ale w najgorszym przypadku O(n²) bez losowego wyboru elementu centralnego.

Algorytm      Najlepszy  Średni     Najgorszy  Pamięć    Stabilny?
──────────────────────────────────────────────────────────────────
Bąbelkowe     Ω(n)       Θ(n²)      O(n²)      O(1)      Tak
Przez wstaw.  Ω(n)       Θ(n²)      O(n²)      O(1)      Tak
Przez wybór   Ω(n²)      Θ(n²)      O(n²)      O(1)      Nie
Przez scalan. Ω(n log n) Θ(n log n) O(n log n) O(n)      Tak
Szybkie       Ω(n log n) Θ(n log n) O(n²)*     O(log n)  Nie
Kopcowe       Ω(n log n) Θ(n log n) O(n log n) O(1)      Nie
Radix Sort    Ω(nk)      Θ(nk)      O(nk)      O(n+k)    Tak
Tim Sort      Ω(n)       Θ(n log n) O(n log n) O(n)      Tak

* Najgorszy przypadek szybkiego sortowania unika się losowym pivotem

Inwersje a sortowanie przez wstawianie:
  Koszt ∝ liczba inwersji w tablicy
  Tablica już posortowana: O(n) porównań (najlepszy przypadek)
  Odwrotnie posortowana: n(n-1)/2 inwersji → O(n²)

Dolna granica dla sortowania porównawczego:
  Każde sortowanie porównawcze wymaga Ω(n log n) porównań
  Dowód: drzewo decyzyjne ma n! liści → wysokość ≥ log₂(n!)

Symulacja sortowania wizualizuje wszystkie główne algorytmy obok siebie na tej samej tablicy. Wybierz rozmiar tablicy (od 8 do 1000 elementów), rozkład (losowy, prawie posortowany, odwrotnie posortowany, wiele duplikatów) i obserwuj animowany wykres słupkowy. Licznik porównań potwierdza przewidywanie Big-O: licznik sortowania przez scalanie rośnie jak n log n; licznik sortowania bąbelkowego rośnie jak n². Prawie posortowane tablice ujawniają ukrytą siłę sortowania przez wstawianie — jego najlepszy przypadek Ω(n).

Część 2: Wyszukiwanie ścieżek w grafach

Symulacja wyszukiwania ścieżek — Dijkstra i A*

Nawigacja, routing sieciowy, sztuczna inteligencja w grach — wszystko to sprowadza się do tego samego problemu: znajdź najkrótszą ścieżkę między dwoma węzłami w grafie ważonym. Algorytm Dijkstry rozwiązuje to optymalnie w O((V + E) log V) za pomocą kolejki priorytetowej. A* rozszerza Dijkstrę o funkcję heurystyczną szacującą pozostałą odległość, drastycznie redukując liczbę odwiedzanych węzłów na uporządkowanych grafach, takich jak siatki.

Dijkstra (najkrótsza ścieżka z jednego źródła):
  Wejście:  graf ważony G=(V,E), źródło s
  Wyjście: dist[v] = najkrótsza odległość od s do v

  Kolejka priorytetowa (kopiec min):
    dist[s] = 0; dist[v] = ∞ dla v ≠ s
    dopóki Q niepuste:
      u = extract_min(Q)
      dla każdego sąsiada v węzła u:
        jeśli dist[u] + w(u,v) < dist[v]:
          dist[v] = dist[u] + w(u,v)
          decrease_key(Q, v, dist[v])

  Złożoność: O((V + E) log V) z kopcem binarnym
             O(E + V log V) z kopcem Fibonacciego

Przeszukiwanie A*:
  f(n) = g(n) + h(n)
  g(n) = rzeczywisty koszt od źródła do n
  h(n) = heurystyka dopuszczalna (nigdy nie zawyża)

  Dopuszczalne heurystyki dla siatek:
    h = odległość euklidesowa (ruch w 8 kierunkach)
    h = odległość Manhattan  (ruch w 4 kierunkach)
    h = odległość Czebyszewa (8 kier., jednolity koszt po skosie)

  A* jest optymalny, gdy h jest dopuszczalna.
  A* odwiedza mniej węzłów niż Dijkstra, gdy h jest informatywna.

Przeszukiwanie wszerz (najkrótsza ścieżka nieważona):
  Złożoność: O(V + E)   znajduje najkrótszą ścieżkę licząc krawędzie

W symulacji wyszukiwania ścieżek rysuj ściany, ustaw punkt startowy i końcowy, a następnie porównaj Dijkstrę, A*, przeszukiwanie wszerz (BFS) i przeszukiwanie w głąb (DFS) na tym samym labiryncie. Licznik odwiedzonych węzłów uwidacznia różnicę: A* z heurystyką Manhattan często przeszukuje 5–10× mniej węzłów niż Dijkstra na siatce, docierając do celu bez skanowania nieistotnych obszarów. DFS znajduje jakąś ścieżkę szybko, ale rzadko najkrótszą.

Symulacja generowania labiryntów

Symulacja labiryntu naturalnie łączy się z wyszukiwaniem ścieżek. Generuje ona doskonałe labirynty (bez pętli, z jednym rozwiązaniem) za pomocą przeszukiwania w głąb z nawracaniem, algorytmu Prima lub algorytmu Kruskala ze strukturą danych Find-Union. Ponieważ doskonałe labirynty są drzewami rozpinającymi, stanowią one minimalny spójny podgraf siatki — piękne skrzyżowanie teorii grafów i kombinatoryki.

Przeszukiwanie w głąb (rekurencyjny backtracker):
  Doskonałe losowe labirynty — bezstronne, ale długie korytarze
  Czas O(V), pamięć stosu O(V)

Losowy algorytm Prima (rosnące drzewo):
  Dodaje losową krawędź ze zbioru granicznego
  Więcej rozgałęzień, krótsza średnia długość ścieżki
  O(E log E) z kolejką priorytetową

Kruskal + Find-Union:
  Przypisz losowe wagi wszystkim krawędziom, posortuj, dodaj jeśli brak cyklu
  Find-Union z kompresją ścieżek:
    find: O(α(n)) ≈ O(1) zamortyzowane
    union: O(α(n)) zamortyzowane
  Ogółem: O(E α(E)) ≈ O(E)

Algorytm Wilsona (błądzenie losowe z usuwaniem pętli):
  Generuje labirynty z rozkładem jednostajnym (naprawdę bezstronny)
  Oczekiwany czas O(V log V)
  Każde drzewo rozpinające równie prawdopodobne

Część 3: Backtracking i spełnianie ograniczeń

Symulacja N-Queens — przycinanie przestrzeni przeszukiwań

Ustaw N hetmanów na szachownicy N×N tak, by żadne dwa się nie atakowały. To kanoniczny problem spełniania ograniczeń. Naiwna metoda siłowa próbuje wszystkich N^N ustawień: dla N=8 to 16 milionów prób. Podstawowy backtracking redukuje to do 15 720 prób, porzucając częściowe rozwiązania w momencie naruszenia ograniczenia. Z forward checking liczba ta spada do około 2000.

Problem:
  Ustaw N hetmanów na planszy N×N, bez wspólnego wiersza/kolumny/przekątnej.

Rozwiązania:
  N=1: 1    N=4: 2    N=8: 92    N=12: 14 200
  N=13: 73 712    N=14: 365 596    N=15: 2 279 184

Naiwna siła brutalna:        O(N^N)
Backtracking (po wierszach): O(N!) — jeden hetman na wiersz
Ze śledzeniem kolumn:        unika O(N) sprawdzeń kolumn na ustawienie
Ze śledzeniem przekątnych:   dwie tablice boolowskie, rozmiar 2N-1 każda

Schemat backtrackingu:
  placeQueens(row, colsUsed, diag1, diag2):
    jeśli row == N: znaleziono rozwiązanie
    dla col w 0..N-1:
      jeśli col ∉ colsUsed ORAZ (row-col) ∉ diag1 ORAZ (row+col) ∉ diag2:
        recurse(row+1, ...)

Forward checking (AC-3):
  Po ustawieniu hetmana usuń zaatakowane pola z dziedzin
  Przytnij poddrzewa, gdzie dowolna zmienna ma pustą dziedzinę
  Znacząco redukuje liczbę nawrotów przy dużym N

Symulacja N-Queens animuje przeszukiwanie backtrackingowe. Obserwuj, jak algorytm ustawia hetmany wiersz po wierszu, cofa się, gdy utknie, próbuje kolejnej kolumny i w końcu znajduje rozwiązanie. Licznik pokazuje łączną liczbę wywołań rekurencyjnych, ujawniając, jak dramatycznie propagacja ograniczeń wypada w porównaniu z gołym backtrackingiem. Przełącz tryb „pokaż wszystkie rozwiązania", aby policzyć pełną przestrzeń rozwiązań.

Część 4: Problem komiwojażera

Symulacja TSP — NP-trudność w praktyce

Komiwojażer musi odwiedzić N miast dokładnie raz i wrócić do miasta startowego, minimalizując całkowity dystans. Rozwiązanie siłowe próbuje wszystkich (N-1)!/2 tras — dla N=20 to 60 biliardów tras. TSP jest NP-trudny: nie jest znany żaden algorytm wielomianowy i większość badaczy uważa, że żaden nie istnieje. Mimo to dla praktycznych rozmiarów sprytne heurystyki i dokładne solvery branch-and-bound szybko znajdują rozwiązania bliskie optymalnym.

Dokładne:
  Siła brutalna:              O((n-1)!/2)    niewykonalne dla n > 15
  Programowanie dynamiczne:   O(2ⁿ · n²)    algorytm Helda-Karpa
  Branch and Bound:           wykładniczy najgorszy przypadek, dobry w praktyce

Heurystyki konstrukcyjne (szybkie, suboptymalne):
  Najbliższy sąsiad:      O(n²)  — buduje trasę zachłannie
    stosunek do optimum:  średnio 1,25, może być 2× gorszy

  Zachłanne dodawanie krawędzi: O(n² log n)
    sortuj krawędzie wg długości, dodawaj jeśli ważne (bez krzyżowania, stopień < 2)

Przeszukiwanie lokalne (poprawa istniejącej trasy):
  2-opt:  usuń 2 krawędzie, połącz ponownie — O(n²) na przebieg
    iteruj do braku poprawy: O(n² · iteracje)
    zwykle w granicach 5% od optimum

  3-opt:  usuń 3 krawędzie — O(n³) na przebieg — lepsze, ale wolniejsze
  Lin-Kernighan (LK): wyrafinowane przeszukiwanie o zmiennej głębokości
    najlepsza heurystyka, < 1% od optimum w większości przypadków

NP-trudność:
  TSP jest NP-trudny: nie jest znany algorytm wielomianowy
  P ≠ NP (przy założeniu): nie istnieje efektywny algorytm dokładny
  TSP z nierównością trójkąta: aproksymacja 1,5 (Christofides 1976)

Symulacja TSP pozwala umieszczać miasta na płótnie, a następnie wybrać algorytm: najbliższy sąsiad, zachłanne krawędzie lub 2-opt. Licznik długości trasy aktualizuje się na żywo w miarę jak zamiany 2-opt poprawiają trasę. Dla 30 miast kilka sekund udoskonalania 2-opt zwykle osiąga wynik w granicach 3–5% od optimum. Zwiększ liczbę miast do 100+ i obserwuj, jak najbliższy sąsiad tworzy groteskowy bałagan skrzyżowań, który 2-opt szybko rozplątuje — to intuicja, dlaczego przeszukiwanie lokalne ma znaczenie.

Część 5: Algorytmy genetyczne

Symulacja algorytmu genetycznego — ewolucja jako optymalizacja

Gdy przestrzeń przeszukiwań jest zbyt rozległa dla metod dokładnych, a przeszukiwanie lokalne wpada w optima lokalne, algorytmy genetyczne wykorzystują mechanizmy ewolucji biologicznej — selekcję, krzyżowanie, mutację — do szerokiej eksploracji. Algorytmy genetyczne nie gwarantują znalezienia optimum globalnego, ale przy wielu praktycznych problemach znajdują doskonałe rozwiązania przy umiarkowanych obliczeniach.

Populacja:  P = {x₁, x₂, …, xₙ}  (kandydujące rozwiązania, zakodowane jako chromosomy)
Fitness:    f(x) → ℝ              (cel do maksymalizacji)

Operatory selekcji:
  Turniejowa:  wybierz k kandydatów, zwróć najlepiej przystosowanego
  Ruletka:     P(wybór xᵢ) = f(xᵢ) / Σf(xⱼ)
  Rankingowa:  prawdopodobieństwo ∝ rangę, nie surowy fitness (różnorodność)

Operatory krzyżowania:
  Jednopunktowe:  przetnij w losowej pozycji, zamień ogony
  Jednorodne:      każdy gen dziedziczony od rodzica 1 z prawdop. p
  Krzyżowanie porządkowe (OX): dla problemów permutacyjnych (TSP)
    skopiuj segment od rodzica 1, uzupełnij resztę od rodzica 2 w kolejności

Operatory mutacji:
  Zmiana bitu:  odwróć każdy bit z prawdopodobieństwem p_m
  Zamiana:      zamień dwie losowe pozycje
  Inwersja:     odwróć losowy podciąg

Twierdzenie o schematach (Holland):
  Krótkie, niskorzędowe, ponadprzeciętne schematy rosną wykładniczo
  Wewnętrzny paralelizm: n chromosomów niejawnie ocenia O(n³) schematów

Parametry w praktyce:
  Populacja: 50–500;  Współczynnik krzyżowania: 0,6–0,9;  Mutacja: 0,001–0,05
  Zbyt niska mutacja → przedwczesna zbieżność
  Zbyt wysoka mutacja → przeszukiwanie losowe

Symulacja algorytmu genetycznego wykorzystuje TSP jako swój cel optymalizacji. Obserwuj zbieżność populacji: wczesne pokolenia wykazują dziko rozproszone długości tras, potem presja selekcyjna przesuwa rozkład ku krótszym trasom, podczas gdy mutacje zapobiegają zapadnięciu się populacji do jednego rozwiązania. Wykreśl krzywe najlepszego/średniego fitnessu, aby zobaczyć klasyczny schodkowy wzorzec zbieżności — skokowe poprawy, gdy krzyżowanie odkrywa nową strukturalną poprawę.

Kolekcja algorytmów

Powiązania między kolekcjami

Algorytmy z tej kolekcji pojawiają się w całej platformie w przebraniu. Wyszukiwanie ścieżek A* stanowi podstawę unikania przeszkód w symulacji stada Boids — agenci znajdują ścieżki bez kolizji, korzystając z tej samej ekspansji kolejki priorytetowej. Find-Union z generowania labiryntów powraca w symulacji perkolacji, śledząc połączone klastry w sieci. Algorytmy genetyczne bezpośrednio napędzają symulację Algorytm genetyczny. Nawet sortowanie jest obecne w symulacji profilu skrzydła, gdzie wartości ciśnienia wzdłuż powierzchni są sortowane, aby znaleźć punkty stagnacji i separacji. Teoria złożoności łączy wszystko: powód, dla którego używamy algorytmów zachłannych do wyszukiwania ścieżek i heurystyk dla TSP, jest dokładnie ten sam — metody dokładne po prostu się nie skalują — fakt, który staje się namacalnie jasny, gdy obserwuje się, jak N-Queens eksploduje powyżej N=15.

Algorytmy i metody z tej kolekcji