Podręcznik

Obecnie informatyka opiera się na efektywnym rozwiązywaniu problemów. Sercem tego procesu są oczywiście algorytmy. W celu utworzenia skutecznego algorytmu, projektanci sięgają po zestaw sprawdzonych metod konstrukcyjnych. Do najważniejszych z nich należą: 

• metody typu „dziel i zwyciężaj”,
• algorytmy bazujące na programowaniu dynamicznym, 
• algorytmy zachłanne, 
• algorytmy z powrotami, 
• metody heurystyczne,
• algorytmy probabilistyczne,
  
• algorytmy iteracyjne (np. gradientowe),
  
• algorytmy przeszukiwania.

Metody typu „dziel i zwyciężaj"

Metoda „dziel i zwyciężaj” polega na podziale problemu na mniejsze, prostsze podproblemy, które są następnie rozwiązywane niezależnie, a ich wyniki łączone w rozwiązanie problemu głównego. To podejście często wykorzystuje się w algorytmach sortowania, takich jak sortowanie szybkie czy sortowanie przez scalanie. Technika ta opiera się na rekurencji i umożliwia uzyskanie znacznej poprawy wydajności w porównaniu do metod naiwnych.

Oto przykłady zastosowania podejścia dziel i zwyciężaj:

• Sortowanie przez scalanie (ang. Merge Sort) – dzieli tablicę na dwie połowy, sortuje je rekurencyjnie, a następnie scala w jedną posortowaną tablicę.

• Sortowanie szybkie (ang. Quick Sort) – wybiera element główny (pivot), dzieli tablicę na elementy mniejsze i większe od pivota, a następnie sortuje każdą część osobno.

• Mnożenie dużych liczb (algorytm Karatsuby) – rozkłada liczby na mniejsze części, mnoży je i łączy wynik przy mniejszej liczbie mnożeń niż klasyczny algorytm.

• Przeszukiwanie binarne – dzieli uporządkowaną listę na pół i przeszukuje tylko tę część, w której może znajdować się szukany element.

• Algorytm znajdowania największego wspólnego dzielnika (NWD) – rekurencyjnie dzieli problem na mniejsze, korzystając z własności dzielników.

• Znajdowanie maksimum i minimum w tablicy – dzieli tablicę na części, znajduje lokalne maksimum i minimum, a następnie wybiera globalne.

• Algorytmy do przetwarzania obrazów (np. kompresja JPEG) – dzielą obraz na mniejsze bloki i przetwarzają każdy blok niezależnie.

• Szybkie przekształcenie Fouriera (FFT) – dzieli problem przekształcenia sygnału na mniejsze podproblemy, przekształca je i łączy wynik.

• Zliczanie inwersji w tablicy – łączy sortowanie przez scalanie z liczeniem par elementów w złej kolejności.

• Algorytmy do znajdowania najbliższej pary punktów na płaszczyźnie – dzielą zbiór punktów i łączą wyniki przy pomocy sprytnej analizy geometrycznej.

Algorytmy bazujące na programowaniu dynamicznym

Programowanie dynamiczne to technika, która sprawdza się w problemach z nakładającymi się podproblemami i optymalną strukturą. W odróżnieniu od „dziel i zwyciężaj”, gdzie podproblemy są niezależne, tutaj ich rozwiązania są przechowywane i wykorzystywane wielokrotnie, co zapobiega redundantnym obliczeniom. Programowanie dynamiczne stosuje się na przykład w problemie plecakowym, w obliczaniu wartości ciągów czy w analizie sekwencji biologicznych. Metoda ta pozwala znacząco skrócić czas działania algorytmu, choć często kosztem zwiększonego zużycia pamięci.

Do tej pory nic nie mówiliśmy o typowych zastosowaniach programowania dynamicznego. Otóż wzorcowymi przykładami wykorzystania PD są zadania polegające na:

• Rozwiązaniu problemu „plecakowego”,
• Znalezieniu najkrótszych ścieżek między parami węzłów grafu – algorytm Floyda-Warshalla,
• Obliczeniu wyrazów ciągu Fibonacciego lub kolejnych wartości symbolu Newtona.

Algorytmy zachłanne

Algorytmy zachłanne działają według prostej zasady: wybieraj na każdym kroku najlepszą lokalnie opcję, mając nadzieję, że doprowadzi to do najlepszego globalnego rozwiązania. Choć nie zawsze dają one wynik optymalny, to w wielu przypadkach, takich jak znajdowanie minimalnego drzewa rozpinającego czy wyznaczanie najkrótszej ścieżki w grafie, okazują się skuteczne i bardzo szybkie. Kluczem do ich stosowania jest możliwość wykazania, że lokalne decyzje prowadzą do optymalnego globalnego wyniku, co nie zawsze jest możliwe.

Przykładami zastosowania podejścia zachłannego są takie algorytmy, jak m.in.:

• algorytm Dijkstry – służący do znajdowania najkrótszych ścieżek w grafach,
• metoda Kruskala – używana do wyznaczania minimalnego drzewa rozpinającego,
• konstrukcja drzewa kodowego Huffmana służącego do kompresji danych,
• algorytmy szeregowania zadań.

Algorytmy z powrotami

Technika z powrotami, znana także jako backtracking, wykorzystywana jest w problemach, gdzie konieczne jest przeszukiwanie dużych przestrzeni rozwiązań. Polega ona na budowaniu rozwiązania krok po kroku i wycofywaniu się z błędnych ścieżek, gdy okaże się, że nie prowadzą do celu. Tę metodę stosuje się często w zagadkach logicznych, takich jak sudoku, układanie hetmanów na szachownicy czy generowanie kombinacji i permutacji. Choć jej czas działania może być wykładniczy, jest niezwykle uniwersalna i stosunkowo prosta do zaimplementowania.

Istnieje wiele różnych zagadnień, do rozwiązania których stosuje się algorytmy z powrotami, m.in.:

• problem „plecakowy” (optymalnego wyboru),
• grupa problemów dotyczących gier (w szachach, warcabach), np.:
  • problem rozmieszczenia n-królowych na szachownicy (znany najczęściej w wersji z 8 hetmanami (królowymi) ),
  • problem znalezienia drogi konika szachowego (odwiedzenie każdego pola szachownicy dokładnie raz) – Knight’s Tour.
• problemy „grafowe”, np.:
  • problem kolorowania grafu (należy w taki sposób użyć m kolorów, by każde dwa sąsiednie węzły były różnego koloru.

Metody heurystyczne

Metody heurystyczne to podejście stosowane w sytuacjach, gdzie rozwiązanie optymalne jest trudne lub niemożliwe do znalezienia w rozsądnym czasie. Heurystyki nie gwarantują najlepszego możliwego wyniku, ale dostarczają rozwiązań wystarczająco dobrych w praktyce. Stosuje się je w problemach NP-trudnych, takich jak komiwojażer czy optymalizacja tras. Do metod heurystycznych należą między innymi algorytmy genetyczne, symulowane wyżarzanie czy lokalne przeszukiwanie. Ich zaletą jest elastyczność i możliwość adaptacji do wielu różnych dziedzin.

Metodami heurystycznymi posługujemy się najczęściej w problemach, gdy brakuje nam pewnych danych, dzięki którym bylibyśmy w stanie znaleźć rozwiązanie przy użyciu klasycznych algorytmów.

Przykładami takich problemów są chociażby:

• prognozowanie pogody,
• wykrywanie wirusów i robaków internetowych.

Algorytmy probabilistyczne

Algorytmy probabilistyczne to klasa algorytmów, które wykorzystują element losowości w swoim działaniu. Mogą podejmować decyzje w sposób losowy lub korzystać z losowych danych pomocniczych. Ich wynik lub czas działania nie zawsze jest taki sam przy każdym uruchomieniu, nawet dla tych samych danych wejściowych.

Przykłady zastosowań:

• Testy pierwszości liczb (Miller–Rabin, Fermata) ,
• Algorytmy w kryptografii (np. generowanie kluczy, testy losowości),
• Symulacje fizyczne i finansowe (metody Monte Carlo),
• Grafika komputerowa (np. rozpraszanie światła, wygładzanie krawędzi),
• Algorytmy na grafach (np. randomizowane wyszukiwanie cykli), 
• Optymalizacja (np. symulowane wyżarzanie – wykorzystuje probabilistyczne przejścia).

Algorytmy iteracyjne

Algorytmy iteracyjne (np. gradientowe) stanowią klasę metod, które rozwiązują problemy poprzez sukcesywne przybliżanie rozwiązania. W przeciwieństwie do innej klasy algorytmów nie dzielą problemu na mniejsze podproblemy, tylko rozpoczynają od pewnego stanu początkowego, a następnie modyfikują go krok po kroku, aż osiągną wynik spełniający określone kryterium zbieżności lub dokładności. Charakterystyczne dla tego podejścia jest użycie pętli, w których każda iteracja przybliża rozwiązanie coraz bardziej do wartości optymalnej. Algorytmy tego typu są powszechnie stosowane w optymalizacji matematycznej, analizie numerycznej i uczeniu maszynowym, gdzie często nie da się wyznaczyć dokładnego wyniku analitycznie. Dobrym przykładem jest metoda spadku gradientowego (ang. gradient descent), która znajduje minimum funkcji poprzez poruszanie się w kierunku przeciwnym do gradientu. Algorytmy iteracyjne mogą działać zarówno na liczbach rzeczywistych, jak i dyskretnych strukturach danych, a ich główną zaletą jest możliwość szybkiego uzyskania przybliżonego rozwiązania nawet dla bardzo dużych i złożonych problemów. W praktyce często łączy się je z innymi technikami, takimi jak heurystyki czy metody probabilistyczne, w celu zwiększenia skuteczności i stabilności.

Algorytmy przeszukiwania

Algorytmy przeszukiwania (ang. search-based algorithms) to grupa algorytmów, które rozwiązują problemy poprzez systematyczne eksplorowanie przestrzeni możliwych rozwiązań. Zamiast budować wynik wprost, analizują możliwe stany lub konfiguracje problemu i wybierają ścieżki prowadzące do rozwiązania na podstawie określonej strategii przeszukiwania. Przestrzeń rozwiązań może być reprezentowana jako drzewo lub graf, w którym węzły odpowiadają stanom, a krawędzie – możliwym przejściom między nimi. Algorytmy te są szczególnie istotne w sztucznej inteligencji, teorii gier, grafach oraz planowaniu działań i tras. Podstawowe techniki przeszukiwania to przeszukiwanie wszerz (ang. BFS – Breadth-First Search) i przeszukiwanie w głąb (ang. DFS – Depth-First Search). Algorytmy te różnią się kolejnością eksplorowania węzłów i mają odmienne właściwości dotyczące kompletności, optymalności i zużycia pamięci. W bardziej zaawansowanych zastosowaniach wykorzystuje się przeszukiwanie z heurystyką, takie jak algorytm A*, który łączy rzeczywisty koszt przebytej drogi z oszacowaniem odległości do celu, co pozwala znacząco przyspieszyć proces rozwiązywania. Inne znane metody to przeszukiwanie iteracyjno-głębokie, przeszukiwanie z kosztem jednolitym czy przeszukiwanie bidirectionalne. Algorytmy przeszukiwania mogą być zarówno deterministyczne, jak i probabilistyczne, zależnie od rodzaju problemu i użytych technik pomocniczych. W przypadku dużych lub nieskończonych przestrzeni stanów, stosuje się ograniczenia głębokości, przeszukiwanie heurystyczne lub losowe eksplorowanie węzłów. Choć nie zawsze prowadzą do rozwiązania optymalnego, często pozwalają znaleźć zadowalające odpowiedzi w akceptowalnym czasie. Ich siłą jest uniwersalność – mogą być stosowane do szerokiego zakresu problemów: od rozwiązywania łamigłówek, przez sterowanie robotami, aż po analizę struktur danych i sieci komputerowych.