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

f

A

(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

_

c,N ­0

^

n­N

0 ¬ f (n) ¬ c · g(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(n

2

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

n

), O(n

log 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 ⊂ N P , 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 (N P − trudne ⊂ N P , ale P ∩ N P − 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: Łą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(n

3

),

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

3

). 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