Projektowanie
algorytmów
Problem
Problem  jest to zbiór danych wejściowych i ich definicja oraz pytanie lub
polecenie do wykonania. Najczęściej problem oznaczamy symbolem Ą.
Przykłady problemów optymalizacji kombinatorycznej:
" Problem komiwojażera
" Problem plecakowy
" Problem szeregowania zadao
" Problem podziału zbioru
Algorytm
Algorytm- jest to procedura (krok po kroku) działająca w skooczonym czasie,
rozwiÄ…zujÄ…ca dany problem Ä„.
Rodzaje algorytmów ze względu na złożonośd obliczeniową:
" Wielomianowe - algorytmy, których funkcja złożoności obliczeniowej f(n)
jest rzędu O(p(n)), gdzie p(n) jest pewnym wielomianem zależnym od
rozmiaru problemu n, np. O(n), O(n2), O(n log n) (algorytmy efektywne
obliczeniowo).
" wykładnicze (ponadwielomianowe) - algorytmy, których funkcji złożoności
obliczeniowej f(n) nie da się ograniczyd żadnym wielomianem p(n), np.
O(2n), O(nlog n), O(n!) (algorytmy nieefektywne obliczeniowo).
Klasy złożoności algorytmów
1. Klasa P - zawiera wszystkie problemy, dla których skonstruowano
wielomianowe algorytmy optymalne.
2. Klasa NP - zawiera wszystkie problemy, dla których skonstruowano
wykÅ‚adnicze algorytmy optymalne. P ‚" NP, ponieważ jeżeli dla pewnego
problemu mamy alg. wielomianowy, zawsze możemy skonstruowad alg.
mniej efektywny (wykładni-czy), np. przegląd zupełny.
3. Klasa problemów NP-trudnych - podklasa NP problemów
wielomianowo ekwiwalentnych, dla których (najprawdopodobniej) nie
można skonstruowad algorytmów wielomianowych. NP-trudne‚"NP, ale
P )"NP-trudne=".
4. Klasa problemów silnie NP-trudnych - podklasa problemów
NP-trudnych, których nie można rozwiązad optymalnie w czasie pseudo-
wielomianowym.
W praktyce:
" 9% istniejących problemów należy do klasy P
" 84% należy do klasy problemów NP-trudnych, z czego 79%
należy do klasy problemów silnie NP-trudnych
" 7% to problemy otwarte
Rodzaje algorytmów (metod)
optymalnych:
" Wielomianowe algorytmy dokładne (dedykowane) - tylko dla
problemów z klasy P
" Programowanie dynamiczne - głównie dla problemów
NP-trudnych w zwykłym sensie (tzn. nie silnie NP-trudnych)
" Programowanie całkowitoliczbowe
" Metoda podziału i ograniczeo - głównie dla problemów (silnie)
NP-trudnych
" Przegląd zupełny
Programowanie dynamiczne
Programowanie dynamiczne opiera siÄ™ na podziale
rozwiązywanego problemu na podproblemy względem kilku
parametrów. W odróżnieniu od techniki dziel i zwyciężaj
podproblemy w programowaniu dynamicznym nie są na ogół
rozłączne, ale musi je cechowad własnośd optymalnej
podstruktury. Zagadnienia odpowiednie dla programowania
dynamicznego cechuje również to, że zastosowanie do nich
metody siłowej (ang. brute force) prowadzi do
ponadwielomianowej liczby rozwiązao podproblemów,
podczas gdy sama liczba różnych podproblemów jest
wielomianowa.
Algorytm przybliżony
algorytm dostarczajÄ…cy rozwiÄ…zanie nieoptymalne dla danego
problemu optymalizacyjnego.
Algorytmy przybliżone są stosowane wtedy, gdy nie potrafimy
znalez
d rozwiÄ…zania optymalnego w sensownym czasie.
Do oceny algorytmów przybliżonych stosujemy następujące
podejścia:
" analiza eksperymentalna
" analiza najgorszego przypadku
" analiza probabilistyczna
Rodzaje algorytmów (metod)
przybliżonych:
" Algorytmy konstrukcyjne i zachłanne - głównie dla problemów
NP-trudnych.
" Algorytmy typu popraw - głównie dla problemów (silnie)
NP-trudnych:
o lokalnego poszukiwania (np. poszukiwanie zstępujące,
poszukiwanie losowe),
o metaheurystyczne (np. poszukiwanie z zabronieniami
(tabu se-arch), symulowane wyżarzanie, poszukiwanie
genetyczne (ewolucyjne), poszukiwanie mrówkowe).
" Wielomianowe i w pełni wielomianowe schematy
aproksymacyjne - głównie dla problemów NP-trudnych.
Algorytmy zachłanne
Algorytm zachłanny w celu wyznaczenia rozwiązania w każdym
kroku dokonuje zachłannego, tj. najlepiej rokującego w danym
momencie wyboru rozwiązania częściowego. Innymi słowy
algorytm zachłanny nie patrzy czy w kolejnych krokach jest
sens wykonywad dane działanie, dokonuje decyzji lokalnie
optymalnej, dokonuje on wyboru wydajÄ…cego siÄ™ w danej
chwili najlepszym, kontynuujÄ…c rozwiÄ…zanie podproblemu
wynikającego z podjętej decyzji. Typowe zadanie
rozwiązywane metodą zachłanną ma charakter
optymalizacyjny.
Algorytmy heurystyczne
Metody znajdowania rozwiązao, dla której nie ma gwarancji znalezienia
rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązao tych
używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt
kosztowny, lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy
wykrywaniu niektórych zagrożeo komputerowych, takich jak wirusy lub
robaki). Metody używa się też często do znajdowania rozwiązao
przybliżonych, na podstawie których póz
niej wylicza siÄ™ ostateczny rezultat
pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy
przypadków, gdy heurystyka jest wykorzystywana do nakierowywania
pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyd czas
działania programu w typowym przypadku bez poświęcania jakości
rozwiÄ…zania
Schematy aproksymacyjne
rodzina algorytmów taka, że dostarcza rozwiązanie problemu z błędem
nie większym niż ustalony
" Wielomianowe schematy aproksymacyjne: czas działania
algorytmu jest ograniczony od góry przez wielomian od
rozmiaru instancji N(I) oraz funkcję wykładniczą od
odwrotności błędu (PTAS)
" W pełni wielomianowe schematy aproksymacyjne: czas
działania algorytmu jest ograniczony od góry przez wielomian
od rozmiaru instancji N(I) oraz wielomian od odwrotności
błędu (FPTAS)