poprawa
ZA
OŻONOŚĆ PROBLEMÓW ALGORYTMICZNYCH
Algorytm dla problemu P
o złożoności O(N 3)
Górne oszacowania dla
Dolne i górne oszacowania złożoności problemu
złożoności problemu P
poprawa
Algorytm dla problemu P
Złożoność każdego poprawnego algorytmu znajdującego
o złożoności O(N 2)
rozwiązanie danego problemu ustanawia górne oszacowanie
Algorytm najlepszy z
Złożoność czasowa
~
możliwych ma złożoność
złożoności dla tego problemu.
właściwa problemowi P (?)
równą złożoności problemu
Czy można skonstruować algorytm o niższej złożoności?
Dowód, że każdy algorytm
będący rozwiązaniem
problemu P ma złożoność
Jeśli się uda, to górne oszacowanie złożoności problemu
co najmniej Ś(N�"lg N)
Ś
Ś
Ś
zostaje poprawione.
Dolne oszacowania dla
uściślenie
złożoności problemu P
Dolne oszacowanie złożoności problemu (otrzymane w wyniku
Dowód, że każdy algorytm
analizy samego problemu) określa zakres dalszej poprawy będący rozwiązaniem
problemu P ma złożoność
rzędu złożoności algorytmów rozwiązujących ten problem.
co najmniej Ś(N)
Ś
Ś
Ś
uściślenie
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 1 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 2
Problemy zamknięte i luki algorytmiczne
dolne górne
problem
oszacowanie oszacowanie
Jeśli dysponujemy dla danego problemu algorytmem
o złożoności O(g(N)), to możemy powiedzieć, że złożoność Wyszukiwanie
Ś(N) O(N)
Ś
Ś
Ś
problemu wynosi O(g(N)), bo na pewno nie jest wyższego z listy nieuporządkowanej
rzędu niż g(N)  algorytm daje górne oszacowanie, a notacja
Wyszukiwanie
Ś(lgN) O(lgN)
Ś
Ś
Ś
O(�") ma dokładnie taki sam sens oszacowania od góry.
z listy uporządkowanej
Jeśli górne i dolne oszacowania złożoności problemu Sortowanie
Ś(N�"lgN) O(N�"lgN)
Ś
Ś
Ś
algorytmicznego spotkają się w klasie złożoności tego samego (bez ograniczania wartości)
rzędu, to możemy stwierdzić, że złożoność problemu wynosi
Wyznaczanie  najkrótszej
Ś(N) O(s(N)�"N) 1)
Ś
Ś
Ś
dokładnie Ś(g(N)) i taki problem nazywamy zamkniętym
sieci kolejowej
(z punktu widzenia określania jego złożoności).
1)
s(N) - bardzo wolno rosnąca funkcja, np. dla N = 64 000 ma wartość 4
Jeśli dla problemu algorytmicznego najlepsze znane górne i
Wyszukiwanie z listy, sortowanie  problemy zamknięte
dolne oszacowania różnią się rzędem złożoności, to taką
Wyznaczanie  najkrótszej sieci kolejowej  luka algorytmiczna
sytuację nazywamy luką algorytmiczną.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 3 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 4
Przykład  problem wież Hanoi Przykład  problem ułożenia płaskiej układanki
Problem jest zamknięty
Algorytm ma rozstrzygać,
(dolne ograniczenie złożoności = złożoność algorytmu
czy istnieje takie ułożenie
rekurencyjnego lub iteracyjnego) i ma złożoność Ś(2N).
Ś
Ś
Ś
kwadratu M x M
2
z N = M kafelków,
Podobno mnisi tybetańscy rozwiązują ten problem w pewnym
które zachowuje zgodność
klasztorze dla N = 64 i kiedy skończą, to także nasz świat się
kolorów na przyległych
skończy!
bokach?
1 ruch na sekundę �! czas wykonania ok. 586 146 828 647 lat
Zakładamy, że kafelków nie można obracać
1 mln ruchów na sekundę �! czas wykonania ok. 586 147 lat
Jest to przykład tzw. problemu decyzyjnego  problemu
algorytmicznego, który polega na znalezieniu prawidłowej
264 = 18 446 744 073 709 551 616
odpowiedzi  tak lub  nie na postawione pytanie
(często jest to pytanie o istnienie rozwiązania problemu)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 5 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 6
1
Wartości wybranych funkcji złożoności
W problemie ułożenia płaskiej układanki występuje
luka algorytmiczna, a górne oszacowanie jego złożoności
N
Funkcja
jest rzędu O(N!),
10 50 100 300 1000
lg N 3 5 6 8 9
bo nie wymyślono lepszego algorytmu, jak tylko przeglądanie
N 10 50 100 300 1000
wszystkich możliwych ułożeń, których jest właśnie N!
N " lg N 33 282 664 2468 9965
"
"
"
Dla układanki 5 x 5 oznacza to: 2
N 100 2500 10 000 90 000 1 000 000
27 mln 1 mld
3
1 mln układów na sekundę �! czas sprawdzenia wynosi N 1000 125 000 1 000 000
(8 cyfr) (10 cyfr)
ok. 492 869 990 446 lat
Liczba Liczba Liczba Liczba
2N 1024
16 cyfrowa 31 cyfrowa 91 cyfrowa 302 cyfrowa
25! = 15 511 210 043 330 985 984 000 000
3,6 mln Liczba Liczba Liczba
N! "
"
"
"
(7 cyfr) 65 cyfrowa 161 cyfrowa 623 cyfrowa
10 mld
Liczba Liczba Liczba
N
N "
"
"
"
85 cyfrowa 201 cyfrowa 744 cyfrowa
(11 cyfr)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 7 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 8
Tempo wzrostu
Dla porównania:
wybranych
liczba protonów w widocznym wszechświecie ma 126 cyfr,
funkcji złożoności
liczba mikrosekund od  wielkiego wybuchu ma 24 cyfry.
Zapotrzebowanie na czas
(jeśli wykonanie jednej operacji trwa mikrosekundę)
N
Funkcja
10 20 50 100 300
1/10 000 1/2500 1/400 1/100 9/100
2
N
sek. sek. sek. sek. sek.
1/1000 1 35,7 400 bilionów 75 cyfrowa
N
2
sek. sek. lat stuleci liczba stuleci
2,8 3,3 70 cyfrowa 185 cyfrowa 728 cyfrowa
N
N
godziny biliona lat liczba stuleci liczba stuleci liczba stuleci
(skala logarytmiczna)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 9 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 10
Funkcja f (N) jest (asymptotycznie) ograniczona z góry
Dwie z klas problemów algorytmicznych:
przez funkcję g(N), jeśli " N0 i C " N e" N0 : f(N) d" C�"g(N)
?
Nie ma dla nich
Jeśli f (N) g(N) , to f (N) jest ograniczona z góry przez g(N)
p
algorytmów
wielomianowych,
Funkcje złożoności dzielimy generalnie na:
są tylko
PROBLEMY TRUDNO
wielomianowe, dla których istnieje takie k < ", że są one ponadwielomianowe
"
"
"
ROZWI
ZYWALNE
k
ograniczone z góry przez funkcję N ,
PROBLEMY A
ATWO
ponadwielomianowe, dla których takie k nie istnieje (np. 2N).
Znane są dla nich
ROZWI
ZYWALNE
algorytmy
Sortowanie
N
2 3 lgN N
wielomianowe
1 lglgN lgN N N�" N N N 2N N! N
�"lgN
�"
�"
p p p Np p p p p p p p p 22
wielomianowe ponadwielom.
k
Algorytm wielomianowy, to algorytm o złożoności O(N ) dla k < "
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 11 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 12
2
Jak sobie poradzić z problemem płaskiej układanki?
Rozważmy 1. propozycję:
1. Może po prostu poczekać na zbudowanie dostatecznie
szybkiego komputera?
Maksymalny rozmiar zadania, które dla którego można
znalez
ć rozwiązanie w godzinę
Funkcja
2. Może brak algorytmu wielomianowego dla tego problemu
złożoności
wynika z braku wiedzy i inwencji u informatyków? Najszybszy współ- Komputer Komputer
czesny komputer 100 razy szybszy 1000 razy szybszy
3. Może udało by się wykazać, że dolne oszacowanie
2
N K 10 " K 31,6 " K
złożoności dla tego problemu jest wykładnicze i stwierdzić,
że problem jest za trudny?
2N L L + 6 L + 10
4. Może jest on tak szczególnym przypadkiem, że można go
pominąć, bo wszystkie ważne problemy są łatwo
rozwiązywalne?
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 13 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 14
Rozważmy 4. propozycję: Zatem dla problemu płaskiej układanki i pozostałych
1000 problemów NPC nie wiadomo nawet czy są to
Układanie płaskiej układanki należy do klasy problemów NPC
problemy trudno, czy łatwo rozwiązywalne!
(NP-zupełnych), która obejmuje ponad 1000 problemów
algorytmicznych o jednakowych cechach:
W wielu dziedzinach zastosowań informatyki wciąż formułowane
są nowe problemy, które okazują się problemami NPC.
dla wszystkich tych problemów istnieją ponadwielomianowe
algorytmy
Przykłady problemów algorytmicznych z klasy NPC (NP-zupełnych)
dla żadnego jak dotąd nie znaleziono algorytmu wielomianowego,
czyli górne oszacowanie złożoności jest ponadwielomianowe Inne płaskie układanki
(wykładnicze)
dla żadnego nie udowodniono, że nie może istnieć dla niego
algorytm wielomianowy
najlepsze wyznaczone dolne oszacowania złożoności są liniowe,
tzn. Ś(N)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 15 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 16
Problem komiwojażera
W wersji decyzyjnej problem komiwojażera polega
Problem polega na znajdowaniu w sieci połączeń pomiędzy
na stwierdzaniu czy istnieje cykl o długości nie większej
miastami najkrótszej drogi zamkniętej (cyklu), która pozwala
niż podana wartość L.
odwiedzić każde z miast i powrócić do miasta wyjściowego.
Algorytmy rozwiązywania problemu komiwojażera mają
6
6
duże znaczenie np. przy:
Sieć z Minimalny
3
3
4
4
8
8
9
9
podanymi cykl projektowaniu sieci telekomunikacyjnych,
długościami o długości
3
3 projektowaniu układów scalonych,
połączeń 28
10
10 planowaniu linii montażowych,
7 5
7 5
programowaniu robotów przemysłowych .
7
7
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 17 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 18
3
Problem wyznaczania drogi Hamiltona
Problemy przydziału i układania harmonogramu
Problem polega na sprawdzaniu, czy w grafie istnieje droga,
która przez każdy wierzchołek przechodzi dokładnie raz. Na przykład:
Należy przydzielić prace do wykonania pracownikom z
uwzględnieniem różnych ograniczeń
Należy wypełnić kontenery pojemnikami o różnych
rozmiarach
Należy ułożyć plan zajęć dopasowujący nauczycieli, klasy i
godziny lekcyjne w taki sposób, aby dwie klasy nie miały
jednocześnie zajęć z tym samym nauczycielem, nauczyciel
nie prowadził w tym samym czasie lekcji w dwóch różnych
klasach, dwaj nauczyciele nie prowadzili jednocześnie lekcji
w tej samej klasie itd.
W tym grafie nie istnieje, ale po uzupełnieniu grafu jedną
krawędzią można ją wyznaczyć
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 19 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 20
Problem spełnialności zdania logicznego Kolorowanie mapy płaskiej 3 kolorami lub szukanie
tzw. liczby chromatycznej grafu
Problem polega na algorytmicznym rozstrzyganiu, czy istnieje
zestaw takich prostych zdań logicznych o określonych wartościach
Problem polega na algorytmicznym rozstrzyganiu, czy podana
prawda lub fałsz, które wstawione do podanego złożonego zdania
mapa może być pokolorowana 3 kolorami tak, aby sąsiednie
logicznego, spowodują, że całe to zdanie stanie się prawdziwe.
obszary nie miały tego samego koloru.
Np. zdanie
1
dla 2 kolorów problem jest łatwo 5
Ź(E �! F) '" (F (" (D �! E))
2
rozwiązywalny - wystarczy sprawdzić,
będzie prawdziwe po wstawieniu zdań o następujących wartościach
czy mapa nie zawiera punktów, w których
4
3
styka się nieparzysta liczba obszarów, np.
E �! PRAWDA, F �! FAA
SZ, D �! FAA
SZ
i zatem jest spełnialne. dla 4 kolorów problem jest banalny, bo udowodniono
A zdanie
twierdzenie o czterech kolorach.
Ź((D '" E) �! F ) '" (F (" (D �! ŹE))
nie jest spełnialne.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 21 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 22
Problem załadunku plecaka
Problem polega na algorytmicznym znajdowaniu najmniejszej
liczby kolorów, którymi można pokolorować wierzchołki Problem polega na algorytmicznym wyznaczaniu takiego upakowania
podanego grafu tak, aby każde dwa wierzchołki bezpośrednio podanych przedmiotów do plecaka, aby łączna ich wartość była
połączone krawędzią miały różne kolory. maksymalna, ale nie została przekroczona pojemności plecaka.
A
atwo można skonstruować graf wymagający dowolnie dużej Dane wejściowe: dla ponumerowanych przedmiotów 1, 2, ..., N
liczby kolorów: są podane ich wartości c1, c2, ..., cN i objętości a1, a2, ..., aN oraz
N
podana jest objętość plecaka b i zachodzi
b <
"a
i
i=1,...,N
Klika - zbiór
Należy wyznaczyć wartość zmiennych decyzyjnych x1, x2, ..., xN ,
wierzchołków
dla kórych xi = 1 oznacza  zapakowanie przedmiotu o numerze i ,
w grafie
a xi = 0 pominięcie tego przedmiotu, tak aby były spełnione
połączonych
warunki:
krawędziami N N
max �" xi i �" xi d" b
"c "a
każdy z każdym i i
i=1,...,N i=1,...,N
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 23 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 24
4
W wersji decyzyjnej problem polega na rozstrzyganiu,
czy dla podanej wartości T istnieje takie upakowanie plecaka,
N N
w którym:
"c �" xi e" T i "a �" xi d" b
i i
i=1,...,N i=1,...,N
Plecak
4 31 zł
zapakowany
1
optymalnie:
2 19 zł 6
2
4
plecak
3 27 zł
b
3 3
1 4 7 zł
2
ai ci
53 zł
Rozwiązanie optymalne: x1 = 0, x2 = 1, x3 = 1, x4 = 1
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 25
5