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(2

n

), O(n

log 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

znaleź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óź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)