Politechnika Wrocławska
Wydział Elektroniki
Kierunek Automatyka i Robotyka
Zasady projektowania algorytmów
Autor:
Tomasz PÅ‚atek
Nr albumu: 163056
[e-mail]
ProwadzÄ…cy:
3 stycznia 2011
Wrocław
1 Definicja algorytmu
Algorytm (nieformalnie) jest pewną ściśle określonoą procedurą obliczeniową, która dla
właściwych danych wejściowych  produkuje żądane dane wyjściowe zwane wynikiem
działania algorytmu.
Algorytm jest więc ciągiem kroków obliczeniowych prowadzących do przekształcenia
danych wejściowych w wyjściowe.
2 Złożoność obliczeniowa
Funkcja złożoności obliczeniowej algorytmu A wyraża się wzorem
fA(N(I)) = max {t},
gdzie t jest to ilość operacji (jednostek czasu) potrzebnych do rozwiązania dowolnej
instancji I problemu o rozmiarze N(I) przez algorytm A.
Notacja O: mówimy, że funkcja f(n) jest rzędu O(g(n)) jeśli

0 f(n) c · g(n),
c,N 0 n N
co oznacza, że dla n " funkcje f(n) oraz g(n) zachowują się podobnie.
3 Rodzaje algorytmów ze względu na złożoność ob-
liczeniowÄ…
" Algorytmy 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 roz-
miaru problemu n, np. O(n), O(n2), O(n log n) (algorytmy efektywne obliczenio-
wo).
" Algorytmy wykładnicze (ponadwielomianowe) - algorytmy, których funkcji zło-
żoności obliczeniowej f(n) nie da się ograniczyć żadnym wielomianem p(n), np.
O(2n), O(nlog n), O(n!) (algorytmy nieefektywne obliczeniowo).
4 Klasy złożoności algorytmów:
" klasa P - zawiera wszystkie problemy, dla których skonstruowano wielomianowe
algorytmy optymalne,
" klasa NP - zawiera wszystkie problemy, dla których skonstruowano wykładnicze
algorytmy optymalne ( P ‚" NP , ponieważ jeżli dla pewnego problemu mamy alg.
wielomianowy, zawsze możemy skonstruować alg. mniej efektywny (wykładniczy),
np. przegląd zupełny),
" klasa problemów NP-trudnych - podklasa NP problemów wielomianowo ekwiwa-
lentnych, dla których (najprawdopodobniej) nie można skonstruować algorytmów
wielomianowych (NP - trudne ‚" NP , ale P )" NP - trudne = Ø),
" klasa problemów silnie NP-trudnych - podklasa problemów NP-trudnych, których
nie można rozwiązać optymalnie w czasie pseudowielomianowym.
1
5 Zasady projektowania algorytmów
Dokładne określenie przynależności danego problemu do klasy złożoności pozwala skon-
struować najodpowiedniejsze algorytmy jego rozwiązania.
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),
" Metoda podziału i ograniczeń - głównie dla problemów (silnie) NPtrudnych.
" Przegląd zupełny.
Rodzaje algorytmów (metod) przybliżonych:
" algorytmy konstrukcyjne i zachłanne - głównie dla problemów NPtrudnych,
" algorytmy typu popraw - głównie dla problemów (silnie) NP-trudnych:
 lokalnego poszukiwania (np. poszukiwanie zstępujące, poszukiwanie losowe),
 metaheurystyczne (np. poszukiwanie z zabronieniami (tabu search), symulo-
wane wyżarzanie, poszukiwanie genetyczne (ewolucyjne), poszukiwanie mrów-
kowe).
" wielomianowe i w pełni wielomianowe schematy aproksymacyjne - głównie dla
problemów NP-trudnych.
6 Metoda  dziel i zwyciężaj
W metodzie  dziel i zwyciężaj problem dzielony jest na kilka mniejszych podproble-
mów podobnych do początkowego problemu, problemy te rozwiązywane są rekurencyj-
nie, a następnie rozwiązania wszystkich podproblemów są łączone w celu utworzenia
rozwiązania całego probemu.
W podejściu  dziel i zwyciężaj każdy poziom rekursji składa się z następujących
trzech etapów:
" Dziel: Dzielimy problem na podproblemy,
" Zwyciężaj: Rozwiązujemy podproblemy rekurencyjnie, chyba że są one małego
rozmiaru i już nie wymagają zastosowania reukursji - używamy wtedy bezpo-
średnich metod,
" Połącz: A
ączymy rozwiązania podproblemów, aby otrzymać rozwiązanie całego
problemu.
Przykładowe algorytmy:
" sortowanie przez scalanie,
" sortowanie szybkie (quicksort),
" wyszukiwanie binarne,
" szybka transformacja Fouriera.
2
7 Metoda  transformuj i zwyciężaj
Algorytmy bazujące na tej metodzie składają się z dwóch głównych kroków:
" krok transformacji: instancja problemu jest modyfikowana do postaci odpowied-
niejszej do rozwiÄ…zywania,
" krok zwyciężania: przetransformowany problem jest rozwiązywany znaną metodą.
Głównymi sposobami transformacji są:
" uproszczenie instancji (transformacja do prostrzej instancji tego samego proble-
mu),
" zmiana sposobu reprezentacji (transformacja tej samej instancji to innej repre-
zentacji),
" redukcja problemu (transformacja do instancji innego problemu, który jesteśmy
w stanie rozwiązać).
Uproszczenie instancji może być wykonane następującymi sposobami:
" sortowanie wstępne (ang. presorting) - posortowane dane upraszczają m.in. zada-
nie szukania zadanego elementu, zadanie sprawdzenia czy wśród danych znajdują
siÄ™ duplikaty, wyznaczanie dominanty zbioru danych.
" eliminacja Gaussa - przekształcenie macierzy współczynników w macierz trójkat-
ną pozwala na zmniejszenie złożoności obliczeniowej do O(n3),
Zmiana sposobu reprezentacji jest wykorzystywana podczas przekształcenia tablicy
do binarnego drzewa poszukiwań: pozwala to na zredukowanie złożoności obliczeniowej
wyszukiwania elementu do O(n3). Podobnym przekształceniem jest kopcowanie.
Redukcja problemu wykorzystywana jest np. w sytuacji gdy interesujÄ…cy nas pro-
blem transformujemy do problemu poszukiwania najkrótszej ścierzki w grafie, a na-
stępnie do rozwiązania tego problemu stosujemy znane algorytmy (Djikstry, Bellmana-
Forda). Innym przykładem jest transformacja do problemu programowania liniowego.
8 Algorytmy siłowe
Jest to najprostrza strategia projektowania algorytmów, często bazująca na przeglą-
dzie zupełnym lub wprost na twierdzeniach i definicjach opisujących problem. Jest
też najprostrza w zastosowaniu, lecz pociąga to za sobą niska wydajność (często nie
pozwalajÄ…cÄ… na rozwiÄ…zanie problemu w rozsÄ…dnym czasie).
9 Algorytmy z nawrotami (backtracking)
W metodzie tej wykorzystujemy własności zadania, aby ograniczyć przeszukiwaną prze-
strzeń. Algorytmy te stopniowo generują kandydatów rozwiązania. Jeżeli wygenero-
wany kandydat nie może byc roziwązaniem (nie spełnia warunków zadania) jest on
opuszczny (dalsze generowanie kandydatów rozwiązania na jego podstawie jest przery-
wane), a następnie wraca się do poprzedniego kandydata.
3
Przykładem takiego algorytmu jest algorytm rozwiązujący problem rozstawienia
hetmanów na szachownicy. Problem polega na rozstawieniu n hetmanów na szachow-
nicy n na n w taki sposób, by się nawzajem nie atakowały. Algorytm próbuje ustawiac
hetmany w kolejnych kolumnach poczawszy od pierwszej kolumny (oczywiscie w każdej
kolumnie ustawia tylko jednego hetmana). W każdej z kolumn szuka pierwszego pola
(poczawszy od dolnego), na którym postawienie hetmana nie koliduje z hetmanami z
wczesniejszych kolumn. Jesli takie pole istnieje, ustawia na nim hetmana i przechodzi
do kolejnej kolumny. Jesli nie istnieje - algorytm powraca do poprzedniej kolumny i
próbuje przestawic hetmana na kolejne nie kolidujace pole.
10 Programowanie dynamiczne
StosujÄ…c programowanie dynamiczne, podobnie jak przy korzystaniu z metody  dziel i
zwyciężaj , rozwiązujemy problemy przez odpowiednie złożenie rozwiązań podproble-
mów. Programowanie dynamiczne można stosować wtedy, kiedy podproblemy nie są
niezależne, tzn. kiedy podproblemy mogą zawierać te same podpodproblemy. Wtedy
algorytm typu  dziel i zwyciężaj wykonuje więcej pracy niż to w istocie koniecz-
ne, wielokrotnie bowiem rozwiÄ…zuje ten sam podproblem. W algorytmie opartym na
programowaniu dynamicznym rozwiązuje się każdy podproblem tylko raz, po czym
zapamiętuje się wynik w odpowiedniej tabeli, unikając w ten sposób wielokrotynych
obliczeń dla tego samego podproblemu.
Programowanie dynamiczne jest zwykle stosowane do problemów optymalizacyj-
nych. W tego typu zagadnieniach możliwych jest wiele różnych rozwiązań. Z każdym
rozwiÄ…zaniem jest zwiÄ…zana pewna liczba (koszt). RozwiÄ…zanie optymalne to takie,
które ma optymalny (minimalny lub maksymalny) koszt. Może być wiele rozwiązań
optymalnych, wszystkie o tym samym optymalnym koszcie.
Proces projektowania algorytmu opartego na programowaniu dynamicznym można
podzielić na cztery etapy:
" scharakteryzowanie struktury optymalnego rozwiÄ…zania,
" rekurencyjne zdefiniowanie kosztu optymalnego rozwiÄ…zania,
" obliczanie optymalnego kosztu metodą wstępującą (czyli rozpoczynając od naj-
mniejszych podproblemów, rozwiązywać coraz większe, wykorzystując rozwiąza-
nia mniejszych),
" konstruowanie optymalnego rozwiązania na podstawie wyników wcześniejszych
obliczeń.
Etapy 1-4 stanowiÄ… trzon rozwiÄ…zywania problemu za pomocÄ… programowania dy-
namicznego. Jeśli interesuje nas tylko koszt rozwiązania optymalnego, to etap 3 można
pominąć. Jeśli mimo wszystko wykonujemy etap 4, to często wygodnie jest zapamięty-
wać dodatkowe informacje w etapie 3, co niejednokrotnie znacznie ułatwia zrekonstru-
owanie optymalnego rozwiÄ…zania.
Przykładowe algorytmy:
" mnożenie ciągu macierzy,
" najdłuższy wspólny pociąg,
" optymalna triangulacja wielokÄ…ta.
4
11 Branch and bound  algorytm podziału i ogra-
niczeń
Dzielimy problem na podproblemy (branching), a następnie obliczamy górne i dolne
ograniczenia (bounding) i  obcinamy (pruning) niektóre gałęzie drzewa przeszukiwań.
Dla problemu maksymalizacji: jeśli dla danego poddrzewa T jego górne ograniczenie
(upper bound) jest mniejsze od dolnego ograniczenia (lower bound) dowolnego innego
poddrzewa, to nie ma sensu testować rozwiązań w T.
12 Algorytmy zachłanne
Algorytm zachłanny wykonuje zawsze działanie, które wydaje się w danej chwili naj-
korzystniejsze. Wybiera zatem lokalnie optymalną możliwość w nadziei, że doprowadzi
ona do globalnie optymalnego rozwiązania. Algorytmy zachłanne nie zawsze prowadzą
do optymalnych rozwiązań, choć dla wielu problemów są wystarczające.
Przykładowe algorytmy:
" wyznaczanie minimalnego drzewa rozpinajÄ…cego,
" algorytm Dijkstry,
" algorytm Chvatla dla problemu pokrycia zbioru.
5