90
Implementacja algorytmu z powrotami w postaci drzewa
Drzewo jest właściwą strukturą do przechowania informacji o
możliwych drogach poszukiwania rozwiązania za pomocą
algorytmu z powrotami.
Poniższy rysunek przedstawia początkową część drzewa, tak
zwanego drzewa poszukiwań, w którym wszystkie możliwe
ścieżki zaczynające się od korzenia drzewa są możliwymi
drogami w labiryncie, zaczynajÄ…cymi siÄ™ od pola o numerze 1.
Jest to drzewo stopnia czwartego.
Znając wszystkie zbiory Si stosunkowo łatwo jest napisać
rekurencyjny algorytm generujÄ…cy takie drzewo.
labirynt
1
2
7
12
13
11
6 14 18
Rys.49 Początkowa część drzewa poszukiwań dla labiryntu z
rys. 47, gdy polem wyjściowym jest pole o numerze 1
 91
Ponieważ drzewo takie przedstawia wszystkie możliwe
ścieżki, jego rozległość, a więc i zajętość pamięci, jest
znaczna. Natomiast niewÄ…tpliwÄ… zaletÄ… takiej reprezentacji jest
możliwość przeglądania drzewa przy użyciu prostych metod,
na przykład  rozszerzonej metody preorder, w której liczba
wywołań rekurencyjnych, jak również głębokość rekurencji,
będzie zaledwie równa głębokości drzewa.
Jest oczywistym, że kształt drzewa, będzie zależał od
uporządkowania wartości w poszczególnych zbiorach Si,
powinniśmy więc przyjąć uporządkowanie generujące drzewo
o możliwie małej wysokości, co zniweluje głębokość rekursji
dla algorytmu przeglÄ…dajÄ…cego drzewo.
Pojedyncze drzewo poszukiwań pozwala badać jedynie
ścieżki rozpoczynające się w punkcie umieszczonym w
korzeniu drzewa. Dlatego dla pełnej reprezentacji labiryntu
musimy utworzyć las zawierający drzewa rozpoczynające się
od wszystkich punktów labiryntu. Aby więc można było
stosować algorytm pozwalający badać ścieżki między dwoma
dowolnymi polami labiryntu musimy dysponować strukturą
zajmującą ogromny obszar pamięci.
Ponieważ zajętość pamięci rośnie tutaj wykładniczo ze
wzrostem rozmiarów labiryntu, dla większych labiryntów
stosowanie reprezentacji opartej o drzewa może okazać się
niemożliwe. Dla porównania  zajętość pamięci przy
wykorzystaniu reprezentacji w postaci zbiorów jest dla
naszego labiryntu nie większa niż 25 x 4 słowa pamięci, a co
najważniejsze rośnie liniowo ze wzrostem liczby pól
labiryntu. Pozostaje problem złożoności czasowej.
 92
Ćwiczenia do samodzielnego rozwiązania:
1. Dlaczego stopień drzewa poszukiwań z rys. 49 wynosi
cztery ?
2. Czy drzewo poszukiwań z rys. 49 zawiera powtarzające
się węzły, i dlaczego ?
3. Czy oprócz metody preorder do przeglądania drzewa z
rys. 49 użyć można innych metod (inorder, postorder)
a jeśli tak, to w jakich sytuacjach byłoby to
uzasadnione?
4. Zaproponuj rekurencyjne algorytmy oparte o schemat
preorder:
a) tworzący drzewo poszukiwań dla danego punktu
poczÄ…tkowego na podstawie
danych zbiorów Si,
b) obliczający ilość wszystkich możliwych ścieżek
między zadanym punktem początkowym a
końcowym,
c) podający długość najkrótszej ścieżki między
zadanym punktem początkowym a końcowym,
wykorzystujÄ…c wygenerowane drzewo
poszukiwań.
Metody usprawniania algorytmów o dużej złożoności
czasowej
Cały szereg dotychczas poznanych algorytmów
charakteryzowało się wykładniczą złożonością czasową. Były
to algorytmy, w których czas obliczeń wzrastał
nieprawdopodobnie szybko ze wzrostem rozmiarów struktury,
 93
której dotyczyły. Związane to było najczęściej z użyciem
rekurencji. Przypomnijmy w tym miejscu takie algorytmy, jak:
rekurencyjny algorytm obliczajÄ…cy n-tÄ… liczbÄ™ Fibonacciego,
algorytm sortowania szybkiego, algorytm szukania w głąb dla
grafu, ogólny algorytm z powrotami.
Duże zapotrzebowanie na czas obliczeń całkowicie
uniemożliwia stosowanie takich algorytmów do
rozwiązywania problemów, których rozmiary są dość znaczne.
Na szczęście wiele konkretnych problemów posiada
specyfikę, pozwalającą na usprawnienie algorytmów, które
dotychczas podawaliśmy w  czystej postaci.
Ogólnie metody usprawniania algorytmów o dużej
złożoności czasowej dzielimy na dwie duże grupy:
- metody systematyczne,
- metody heurystyczne.
W kolejnych rozdziałach postaramy się przybliżyć na czym
metody te polegajÄ…, opierajÄ…c siÄ™ na wybranych,
charakterystycznych przykładach.
Metody systematyczne
CechÄ… charakterystycznÄ… metod systematycznych jest
pewność. Ich stosowanie nie wpływa na jakość algorytmu, w
szczególności: nie zmniejsza szans na znalezienie
rozwiązania, w niczym nie ogranicza ilości rozwiązań, czy ich
dokładności.
Istnieje bardzo dużo różnego rodzaju metod usprawniania
algorytmów w sposób systematyczny. Prawie zawsze zależą
on od specyfiki rozwiÄ…zywanego problemu. W niniejszym
rozdziale omówimy trzy najczęściej spotykane metody.
 94
Metoda obcinania gałęzi
Metoda ta polega, mówiąc ogólnie, na rezygnacji z pewnych
dużych obszarów potencjalnych rozwiązań w oparciu o
stwierdzenia zaprzeczające istnieniu rozwiązań w tych
obszarach.
Jeśli problem byłby przedstawiony w postaci drzewa (
takiego jak drzewo poszukiwań ), to obcinanie gałęzi będzie
polegać na zaniechaniu poszukiwań w gałęzi ( poddrzewie )
zaczynającym się od określonego węzła. Można tego dokonać
tylko wtedy, jeśli mamy uzasadnioną pewność, że wybór tego
węzła i wszystkich jego następników nie prowadzi do
rozwiązań.
Do jak dużych usprawnień algorytmu może prowadzić
metoda obcinania gałęzi pokażemy posługując się klasycznym
przykładem tak zwanego problemu ośmiu hetmanów.
Problem ten sprowadza siÄ™ do odpowiedzi na pytanie:
Na ile różnych sposobów można ustawić na szachownicy o
rozmiarach 8 x 8 osiem hetmanów, aby się wzajemnie nie
szachowały ?
Algorytm rozwiÄ…zania tego problemu w  czystej postaci, to
jest opartej tylko na regułach szachowania, wymaga dla n=8
astronomicznej liczby badań E"
E" 4.4 x 109.
E"
E"
Stosując metodę obcinania gałęzi wykluczymy przede
wszystkim takie ustawienia hetmanów, które zawierają dwie
figury w tym samym wierszu, w tej samej kolumnie, na tej
samej przekątnej. Taka eliminacja ogranicza liczbę ustawień
do zbadania do 2056 ustawień.
 95
Metoda sklejania gałęzi
Metoda sklejania (łączenia) gałęzi jest kolejnym przykładem
metody systematycznej. Jeśli szukamy pewnych rozwiązań a
w drzewie poszukiwań istnieje więcej poddrzew
izomorficznych (takich samych jak badane poddrzewo), to
wystarczy zbadać tylko jedno, a otrzymany wynik
wykorzystać w innych miejscach wystąpienia takiego
poddrzewa.
Okazuje się, że zastosowanie metody sklejania gałęzi do
algorytmu rozwiązującego problem ośmiu hetmanów, jako
kolejnej metody systematycznej po wcześniejszym
zastosowaniu metody obcinania gałęzi, pozwala zredukować
liczbę badań już tylko do 801 węzłów.
Metoda dekompozycji
Wśród metod systematycznych szczególnie ważną pozycje
zajmuje metoda zwana metodÄ… dekompozycji problemu, lub
metodą  dziel i zwyciężaj . Jej zasadnicza idea została
zastosowana w omawianym już algorytmie sortowania
szybkiego Quick Sort dla tablic.
Ogólnie mówiąc polega ona na rozłożeniu rozwiązywane
problemu na k podproblemów ( jeśli jest to oczywiście
możliwe ), rozwiązaniu każdego z nich, a następnie
połączeniu rozwiązań cząstkowych w jedną całość. Wzrasta
wtedy zapotrzebowanie na pamięć, trzeba bowiem gdzieś
przechowywać rozwiązania cząstkowe przed ich zcaleniem,
ale może prowadzić do znacznego skrócenia czasu obliczeń.
 96
Załóżmy, że rozwiązanie wymaga czasu C * 2n , gdzie n jest
rozmiarem zadania, a C - pewną stałą. Po zastosowaniu
dekompozycji czas obliczeń skraca się do k *C * 2n/k + T,
gdzie T jest czasem potrzebnym na połączenie wszystkich
rozwiązań cząstkowych. Jeśli k nie jest duże i połączenie nie
jest zbyt kosztowne, metoda ta może dać znaczne skrócenie
czasu obliczeń.
Metody heurystyczne
Metody heurystyczne stosujemy, gdy nie ma możliwości
posłużenia się metodami systematycznymi. Idea tych metod
polega na przyjęciu pewnych założeń, co do których nie
mamy pewności, lub nawet wiemy, że nie są słuszne w całym
obszarze działania algorytmu, ale które bardzo wspomagają
poszukiwanie rozwiązań. Postępujemy tak mając świadomość,
że w pewnych, chociaż mniej prawdopodobnych sytuacjach,
zastosowana metoda heurystyczna może utrudnić szybkie
znalezienie rozwiązania, a czasem nawet uniemożliwić w
ogóle jego znalezienie.
Po metody heurystyczne będziemy więc sięgać, gdy nie
zależy nam na znalezieniu wszystkich rozwiązań i możemy
zadowolić się jednym rozwiązaniem, które jednak musi być
znalezione bardzo szybko (typowa sytuacja z gier
komputerowych).
W innych jeszcze przypadkach, gdy istnienie rozwiązań jest
bardzo wątpliwe, warto skorzystać z metod heurystycznych i
być może w krótkim czasie znalez
ć jakieś rozwiązanie.
Jest bardzo wiele rozwiązań heurystycznych, tak jak wiele
jest różnych typów algorytmów wymagających usprawnienia.
 97
W odniesieniu do algorytmu poszukujÄ…cego drogi w
labiryncie od pola a do pola b, jeśli wartość a jest mała, a
wartość b duża, stosowanie heurystyki mogłoby polegać na
ustawieniu wartości we wszystkich zbiorach Si w porządku
malejÄ…cym.
W ten sposób zapewnilibyśmy wybory pól o dużych
wartościach w pierwszej kolejności i większe
prawdopodobieństwo poruszania się po krótszej ścieżce a co
za tym idzie  szybsze osiągnięcie celu. Przyjmując taką
heurystykę musimy mieć świadomość, że przy pewnych
szczególnych ograniczeniach, występujących w labiryncie,
przyjęcie takiej heurystyki może utrudnić znalezienie
rozwiÄ…zania.
Szacowanie złożoności obliczeniowej algorytmów
Wykonanie każdego algorytmu wymaga określonego czasu
pracy komputera i określonej ilości pamięci.
Jak to już podkreślaliśmy, dla pewnych klas algorytmów,
czas ich działania lub rozmiar potrzebnej pamięci zwiększa się
bardzo szybko ze wzrostem rozmiaru zadania. Pojęcie
rozmiaru zadania, jak również innych pojęć, zdefiniujemy
sobie w dalszej części tego rozdziału dokładniej. Na razie
założymy, są one albo intuicyjnie dość zrozumiałe, albo ich
znaczenie zostało już wcześniej zasygnalizowane.
Załóżmy, że dysponujemy komputerem, który pracuje bez
przerwy przez 24 godz. wykonujÄ…c tylko 105 operacji
jednostkowych na sekundÄ™.
 98
Maksymalny Maksymalny rozmiar
Klasa rozmiar zadania
Algorytm
algorytmu zadania po 10-krotnym zwiększeniu
szybkości
A1 O(N) n1=864*107 10* n1
A2 O(N*log N) n2=250*106 ok. 10* n2 dla n2>>1
A3 O(N2) n3=900*102 3.16* n3
A4 O(N3) n4=200*101 2.15* n4
A5 O(2N) n5= 33 n5 + 3.3
A6 O(N!) n6= 13 -
Rys. 50 Tabela maksymalnych rozmiarów zadania, które można
rozwiązać w czasie 24 godz. dysponując algorytmami
różnych klas.
Trzecia kolumna powyższej tabeli pokazuje, jakie mogą być
maksymalne rozmiary zadania, które można rozwiązać w
czasie 24 godz. dla algorytmów różnych klas. Ostania
kolumna natomiast, jak zwiększy się maksymalny rozmiar
zadania po 10-krotnym zwiększeniu szybkości obliczeń przez
komputer.
Wyniki zamieszczone w tej tabeli pozwalają ocenić, jak
ważną sprawą jest dysponowanie algorytmem odpowiedniej
klasy. Widać, że dostatecznie satysfakcjonujące są algorytmy
klasy O(N) i O(N * log N), niestety bardzo często zmuszeni
jesteśmy sięgać po algorytmy klasy O(N2).
SzokujÄ…co niskie wyniki dajÄ… natomiast algorytmy A5 i A6, to
jest algorytmy o wykładniczej złożoności obliczeniowej.
Trzeba tu bowiem aż całej doby, aby doczekać się na wynik
działania algorytmu, gdy rozmiar rozwiązywanego zadania
wynosi zaledwie kilkadziesiąt, lub nawet kilkanaście.
 99
Ostania kolumna tej tabeli uzmysławia nam, że rozwój
sprzętu (coraz szybsze procesory i pamięci) niewiele
poprawiają sytuację, zwłaszcza dla algorytmów o dużej
złożoności obliczeniowej, dla których maksymalny rozmiar
zadania nawet nie wzrasta liniowo ze wzrostem mocy
obliczeniowej (algorytm A5), lub nawet jest tak mały, że
trudno go uchwycić (algorytm A6).
Tak więc ogromny postęp w rozwoju sprzętu
komputerowego, jaki cały czas obserwujemy, nie wpłynie w
zasadniczy sposób na czas obliczeń, jeśli do rozwiązywania
problemów stosować będziemy nieodpowiednie algorytmy.
Rola algorytmiki, dziedziny informatyki teoretycznej,
zajmującej się opracowywaniem nowych algorytmów i
doskonaleniem już istniejących, jest ogromna.
Odwróćmy teraz sytuacje i załóżmy, że dysponujemy
komputerem, który wykonuje 106 operacji jednostkowych na
sekundę i podajmy czasy wykonywania się programów
opartych o algorytmy różnych klas, gdy rozmiary zadania
wynoszÄ…: 10, 20 i 30.
Klasa N=10 N=20 N=30
Algorytm
algorytmu
A1 O(N) 1*10-5 sek 2*10-5 sek 3*10-5 sek
A2 O(N2) 1*10-4 sek 4*10-4 sek 9*10-5 sek
A3 O(N3) 1*10-3 sek 8*10-3 sek 2.7*10-2 sek
A4 O(2N) 1*10-3 sek 1 sek 17.9 min
A5 O(3N) 0.59 sek 58 min 6.5 lat
A6 O(N!) 3.6 sek 768 wieków 8.4 *1016
wieków
Rys. 51 Czasy wykonywania się programów oparte o algorytmy
różnych klas.
 100
Wyniki zamieszczone w tej tabeli potwierdzajÄ… wnioski
wynikające z analizy wyników zamieszczonych w poprzedniej
tabeli i jeszcze bardziej utwierdzają w przekonaniu, że
sięganie po algorytmy o wykładniczej złożoności
obliczeniowej dla zadań o rozmiarze przekraczającym
kilkanaście mija się z celem.
Uściślimy teraz, stosowane dotychczas w sposób dość
intuicyjny, pojęcia. Zobaczymy też, jak w prosty sposób, nie
uciekajÄ…c siÄ™ do rozbudowanego aparatu matematycznego,
szacować można złożoność obliczeniową algorytmów.
Następujące operacje, zapisane w języku wysokiego
poziomu, uważać będziemy dla celów szacowania złożoności
obliczeniowej, za operacje jednostkowe:
- wykonanie operatora numerycznego, relacyjnego lub
logicznego,
- nadanie wartości zmiennej typu prostego,
- obliczenie wartości zmiennej indeksowanej,
wskazywanej lub pola struktury,
- inicjowanie procedury lub funkcji,
- przekazanie wartości parametru aktualnego,
- wykonanie operacji wejścia lub wyjścia.
Dla celów szacowania złożoności obliczeniowej założyć
można, że czas wykonywania wszystkich tych operacji jest
taki sam.
Załóżmy teraz, że mamy algorytm K, dla którego dla
każdego zestawu danych wejściowych d "D (D jest zbiorem
"
"
"
zestawów danych wejściowych), obliczenia algorytmu
dochodzą do punktu końcowego. Przez T(d) oznaczać
 101
będziemy liczbę operacji jednostkowych wykonywanych
przez algorytm K dla d "D. Funkcję T(d) nazywamy pełną
"
"
"
funkcjÄ… kosztu.
Jest to funkcja T: D N ze zbioru danych wejściowych w



zbiór liczb naturalnych (liczbę operacji jednostkowych).
Zwykle bardzo trudno jest ustalić i opisać pełną funkcję
kosztu, jest ona bowiem trudna do wyznaczenia i zapisania w
jednolity, czytelny sposób dla każdego z możliwych zestawów
danych wejściowych.
Z powyższych powodów określamy zwykle tylko rząd
wielkości funkcji. Z praktycznego punktu widzenia jest
zresztą niecelowe wyznaczanie pełnej funkcji kosztu.
Niewiele informacji daje nam bowiem opis zachowania siÄ™
algorytmu w sytuacjach najlepszego przypadku, czy nawet
średnie zachowanie się algorytmu.
Natomiast interesujÄ…ce sÄ… sytuacje najgorszego przypadku,
gdyż tutaj tkwi niebezpieczeństwo znacznego wydłużenia
czasu obliczeń. Określmy teraz pojęcie rzędu funkcji. Niech X
będzie dowolnym zbiorem. Dysponujemy dwiema funkcjami
f: X R.
R oraz g: X


Definicja: Powiemy, że funkcja f jest co najwyżej rzędu
funkcji g, co zapiszemy f=O(g), jeśli istnieje stała
c>0, takie że relacja |f(x)| d" c * |g(x)| zachodzi dla
d"
d"
d"
prawie wszystkich wartości x "X (to jest dla
"
"
"
wszystkich, za wyjÄ…tkiem pewnego, niewielkiego,
skończonego, być może pustego, podzbioru X).
Tym niewielkim, skończonym podzbiorem będą, w
przypadku szacowania złożoności obliczeniowej, te zbiory
 102
danych, dla których pełna funkcja kosztu T(d) nie da się
dokładnie oszacować przez jakąś prostą funkcję g(N).
Sytuacja ta zresztą dotyczy zwykle niewielkich wartości N, a
ponieważ jesteśmy zainteresowani szacowaniem złożoności
obliczeniowej dla dużych N, możemy pominąć te niewielkie
zbiory danych wejściowych i szacować T(d) przez g(N) jako
O(g(N)) mówiąc o funkcji kosztu niepomyślnego
przypadku lub po prostu o funkcji kosztu. W literaturze
spotkać można jeszcze inne określenia dla funkcji kosztu:
funkcja złożoności czasowej (lub złożoność czasowa),
pesymistyczna złożoność czasowa, klasa algorytmu.
Teraz zdefiniujemy sobie pojęcie rozmiaru danych.
Ponieważ uzależnianie funkcji kosztu od wszystkich danych
komplikuje sprawę konstruowania tej funkcji, wyróżnia się
spośród danych te, które mają największy wpływ na wartość
funkcji kosztu.
Na przykład, w algorytmie wykonującym mnożenie
macierzy, gdzie D = < A, B, m, n, k >, macierz A ma rozmiar
m*n a macierz B ma rozmiar n*k, wpływ na funkcje kosztu
majÄ… tylko rozmiary obu macierzy, to jest m, n i k.
Chociaż w szeregu algorytmów również postać samych
danych (ich wartość, sposób uporządkowania, itd.) wpływa na
czas działania algorytmów, dla algorytmu mnożenia macierzy
można przyjąć, że rozmiarem danych, oznaczmy go przez |d|,
jest |d|=max(m,n,k).
Algorytm mnożenie macierzy jest jednak algorytmem pod
tym względem trochę nietypowym. Na ogół łatwo jest
określić, co jest rozmiarem danych. Są to: rozmiar
 103
jednowymiarowej tablicy, liczba elementów w liście liniowej
jednokierunkowej, liczba węzłów w drzewie, lub jego
wysokość, liczba węzłów i/lub liczba krawędzi w grafie.
Podobnie, przy szacowaniu złożoności obliczeniowej
algorytmów rozważa się tylko pewne wyróżnione operacje
jednostkowe, zwane operacjami dominujÄ…cymi algorytmu.
W algorytmach wykorzystujÄ…cych iteracjÄ™ sÄ… to zwykle
warunki kontrolujące pętle iteracyjne. Ilość wykonanych
badań takiego warunku jest w przybliżeniu równa ilości
wykonań wnętrza pętli iteracyjnej.
Instrukcje wewnętrzne pętli, o ile same nie są pętlami lub
wywołaniami iteracyjnymi, nie mają wpływu na szacowanie
kosztu algorytmu, bowiem od ich ilości zależy tylko wartość
stałej przez którą mnożymy ilość wykonań pętli. Ponieważ
wyznaczamy tylko rząd funkcji, nie ma to żadnego znaczenia
dla szacowania złożoności czasowej algorytmu.
Tak więc otrzymaliśmy bardzo prosty przepis na szacowania
złożoności obliczeniowej algorytmów iteracyjnych pod
warunkiem, że potrafimy dobrze zidentyfikować rozmiar
danych a także wskazać wszystkie operacje dominujące
algorytmu. O wiele trudniej jest szacować funkcje kosztu dla
algorytmów rekurencyjnych. To jednak przekracza ramy
naszego wykładu.
Poniższy przykład zilustruje, jak szacować złożoność
obliczeniową algorytmów iteracyjnych. Zadanie polega na
oszacowaniu funkcji kosztu dla algorytmu na podstawie
fragmentów programu, zapisanego w języku C++.
 104
. . . . .
int a[N];
. . . . .
for (int i:=2; i<= n; i++)
1: if (a[i-1]>a[i]) then
{
v:=a[i]; j:=i-1;
do
{ a[j+1]:=a[j]; j:=j-1; }
2: while( a[j] <= v );
a[j+1]:=v;
}
Badanie warunku zapisanego w linii 1 wykona się dokładnie
n-1 razy, w linii 2  co najwyżej i-1 razy (tzn. dla j=i-1, i-2,
..., 0). Tak więc ogólna liczba porównań jest ograniczona od
od góry przez
n
(i-1) + "
"(i-1) = n-1 + n*(n+1)/2  1  (n-1) = = 0.5*n2 + 0.5*n  1
"
"
i=2
Ponieważ otrzymana funkcja może być ograniczona przez
funkcję n2 możemy stwierdzić, że złożoność obliczeniowa
tego algorytmu wynosi O(n2).
Na koniec tego rozdziału zdefiniujemy jeszcze w sposób
ostateczny pojęcia algorytmu o wielomianowej i wykładniczej
złożoności czasowej.
Definicja: Algorytmem wielomianowym nazywać będziemy
algorytm, którego funkcją złożoności czasowej jest
O(p(N)), gdzie p jest pewnym wielomianem a N 
rozmiarem danych.
Definicja: Każdy algorytm, którego funkcja złożoności
czasowej nie może być ograniczona
 105
wielomianem, nazywamy algorytmem
wykładniczym (chociaż jego funkcja złożoności
czasowej niekoniecznie musi być funkcją
wykładniczą).
Ćwiczenia do samodzielnego rozwiązywania:
1. Spróbuj oszacować funkcje złożoności obliczeniowej dla
algorytmów omówionych w treści wykładu.
Problemy algorytmicznie trudne
Już od bardzo dawna ludzie zajmujący się algorytmami
starali się odpowiedzieć sobie na pytanie:
Czy dla problemów, dla których nie znaleziono dotychczas
rozwiązujących je w wielomianowym czasie algorytmów,
takie algorytmy w ogóle istnieją ?
Dzisiaj można stwierdzić, że odpowiedz
na to pytanie jest
bardzo złożona.
Wszystkie omówione w trakcie wykładu algorytmy
rozwiązywały problemy należące do wielkiej rodziny
problemów, nazwanej problemami decyzyjnymi. Odrębna
rodzinę stanowią, na przykład, problemy zwane problemami
optymalizacyjnymi. Problemami z tego zakresu nie
zajmowaliśmy się.
Klasę problemów decyzyjnych nazwano NP. W klasie tej
zawarta jest klasa problemów nazwana klasą P.
Definicja: Klasę problemów P tworzą wszystkie problemy
decyzyjne, dla których istnieją rozwiązujące je w
wielomianowym czasie algorytmy.
 106
Najbardziej interesującą klasą jest klasa tzw. problemów NP
 zupełnych, do której należą klasycznie trudne problemy
decyzyjne i dla których, mimo usiłowań, nie udało się znalez
ć
algorytmów wielomianowych. Prawdopodobnie można je
rozwiązywać tylko przy pomocy algorytmów wykładniczych.
Aktualna lista problemów NP  zupełnych obejmuje już kilka
tysięcy problemów z różnych dziedzin.
Oznaczałoby to, że klasa problemów P jest właściwą
podklasą NP, a ponadto, że klasy problemów P i NP -
zupełnych są rozłączne.
klasa NP
klasa P
problemy NP- zupełne
Rys. 52 Podział klas problemów z punktu widzenia istnienia dla nich
algorytm wielomianowych.