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 S

i

stosunkowo łatwo jest napisać

rekurencyjny algorytm generujący takie drzewo.

Rys.49 Początkowa część drzewa poszukiwań dla labiryntu z
rys. 47, gdy polem wyjściowym jest pole o numerze 1

labirynt

2

6

1

7

12

14

11

13

18

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 S

i

,

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 S

i

,

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ń ≅

≅

≅

≅ 4.4 x 10

9

.

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

n

, gdzie n jest

rozmiarem zadania, a C - pewną stałą. Po zastosowaniu
dekompozycji czas obliczeń skraca się do k *C * 2

n/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 znaleźć 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 S

i

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 10

5

operacji

jednostkowych na sekundę.

98

Algorytm

Klasa

algorytmu

Maksymalny

rozmiar

zadania

Maksymalny rozmiar

zadania

po 10-krotnym zwiększeniu

szybkości

A

1

A

2

A

3

A

4

A

5

A

6

O(N)
O(N*log N)
O(N

2

)

O(N

3

)

O(2

N

)

O(N!)

n

1

=864*10

7

n

2

=250*10

6

n

3

=900*10

2

n

4

=200*10

1

n

5

= 33

n

6

= 13

10* n

1

ok. 10* n

2

dla n

2

>>1

3.16* n

3

2.15* n

4

n

5

+ 3.3

-

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

2

).

Szokująco niskie wyniki dają natomiast algorytmy A

5

i A

6

, 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 A

5

), lub nawet jest tak mały, że

trudno go uchwycić (algorytm A

6

).

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 10

6

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.

Algorytm

Klasa

algorytmu

N=10

N=20

N=30

A

1

A

2

A

3

A

4

A

5

A

6

O(N)
O(N

2

)

O(N

3

)

O(2

N

)

O(3

N

)

O(N!)

1*10

-5

sek

1*10

-4

sek

1*10

-3

sek

1*10

-3

sek

0.59 sek

3.6 sek

2*10

-5

sek

4*10

-4

sek

8*10

-3

sek

1 sek

58 min

768 wieków

3*10

-5

sek

9*10

-5

sek

2.7*10

-2

sek

17.9 min

6.5 lat

8.4 *10

16

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 oraz g: X →

→

→

→ R.

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

≤

≤

≤ c * |g(x)| zachodzi dla

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

2

+ 0.5*n – 1

i=2

Ponieważ otrzymana funkcja może być ograniczona przez
funkcję n

2

możemy stwierdzić, że złożoność obliczeniowa

tego algorytmu wynosi O(n

2

).

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 odpowiedź 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ę znaleźć
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.

Rys. 52 Podział klas problemów z punktu widzenia istnienia dla nich
algorytm wielomianowych.

klasa NP klasa P

problemy NP- zupełne