Rozdział 7

Wyszukiwanie wyczerpujące

7.1.

Wprowadzenie

Rozwiązanie wielu problemów wymaga odpowiedzi na pytania typu: „ jak wiele jest możliwości. . . ”,

„znaleźć wszystkie możliwe zbiory spełniające pewien warunek”, „czy istnieje sposób. . . ”.

Znalezienie odpowiedzi na te pytania polega zwykle na analizie wszystkich potencjalnych rozwiązań

i wyborze spośród nich tych, które spełniają warunki zadania. Ponieważ w ten sposób zostają wyczerpane

wszystkie możliwe rozwiązania, postępowanie takie nazywamy wyszukiwaniem wyczerpującym (ang.

exhaustive search). Sposobem tym rozwiązujemy problemy, dla których nie istnieje lub nie jest znany

algorytm generujący rozwiązanie w inny sposób. Wyszukiwanie wyczerpujące jest bowiem czasochłonne,

co w skrajnych przypadkach może uniemożliwiać praktyczne jego zastosowanie.

7.2.

Organizacja poszukiwań

Dalej zostaną przedstawione dwie ogólne metody organizacji tego rodzaju poszukiwań: metoda powro-

tów i metoda sita.



metoda powrotów (ang. backtrack) polega na kostruowaniu pewnego częściowego rozwiązania

problemu i próby rozszerzania tego rozwiązania w kolejnych krokach. Jeśli rozszerzenie nie jest

możliwe, należy skrócić rozwiązanie częściowe i spróbować rozszerzyć je w inny niż poprzednio

sposób. W razie niepowodzenia skracanie (czyli właśnie powroty) jest kontynuowane. Metoda ta

gwarantuje znalezienie rozwiązania, jeśli tylko takie istnieje i jest poprawnie opisane w algorytmie.

Metoda powrotów jest stosowana dla szerokiej klasy problemów wyszukiwawczych, m.in. w rozbio-

rach zdań, grach itp.

93

94

Analiza algorytmów - ćwiczenia

Termin backtrack wprowadził D. H. Lehmer w 1950 roku, ale sama metoda była wielokrotnie

wcześniej odkrywana, chociaż nie została opisana w ogólnej postaci.



metoda sita jest logicznym uzupełnieniem metody powrotów i polega na eliminacji rozwiązań

nie spełniających warunków zadania. Zbiór rozwiązań konstruuje się więc „z góry”, wychodząc od

wszystkich możliwych rozwiązań. Sita są wygodne przede wszystkim w zastosowaniach z zakresu

teorii liczb.

Metody powrotów i sita są tylko metodami ogólnymi. Bezpośrednie ich stosowanie prowadzi zwykle

do algorytmów o ogromnych wymaganiach czasowych iłub pamięciowych. Na komputerach PC w roz-

sądnym czasie rzędu godzin można przeszukiwać zbiory o mocy 10

10

. Dlatego też metody te powinny

być uważane za schemat konstrukcji rozwiązania, a nie rozwiązanie. Schemat taki musi być każdorazo-

wo dostosowywany do konkretnych potrzeb, i to na tyle pomysłowo, aby możliwa była jego praktyczna

realizacja.

7.3.

Metoda powrotów

Koncepcja metody powrotów zostanie wyjaśniona na przykładzie zadania o przechodzeniu przez labirynt.

7.1. Szukanie wyjścia z labiryntu

Celem jest znalezienie drogi z pola początkowego (we) do pola końcowego (wy) przez sąsiadujące

pola, nie przechodząc oczywiście przez ściany (rys. ??).

Najbardziej prymitywnym rozwiązaniem byłoby ponumerowanie wszystkich pól labiryntu, wyge-

nerowanie wszystkich możliwych permutacji ciągów tych numerów o długościach nie przekraczających

liczby pól labiryntu i sprawdzenie, które z tych permutacji opisują rozwiązanie. Dla przykładowego la-

birytnu z rysunku ?? oznaczałoby to sprawdzenie 25! + 24! + . . . + 1! permutacji. Liczba ta przekracza

1, 6e25 i realizacja takiego algorytmu w rozsądnyn czasie jest oczywiście nierealna.

Istnieje też algorytm znajdujący drogę w czasie O(n

2

), gdzie n jest długością boku labiryntu. Tutaj

zostanie przedstawiona metoda powrotów, która również pozwala na efektywne znalezienie rozwiązania.

Algorytm zbudowany zgodnie z tą koncepcją może wyglądać następująco:

Rozdział 7: Wyszukiwanie wyczerpujące

95

1. Jeśli znajdujemy się na końcowym polu, to rozwiązanie zostało znalezione – koniec szukania.

2. Spośród pól sąsiadujących z tym, na którym aktualnie stoimy, wybieramy jedno z tych, które jeszcze

nie należy do drogi, do którego da się przejść i jednocześnie nie było jeszcze analizowane Jeśli jest

takie pole, wydłużamy drogę o to pole i realizujemy szukanie drogi tak, jakby było ono polem

wyjściowym. Jeśli nie, to skracamy drogę o aktualne pole. Jeśli nie da się skrócić, to rozwiązania

nie ma.

Reguły te mówią, w jaki sposób przedłużyć aktualną drogę (o ile to możliwe) i co zrobić w razie

niepowodzenia.

Na tym polega metodów: należy rozszerzać aktualne rozwiązanie dopóki jest to możliwe, a gdy

rozwiązanie nie może być dalej rozszerzane, należy wrócić do stanu bezpośrednio poprzedzającego stan

„zablokowany” i sprawdzić nie badane dotychczas rozwiązania.

Jest to rekurencyjna wersja algorytmu. Wymaga pamiętania na każdym poziomie (odpowiadającym

bieżącej długości drogi) listy pól sąsiadujących już przeanalizowanych i pozostałych do analizy.

7.4.

Ogólny algorytm

W najogólniejszym przypadku zakładamy, że rozwiązaniem problemu jest wektor (a

1

, a

2

, . . . a

k

) o skoń-

czonej, ale nie znanej z góry długości, spełniający pewne warunki. Każda „współrzędna” a

i

jest ele-

mentem skończonego, liniowo uporządkowanego zbioru A

i

, oznaczającego możliwe wartości a

i

, być

może różne dla różnych i.

W wyszukiwaniu należy więc jako potencjalne rozwiązania rozważyć elementy zbioru A

1

×A

2

×. . . A

k

dla k = 0, 1, 2, . . . .

W przykładzie z labiryntem wszystkie zbiory A

i

będą jednakowe:

A

i

=

{ruch w lewo, ruch w górę, ruch w prawo, ruch w dół}

Reguły można opisać następująco: nie wolno przechodzić przez ściany, po ruchu w górę nie może

wystąpić ruch w dół, po ruchu w lewo nie może wystąpić ruch w prawo itd., nie można wykonać ruchu

na pole już znajdujące się w bieżącej drodze.

Powróćmy do ogólnego algorytmu. Na początek przyjmuje się jako rozwiązanie częściowe wektor

pusty (), a na podstawie danych ograniczeń określamy, które elementy zbioru A

1

są kandydatami na

współrzędną a

1

. Taki podzbiór zbioru A

1

oznaczymy przez S

1

. Wybieramy jako a

1

pierwszy element ze

zbioru S

1

otrzymując w ten sposób rozwiązanie częściowe (a

1

).

Ogólnie, różne ograniczenia opisujące rozwiązania mówią, jaki podzbiór S

k

zbioru A

k

jest zbiorem

kandydatów na roszerzenie rozwiązanie częściowego (a

1

, . . . a

k−1

) do (a

1

, . . . a

k−1

, a

k

). Jeśli S

k

=

∅, to

96

Analiza algorytmów - ćwiczenia

„wracamy” i wybieramy jako a

k−1

inny element S

k−1

. Jeśli znowu S

k−1

=

∅, to cofamy się do a

k−2

. Jeśli

wycofamy się aż do a

1

i też okaże się, że nie ma już innych elementów S

1

do rozszerzenia rozwiązania,

to skończyliśmy przeszukiwanie.

Dzięki ograniczaniu możliwych ruchów do elementów zbioru S

k

zamiast A

k

, mamy możliwość znacz-

nego okrojenia tzw. drzewa wyszukiwania. Bez ograniczania musielibyśmy przeanalizować drzewo o

|A

1

| · |A

2

| · . . . · |A

d

| liściach, gdzie d jest długością rozwiązania, jak przedstawiono na rys. 7.2.

7.2. Ilustracja możliwości obcinania gałęzi drzewa wyszukiwania. Bez obcinania przeanalizowane musia-

łyby być wszystkie węzły. Obcięcia znacznie redukują liczbę węzłów, tym bardziej, im wyżej (bliżej

korzenia) są dokonywane.

Algorytm z powrotami pozwala wcześnie odcinać całe gałęzie drzewa wyszukiwania, zmniejszając

liczbę koniecznych obliczeń.

Rysunek 7.3 przedstawia przykładowe drzewo z odciętymi gałęziami i kolejność przeszukiwania

węzłów drzewa przez algorytm wyszukiwania wyczerpującego. Jeśli rozwiązania istnieją, to na pewno

będą w tym drzewie – to musi zagwarantować metoda odcinania gałęzi.

Korzeń drzewa reprezentuje pusty wektor rozwiązania ().

Każdy wierzchołek drzewa reprezentuje pewne rozwiązanie częściowe (a

1

, a

2

, . . . , a

i

).

Ogólny algorytm wyszukiwania wyczerpującego (z powrotami) można zapisać następująco:

Powyższa wersja wymaga jednoczesnego zapamiętywania wielu zbiorów S

k

, dla różnych k (pozio-

mów). Może to być zrealizowane np. w tablicy. Zmienna k numeruje „poziomy”, w przypadku labiryntu

Rozdział 7: Wyszukiwanie wyczerpujące

97

7.3. Przykładowe drzewo z odciętymi gałęziami i kolejność przeszukiwania węzłów drzewa przez algorytm

wyszukiwania wyczerpującego, zaznaczona przerywaną linią.

byłyby to długości aktualnie analizowanej drogi. Przy skracaniu rozwiązania (tzn. powrotach z powodu

niepowodzenia w rozszerzaniu wektora (a

1

, a

2

, . . . , a

k

)) potrzebna jest informacja o możliwościach – ele-

mentach zbiorów S

k−1

, S

k−2

itd., które nie zostały jeszcze przeanalizowane. Stąd konieczność jawnego

przechowywania wielu S

k

np. w tablicy. Jest to właściwie zapis rekurencyjnego algorytmu w postaci

nierekurencyjnej, ze stosem emulowanym w tablicy. Wersja rekurencyjna może okazać się czytelniejsza:

Operator

|| oznacza konkatenację ciągów, czyli „zlepianie” ciągów:

(a

1

, a

2

, . . . , a

k

)

|| (b

1

, b

2

, . . . , b

l

) = (a

1

, a

2

, . . . , a

k

, b

1

, b

2

, . . . , b

l

)

W powyższym algorytmie do ciągu w dołącza się nowy element a.

7.5.

Metoda podziału i ograniczeń

Metoda podziału i ograniczeń jest odmianą metody powrotów. Zakładamy, że z każdym rozwiązaniem

jest związany pewien koszt, a rozwiązaniem optymalnym jest rozwiązaniem o najniższym koszcie. Aby

metoda to mogła być zastosowana, musi też być możliwe zdefiniowanie kosztu rozwiązań częściowych.

98

Analiza algorytmów - ćwiczenia

1

procedure wyszukiwanie z powrotami;

2

begin

3

„wyznacz S

1

na podstawie A

1

i ograniczeń”;

4

k := 1;

5

while k > 0 do

6

while S

k

= ∅ do

7

a

k

:= element z S

k

;

8

S

k

:= S

k

− {a

k

};

9

if „(a

1

, a

2

, . . . , a

k

) jest rozwiązaniem” then

10

„wypisz (a

1

, a

2

, . . . , a

k

)”;

11

end if;

12

k := k + 1;

f

następny „poziom”

g

13

„wyznacz S

k

na podstawie A

k

i ograniczeń”;

14

end while;

15

k := k

− 1;

f

powrót

g

16

end while;

17

end.

1

procedure wysz z pow rek(w: wektor; i: integer);

2

var a: element wektora; S: zbiór;

3

begin

4

if „w jest rozwiązaniem” then

5

„wypisz(w)”;

6

end if;

7

„wyznacz S”;

8

for a

∈ S to Poprawić BookAA.cls do

9

wysz z pow rek(w

|| (a), i + 1);

10

end for;

11

end.

Rozdział 7: Wyszukiwanie wyczerpujące

99

Ponadto, rozszerzanie rozwiązania nie może zmniejszać jego kosztu:

koszt(a

1

, a

2

, . . . , a

k−1

)

koszt(a

1

, a

2

, . . . , a

k−1

, a

k

)

Jeśli są spełnione te warunki, to można odrzucać rozwiązania częściowe, których koszt jest większy od

dotychczas znalezionego rozwiązania optymalnego. Dzięki temu odcinaniu gałęzi drzewa wyszukiwania

uzyskuje się dalsze zmniejszenienie liczby węzłów do analizy.

Algorytm w ogólnej postaci jest podobny do przedstawionego wcześniej algorytmu ogólnego wyszu-

kiwania wyczerpującego. Jest tylko uzupełniony o wyznaczanie kosztu, zapamiętywanie aktualnej mini-

malnej wartości tego kosztu i odcinanie gałęzi drzewa na pewno prowadzących do rozwiązań o wyższym

koszcie niż bieżące minimum.

Oczywiście metoda ta może być stosowana tylko dla szczególnego rodzaju problemów, najczęściej

takich, w których każdy liść pełnego drzewa wyszukiwania reprezentuje poprawne rozwiązanie i należy

tylko wybrać spośród nich rozwiązanie optymalne (najtańsze).

Ogólny algorytm rozwiązujący problem metodą podziału i ograniczeń można zapisać następująco:

1

procedure wyszukiwanie z powrotami;

2

begin

3

min koszt :=

∞;

f

nieskończoność, bieżące minimum

g

4

koszt := 0;

f

aktualny koszt

g

5

„wyznacz S

1

na podstawie A

1

i ograniczeń”;

6

k := 1;

7

while k > 0 do

8

while (S

k

= ∅) and (koszt < min koszt) do

9

a

k

:= element z S

k

;

10

S

k

:= S

k

− {a

k

};

11

koszt := koszt(a

1

, a

2

, . . . , a

k

);

12

if „(a

1

, a

2

, . . . , a

k

) jest rozwiązaniem” and koszt < min koszt then

13

min koszt := koszt((a

1

, a

2

, . . . , a

k

));

14

end if;

15

k := k + 1;

f

następny „poziom”

g

16

„wyznacz S

k

na podstawie A

k

i ograniczeń”;

17

end while;

18

k := k

− 1;

f

powrót

g

19

koszt := koszt((a

1

, a

2

, . . . , a

k

));

20

end while;

21

end.

100

Analiza algorytmów - ćwiczenia

7.6.

Modyfikacje metody powrotów

W konkretnych przypadkach zadań rozwiązywanych metodą wyszukiwania wyczerpującego możliwe są

różnego rodzaju optymalizacje przyspieszające przeszukiwanie drzewa. Wymienimy tu niektóre z nich:



wykluczanie (lub obcinanie gałęzi) polega na usuwaniu pewnych poddrzew z drzewa wszyst-

kich rozwiązań, czyli obcinaniu gałęzi nie tylko w przypadku prostego braku możliwości rozszerze-

nia rozwiązania wynikającego z ograniczeń nałożonych przez zadanie, ale również przy spełnieniu

innych warunków. Pewnym odejściem od ścisłego przeszukiwania wyczerpującego mogą tu być

heurystyczne metody oceny stanu wyszukiwania. Na podstawie oceny można odciąć gałęzie „nie

rokujące nadziei” na dojście do rozwiązania, ale bez pewności, czy ocena była prawidłowa i czy nie

odrzucono gałęzi prowadzącej do (być może jedynego) rozwiązania.



skelejanie (lub łączenie gałęzi) polega na unikaniu wielokrotnego powtarzania tego samego

przeszukiwania, jeśli w drzewie są dwa lub więcej podrzewa izomorficzne, czyli takiego samego

kształtu

1

. Wtedy wystarczy przeszukać tylko jedno z nich, a dla kolejnych prób przeszukiwania

odczytać wcześniej uzyskany wynik. Przykładowo, na rys. 7.4 przedstawiono labirynt, którego lewa

część połączona jest z prawą tylko jednym przejściem. W takiej sytuacji początkowa część drzewa

może zawierać wiele węzłów opisujących sposób dojścia do tego przejścia. Ale każdy z tych węzłów

będzie korzeniem identycznego poddrzewa opisującego dalszą drogę z tego przejścia do wyjścia z

labiryntu. Wystarczyłoby przeanalizować tylko jedno takie podrzewo. Praktyczna implementacja

tego sposobu może być bardzo trudna.

7.4. Labirynt ilustrujący możliwość łączenia gałęzi drzewa wyszukiwania



reorganizacja wyszukiwania - jest to metoda heurystyczna, użyteczna, gdy istnienie rozwią-

zań jest wątpliwe, lub gdy poszukuje się tylko jednego (jakiegokolwiek) rozwiązania. Jeśli istnieje

podejrzenie, że rozwiązanie będzie miało jakiąś szczególną własność, warto tak poprowadzić poszu-

kiwania, aby to potencjalne rozwiązanie było sprawdzone w pierwszej kolejności, a przynajmniej

jak najszybciej. Jeśli jest to możliwe, drzewo powinno być tak przebudowane, aby węzły niskiego

1

przez jednakowy kształt rozumiemy tu identyczność drzew

Rozdział 7: Wyszukiwanie wyczerpujące

101

stopnia (tzn. o małej liczbie synów) znalazły się blisko korzenia drzewa. Wtedy ewentualne odcięcie

gałęzi spowoduje eliminację większej liczby liści. Ilustruje to rys. 7.5.

7.5. Reorganizacja drzewa. Obydwa drzewa mają jednakową liczbę liści, ale drzewo (a) można efektywniej

przeszukać niż (b), ponieważ odcięcie gałęzi wyeliminuje naraz więcej liści.

7.7.

Szacowanie efektywności

Na ogół metoda powrotów prowadzi do algorytmów o wykładniczej złożoności względem długości wektora

rozwiązań. Jeśli rozwiązania maja długość co najmniej d, to należy w drzewie sprawdzić

d



i=1

|A

i

|

liści, gdzie

|A

i

| jest liczbą elementów w zbiorze A. Nawet przy szerokim zastosowaniu wykluczania i

sklejania można się spodziewać, że

|S

i

| będzie stałą – pewnym ułamkiem |A

i

|.

Realizacja algorytmu wyszukiwania może więc trwać bardzo długo. Użytkownik chciałby wiedzieć,

jakiego czasu działania ma się spodziewać i znać przybliżony czas zakończenia obliczeń. Oszacowanie

tego czasu nie jest możliwe bez znajomości liczby węzłów drzewa wyszukiwania, które będą analizowane.

Wtedy można obliczyć stosunek liczby dotychczas przeanalizowanych węzłów do wszystkich węzłów i

wyznaczyć ułamek wykonanej pracy, który można np. przedstawić w postaci „paska postępu” (ang.

progress bar). Jednak dokładne obliczenie liczby wszystkich węzłów metodami analitycznymi jest bardzo

trudne ze względu na nieprzewidywalność oddziaływań różnych ograniczeń podczas schodzenia w głąb

drzewa.

7.7.1.

Metoda Monte Carlo

W przypadku trudnych do obliczenia metodami analitycznymi wartości stosuje się czasem metodę Monte

Carlo. Prawidłowe jest skojarzenie tej nazwy z kasynami i grami losowymi. Metoda polega na wykonaniu

pewnej liczby eksperymentów losowych i oszacowaniu szukanej wartości na podstawie wyników tych

eksperymentów. Przykładowo, chcąc wyznaczyć pole koła albo innej figury nie znając dokładego wzoru

opisującego to pole, można umieścić figurę w kwadracie o jednostkowym polu. Następnie wylosować dużą

liczbę punktów w tym kwadracie (rozkład prawdopodobieństwa powinien być równomierny), dla każdego

sprawdzić, czy należy do figury czy nie i ostatecznie wyznaczyć stosunek liczby punktów „trafionych” do

102

Analiza algorytmów - ćwiczenia

wszystkich wylosowanych, otrzymując przybliżoną wartość pola figury. Błąd, którym będzie obarczony

wynik, będzie tym mniejszy, im więcej punktów zostanie wylosowanych.

7.7.2.

Szacowanie wielkości drzewa

Tę samą metodę można zastosować do oszacowania wielkości drzewa wyszukiwania. W tym celu zostanie

przeprowadzonych kilka eksperymentów polegających na wykonaniu wyszukiwania metodą powrotów z

wybranymi losowo wartościami a

i

.

Wędrując przy każdym eksperymencie w głąb drzewa będziemy szacować wielkość całego drzewa.

W tym celu założymy, że wszystkie rozgałęzienia wyglądają tak, jak napotykane wzdłuż ścieżki, którą

przechodzimy, czyli mają tyle samo synów. Dla każdego eksperymentu uzyskuje się więc jedno oszacowa-

nie liczby węzłów drzewa. Ilustruje to rys. ??. Wylosowana ścieżka, którą poruszamy się w dół drzewa,

po wyjściu z korzenia rzechodzi przez węzeł o dwóch synach. Przyjmujemy więc, że wszystkie pozostałe

węzły na tym poziomie też mają dwóch synów. Na następnych poziomach również przyjmujemy takie

założenie, aż do liścia kończącego ścieżkę.

7.6. Szacowanie wielkości drzewa

Jeśli oznaczymy liczbę synów węzłów na wylosowanej ścieżce przez x

1

, x

2

, . . . , x

d

, gdzie d jest

długością ścieżki, to całkowita liczba węzłów W drzewa (bez korzenia) zostanie oszacowana przez:

W = x

1

+ x

1

x

2

+ x

1

x

2

x

3

+ . . . +

d



j=1

x

j

=

d



i=1

i



j=1

x

j

W jednym eksperymencie sprawdzamy tylko jedną ścieżkę. Aby uzyskać wiarygodny wynik, nale-

ży wykonać więcej eksperymentów i uśrednić wynik. Liczba eksperymentów zależy głównie od czasu,

który możemy poświęcić na szacowanie wielkości drzewa. Im więcej eksperymentów, tym dokładniejsze

oszacowanie.

Algorytm szacujący wielkość drzewa jest modyfikacją podstawowego algorytmu wyszukiwania wy-

czerpującego, ale bez powrotów – za każdym razem interesuje nas tylko jedna droga z korzenia do liścia,

więc nie ma potrzeby implementacji skracania rozwiązania. Poza tym różni się od niego wyborem loso-

wego elementu z S

i

zamiast kolejnego i jest uzupełniony o obliczanie średniej liczby węzłów.

Przykładowo, szacując wielkość drzewa wyszukiwania dla problemu rozmieszczania 11 hetmanów

na szachownicy 11 na 11, można otrzymać dla N = 1000 oszacowanie liczby węzłów na 70806, przy

rzeczywistej liczbie węzłów 70214.

Rozdział 7: Wyszukiwanie wyczerpujące

103

1

procedure szacowanie;

2

begin

3

f

N oznacza liczbę eksperymentów do przeprowadzenia

g

4

średnia := 0;

5

for i := 1 to N do

6

iloczyn := 1;

f

na iloczyn x

1

x

2

x

3

. . .

g

7

suma := 0;

f

na sumę iloczynów x

1

+ x

1

x

2

+ . . .

g

8

„wyznacz S

1

na podstawie A

1

i ograniczeń”;

9

k := 1;

10

while S

k

= ∅ do

11

iloczyn := iloczyn *

|S

k

|;

12

suma := suma + iloczyn;

13

a

k

:= losowy element z S

k

;

14

f

nie musimy usuwać a

k

z S

k

, bo i tak nie będzie powrotu

g

15

k := k + 1;

f

następny „poziom”

g

16

„wyznacz S

k

na podstawie A

k

i ograniczeń”;

17

end while;

18

f

dotarliśmy do liścia, mamy oszacowanie liczby węzłów w tym eksperymencie

g

19

średnia := średnia + suma;

20

end for;

21

średnia := średnia / N ;

22

end.

104

Analiza algorytmów - ćwiczenia

7.8.

Drzewa gier i

α–β obcięcie

Inny wariant metody podziału i ograniczeń jest stosowany podczas budowania drzewa gier.

Drzewo gry jest to drzewo, które powstaje w wyniku sprawdzania metodą powrotów wszystkich

możliwych ciągów posunięć. Korzeniem drzewa jest początkowy stan gry, synami korzenia są wszystkie

możliwe stany, jakie mogą wystąpić po ruchu pierwszego gracza, synami tych węzłów są z kolei wszystkie

możliwe stany, które mogą wystąpić po odpowiadającym ruchu drugiego gracza itd.

7.7. Fragmenty drzewa gry w kółko i krzyżyk. Źródło: [1].

Na przykład, rysunek 7.7 przedstawia fragmenty drzewa gry w kółko i krzyżyk na planszy 3*3.

Drzewo pokazuje tylko synów nierównoważnych ze względu na obroty i symetrie.

Każdy liść drzewa gry odpowiada jednemu z możliwych zakończeń gry. W omawianym przypadku

będzie to zwycięstwo krzyżyka, zwycięstwo kółka lub remis.

Spróbujmy użyć tego drzewa do znalezienia strategii wygrywającej dla grającego krzyżykiem. Stra-

tegia wygrywająca to takie postępowanie, które doprowadzi do wygranej niezależnie od posunięć drugiego

gracza. Oczywiście nie zawsze istnieje taka strategia. Zbudowanie i analiza pełnego drzewa gry pozwala

odpowiedzieć na pytanie o istnienie takiej strategii.

Budujemy drzewo „z punktu widzenia” pierwszego gracza, grającego krzyżykami. Po zbudowaniu

drzewa przystępujemy do przypisywania wartości liściom tego drzewa. Każdemu z nich przypisujemy

wartość +1 w przypadku wygranej x,

−1 w przypadku przegranej x i 0 w przypadku remisu.

Wartości pozostałych węzłów wyznaczamy sukcesywnie począwszy od liście w kierunku korzenia

drzewa. Będą one oceniały wartość węzła z punktu widzenia gracza x, to znaczy będą mówiły, czy dla

stanu gry opisanego danym węzłem istnieje dla niego strategia wygrywająca (wtedy węzeł ma wartość

Rozdział 7: Wyszukiwanie wyczerpujące

105

+1), czy też istnieje strategia wygrywająca dla gracza o (wtedy węzeł ma wartość

−1), czy też nie istnieją

takie strategie (wtedy węzeł otrzyma wartość 0).

Dla węzła N o synach N

1

, N

2

, . . . , N

k

wartość v(N ) definiujemy w następujący sposób:

v(N ) =






max(v(N

1

), . . . , v(N

k

))

jeśli poziom węzła N jest nieparzysty

min(v(N

1

), . . . , v(N

k

))

jeśli poziom węzła N jest parzysty

Zakładamy więc, że gracz x jest inteligenty i zawsze starać się zmaksymalizować swoją wygraną. Prze-

ciwnik (o) również jest inteligentny i też stara się zmaksymalizować swoją wygraną, czyli zminimalizować

wygraną x. Jest to tzw. reguła mini-maksowa.

Przesuwamy się od liści w górę drzewa przypisując węzłom odpowiednie wartości, aż dotrzemy do

korzenia

2

.

Wyznaczenie wartości węzła jest istotne, ponieważ na podstawie tej wartości można ustalić, który

ruch (gałąź) należy wybrać. Przy wartości +1 nie ma wątpliwości, że kierując się w tę stronę dotrzemy

do liścia z naszą wygraną.

Okazuje się, że budując pełne drzewo gry dla gry w kółko i krzyżyk na planszy 3*3 i oceniając w

ten sposób węzły, uzyskamy wartość korzenia równą 0. Oznacza to, że nie istnieje strategia wygrywająca

dla żadnego z graczy. Gracze grając uważnie powinni zawsze doprowadzić do remisu, co czyni grę mało

interesującą.

Takie drzewo można budować dla wielu gier, na przykład dla szachów. Po dokonaniu wartościowania

liści tego drzewa i następnie wszystkich węzłów, można znaleźć odpowiedź na pytanie, czy istnieje stra-

tegia wygrywająca, a jeśli tak, to dla którego z graczy i w jaki sposób należy postępować, aby na pewno

wygrać. Niestety drzewo gry dla szachów jest tak duże, że (na razie) nie ma możliwości skonstruowania

go, a tym samym nie można dokonać oceny węzłów.

W takiej sytuacji pozostaje stosowanie kombinowanych rozwiązań heurystycznych. Zamiast budo-

wać pełne drzewo, konstruujemy tylko jego fragment od bieżącego stanu gry do takiej głębokości, jaką

da się praktycznie przeanalizować – np. kilku ruchów w przód. Na tym najniższym poziomie dokonujemy

wartościowania węzłów metodami heurystycznymi, tzn. oceniamy sytuację jako „bardzo dobrą”, „dobrą”,

„złą” itd., z punktu widzenia jednego z graczy. Ocenę wyrażamy jako liczbę z większego przedziału (nie

ograniczamy się tylko do

−1, 0 i +1). Ocena jest heurystyczna, tzn. dokonywana na podstawie reguł,

które wydają się sensowne osobie implementującej algorytm, ale nie wynikają ze ścisłej analizy. Następnie

węzły leżące powyżej tego poziomu są oceniane zgodnie z regułą mini-maksową, aż do węzła opisującego

bieżący stan gry. W ten sposób gracz orientuje się, jaka jest jego sytuacja i jak postąpić, aby dotrzeć do

węzła o najkorzystniejszej dla niego (największej) wartości.

Do obliczenia wartości wszystkich węzłów można oczywiście zastosować zwykłą metodę powrotów.

Lepsza (szybsza) jest jednak metoda nazywana α–β obcięciem, w której stosuje się technikę podziału i

ograniczeń do odcinania poddrzew z drzewa gry.

2

celowe jest przedstawienie fikcyjnego drzewa gry i opisanie go zgodnie z omawianą metodą

106

Analiza algorytmów - ćwiczenia

Wyznaczenie wartości związanej z danym węzłem daje informację na temat wartości, która będzie

przypisana jego ojcu. Jeśli ojciec znajduje się na poziomie, dla którego v(N ) oblicza się jako maksimum,

to wartość przypisana temu węzłowi jest dolną granicą wartości związanej z jego ojcem. Ta dolna granica

jest nazywana α-wartością. W symetrycznej sytuacji, kiedy obliaczane jest minimum, górną granicę

nazywa się β-wartością.

7.8. Ilustracja α–β obcięcia. Źródło: [1].

Rysunek 7.8 ilustruje tę technikę. Jeśi węzłowi d przypisywana jest wartość 3, to znaczy, że węzeł m

nie może mieć wartości większej niż 3. Jeśli więc okaże się, że leżący dwa poziomy niżej węzeł f ma wartość

5, a węzeł h w związku z tym wartość nie mniejszą niż 5, to nie ma sensu dalej analizować poddrzewa

h, bo i tak nie doprowadzi to do przypisania h wartości mniejszej niż 3. Taką sytuację nazywamy β-

odcięciem: występuje wtedy, kiedy pewien węzeł leżący dwa poziomy poniżej węzła z β-wartością ma

wartość większą niż β.

Analogicznie wygląda sytuacja dla poziomu, na którym obliczane jest maksimum. Węzeł m ma

wartość 3, a węzeł z wartość nie większą niż 2 (ponieważ wartość q jest równa 2). Wobec tego wartość

korzenia będzie równa co najmniej 3 i można pominąć fragment drzewa leżący poniżej z. Taką sytuację

nazywamy α-odcięciem.

Oszczędność w stosunku do normalnego wyszukiwania w dużym stopniu zależy od uporządkowania

Rozdział 7: Wyszukiwanie wyczerpujące

107

węzłów w drzewie.

7.9.

Przykład wyszukiwania wyczerpującego

Jednym z podręcznikowych przykładów problemu rozwiązywanego metodą wyszukiwania wyczerpującego

jest problem 8 hetmanów:

Rozmieścić na szachownicy 8 hetmanów w taki sposób, aby żaden z nich nie atakował innego.

Problemem tym zajmował się C. F. Gauss w 1850 roku, ale nie znalazł pełnego rozwiązania. Wy-

maga to bowiem nie analitycznego rozwiązania (w czym Gauss był biegły), ale po prostu wypróbowania

wszystkich możliwości. W czasach, kiedy nie istniały komputery, nawet takie niewielkie zadanie rzeczy-

wiście było wyczerpujące.

Algorytm rozwiązujący to zadanie metodą powrotów wygląda następująco:

1

procedure próbuj(i: integer);

2

var k: integer;

3

begin

4

„wyznacz możliwe pozycje hetmana w kolumnie i”;

5

for k := 1 to liczba pozycji do

6

„wybierz k-tego kandydata”;

7

if „dopuszczalny” then

8

„wstaw k-tego kandydata”;

9

if i < 8 then

10

próbuj(i+1);

11

else

12

„wydrukuj rozwiązanie”;

13

end if;

14

„usuń k-tego kandydata”;

15

end if;

16

end for;;

17

end.

Procedurę wywołujemy z parametrem i = 1. Algorytm podejmuje próby umieszczania hetmanów w

kolejnych kolumnach. Bieżące rozmieszczenie hetmanów może być przechowywane w zmiennej globalnej, a

możliwe pozycje hetmana w zmiennej lokalnej procedury. Wybór k-tego kandydata oznacza też usunięcie

go ze zbioru znalezionych kandydatów.

Algorytm znajduje 92 rozwiązania, których tylko 12 jest istotnie różnych. Pozostałe powstają przez

symetrie i obroty jednego z 12 rozwiązań.

108

Analiza algorytmów - ćwiczenia

Inne problemy, które mogą być rozwiązywane metodą wyszukiwania wyczerpującego, to szukanie

drogi skoczka na szachownicy

3

, problem komiwojażera itp.

7.10.

Sita

Sito jest techniką kombinatoryczną polegającą na generacji wszystkich potencjalnych rozwiązań proble-

mu, a następnie eliminacji tych elementów, które nie spełniają warunków zadania. Metody sitowe są

logicznym uzupełnieniem metod powrotów.

Klasycznym przykładem jest sito Eratostenesa

4

do znajdowania liczb pierwszych w zadanym prze-

dziale od 2 do N dla pewnego N .

W pierwszym kroku wypisujemy wszystkie liczby z interesującego nas przedziału (N = 14):

2,

3,

4,

5,

6,

7,

8,

9,

10, 11, 12, 13, 14

Pierwszą z lewej liczbą jest 2. Oznaczamy ją jako pierwszą i usuwamy pozostałe wielokrotności 2, czyli

co drugą liczbę zaczynając od czwórki:

2,

3,

5,

7,

9,

11,

13

Następną jeszcze nie skreśloną liczbą jest 3. Zaznaczamy ją jako pierwszą i usuwamy co trzecią zaczynając

od szóstki:

2,

3,

5,

7,

11,

13

Znaleźliśmy kolejną liczbę pierwszą: piątkę. Zaznaczamy ją jako pierwszą. W tym miejscu okazuje się, że

dalej nie musimy skreślać, ponieważ 5 >

√

N i wszystkie liczby złożone zostały już wcześniej skreślone

(co najmniej jeden z czynników każdej liczby złożonej nie większej od N jest nie większy od

√

N ).

Ostatecznie otrzymujemy:

2,

3,

5,

7,

11,

13

Jeśli elementy w zbiorze potencjalnych rozwiązań mogą być indeksowane liczbami naturalnymi i

w prosty sposób wyznaczane na podstawie indeksu, to nie ma potrzeby przechowywania w pamięci

wszystkich tych rozwiązań. Wystarczy zastosować tzw. wektor charakterystyczny, którym jest taki

3

dla szczególnych rozmiarów szachownicy istnieją lepsze metody

4

a nie Erastotenesa

Rozdział 7: Wyszukiwanie wyczerpujące

109

ciąg bitów, że i-ty bit jest równy 0, jeśli i-ty element zbioru nie jest rozwiązaniem, albo 1, jeśli i-ty

element zbioru jest rozwiązaniem. W ten sposób jeden bajt pamięci może przechować informację o ośmiu

elementach zbioru.

Sito Eratostenesa jest szczególnym przypadkiem sita modularnego. Sita modularne pozwalają

znajdować liczby całkowite z zadanego przedziału, które należą jednocześnie do wielu różnych ciągów

arytmetycznych.

Literatura

[1] Edward M. Reingold, Jurg Nievergelt, Narsingh Deo, Alorytmy kombinatoryczne, Państwowe Wy-

dawnictwo Naukowe, Warszawa 1985

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, WNT,

Warszawa 1997

Wersja 0.04 (2000-06-02, 2001-11-37) (PF)

110

Analiza algorytmów - ćwiczenia

Rozdział 8

Algorytmy zachłanne

111

112

Analiza algorytmów - ćwiczenia

Rozdział 9

Algorytmy grafowe

9.1.

Wprowadzenie

Grafy są często stosowaną strukturą danych w informatyce, a algorytmy na nich operujące należą do

podstawowych. W niniejszym rozdziale przedstawimy w skrócie sposoby reprezentowania grafów w pa-

mięci komputera. W dalszym ciągu sformułujemy kilka problemów związanych z grafami, a następnie

omówimy wybrane algorytmy ich rozwiązywania.

9.2.

Oznaczenia i pojęcia

Graf skierowany G (digraf) jest opisany parą (V, E), gdzie V jest skończonym zbiorem wierzchołków

grafu, a E jest relacją binarną w V . Elementy zbioru E nazywamy łukami grafu. W grafie nieskierowa-

nyn G = (V, E) zbiór E to zbiór nieuporządkowanych par wierzchołków. Każda taka para wierzchołków

określana jest mianem krawędzi grafu. Jeśli (u, v) jest łukiem digrafu, to mówimy, że wychodzi ona

z wierzchołka u i wchodzi do wierzchołka v. Jeśli jest ona krawędzią grafu nieskierowanego, to mówimy,

że jest incydentna (sąsiednia) z wierzchołkami u i v. Jeśli istnieje w grafie krawędź (u, v) to mówimy, że

wierzchołek v jest sąsiedni do wierzchołka u. Dla grafów nieskierowanych relacja sąsiedztwa jest syme-

tryczna, dla skierowanych nie musi być symetryczna. Stopniem wierzchołka w grafie nieskierowanym jest

liczba incydentnych z nim krawędzi. Dla wierzchołków grafów skierowanych definiuje się odpowiednio

stopień wyjściowy oraz stopień wejściowy, a także stopień, będący sumą stopnia wejściowego i stopnia

wyjściowego. Droga (ścieżka) o długości k z wierzchołka p do q w grafie G = (V, E) jest ciągiem wierz-

chołków

v

0

, v

1

, . . . , v

k

 takich, że p = v

0

, q = v

k

i (v

i−1

, v

i

)

∈ E dla i = 1, 2, . . . , k. Długość drogi jest

liczbą jej krawędzi. Droga zawiera wierzchołki i krawędzie. Droga jest prosta, jeśli wszystkie jej wierz-

chołki są różne. Poddroga drogi jest ciągiem kolejnych jej wierzchołków. W grafie skierowanym droga

113

114

Analiza algorytmów - ćwiczenia

v

0

, v

1

, . . . , v

k

 tworzy cykl, jeśli v

0

= v

k

oraz droga zawiera co najmniej jedną krawędź. Cykl jest pro-

sty, jeśli wszystkie wierzchołki v

1

, . . . , v

k

są różne. Pętla jest cyklem o długości 1. Cykl

v

0

, v

1

, . . . , v

k



oraz

v

1

, v

2

, . . . , v

k

, v

0

 to ten sam cykl. Graf skierowany nie zawierający pętli nazywamy prostym. Graf

nie zawierający cykli nazywamy acyklicznym. Graf nieskierowany jest spójny, jeśli pomiędzy każdą parą

wierzchołków istnieje co najmniej jedna droga. Mówimy, że wierzchołek v jest osiągalny z u, jeśli z wierz-

chołka u istnieje droga do v. Składowe spójne grafu to klasy abstrakcji wierzchołków w relacji „ jest

osiągalny z”. Inaczej mówiąc, składowe spójne to takie podzbiory wierzchołków i krawędzi grafu, że po-

między każdą parą wierzchołków należących do tego samego podzbioru istnieje co najmniej jedna droga.

Graf skierowany jest silnie spójny, jeśli każde dwa wierzchołki są osiągalne jeden z drugiego. Silne spójne

składowe grafu skierowanego to klasy abstrakcji wierzchołków w relacji „są wzajemnie osiągalne”. Graf

skierowany jest silnie spójny, jeśli ma dokładnie jedną silnie spójną składową. Dwa grafy G = (V, E)

i G



= (V



, E



) są izomorficzne („ jednakowego kształtu”), jeśli istnieje bijekcja f : V

→ V



taka, że

(u, v)

∈ E wtedy i tylko wtedy, gdy (f(u), f(v)) ∈ E



. Czyli można przenumerować wierzchołki grafu G

tak, aby były wierzchołkami grafu G



zachowując odpowiadające krawędzie w G i G



. Graf G



= (V



, E



)

jest podgrafem grafu G = (V, E), jeśli V



⊆ V i E



⊆ E. Podgraf G



grafu G jest podgrafem utworzonym

z V



, jeśli wszystkie krawędzie łączące w G wierzchołki ze zbioru V



znajdują się również w zbiorze

E



. Acykliczny graf nieskierowany nazywa się lasem. Spójny, acykliczny graf nieskierowany nazywa się

drzewem. Graf nieskierowany jest dwudzielny, jeśli zbiór jego wierzchołków V może zostać podzielony na

dwa rozłączne podzbiory V

1

i V

2

takie, że wierzchołki każdej krawędzi tego grafu należą odpowiednio do

podzbioru V

1

i V

2

.

9.3.

Metody reprezentacji grafów w pamięci

Przyjęto dwa podstawowe sposoby reprezentacji grafu G = (V, E) w pamięci komputera: przez listy

sąsiedztwa oraz macierz sąsiedztwa. Listy sąsiedztwa zapisane są w tablicy odsyłaczy Adj. Każda lista

odpowiada pojedynczemu wierzchołkowi. Na liście znajdują się numery wierzchołków sąsiednich z tym

wierzchołkiem. Porządek wierzchołków na listach sąsiedztwa jest dowolny. Macierz sąsiedztwa jest ma-

cierzą A =

{a

ij

} o wymiarach |V | × |V | taką, że a

ij

= 1 jeśli w grafie istnieje krawędź (i, j), a 0 jeśli nie

istnieje. Rys. 9.1 przedstawia opisy grafu nieskierowanego, natomiast rys. 9.2 opisy grafu skierowanego.

9.4.

Algorytmy wyznaczania najkrótszych dróg w grafie ważonym

Funkcja wagowa w : E

→ R przyporządkowuje każdej krawędzi grafu wagę o wartości rzeczywistej. Graf

z taką funkcją jest określany jako graf ważony lub sieć. Wagą (długością) drogi p =

v

1

, v

2

, . . . , v

k

 jest

Rozdział 9: Algorytmy grafowe

115

9.1. Dwie reprezentacje grafu nieskierowanego: (a) graf nieskierowany, (b) listy sąsiedztwa, (c) macierz

sąsiedztwa

9.2. Dwie reprezentacje grafu skierowanego: (a) graf skierowany, (b) listy sąsiedztwa, (c) macierz sąsiedz-

twa

suma wag tworzących ją krawędzi:

w(p) =

k



i=2

w(v

i−1

, v

i

)

Problem szukania najkrótszej drogi z wierzchołka i do j w grafie ważonym (skierowanym lub nie-

skierowanym) sprowadza się do znalezienia drogi prowadzącej z i do j o minimalnej wadze, nazywanej

również kosztem. Dróg takich może być więcej niż jedna.

Istnieją różne warianty algorytmów znajdujących najkrótsze drogi w grafie:



Najkrótsze drogi z jednym źródłem: wyróżniamy jeden wierzchołek s (nazywany źródłem, ang. sour-

ce) grafu G i szukamy najkrótszych dróg z tego wierzchołka do wszystkich pozostałych wierzchołków

grafu.



Najkrótsze drogi z jednym wierzchołkiem docelowym: wyróżniamy jeden wierzchołek docelowy t

(ang. target) grafu G i szukamy najkrótszych dróg prowadzących ze wszystkich pozostałych wierz-

chołków grafu do wierzchołka t. Zmieniając zwrot wszystkich łuków (w grafach skierowanych)

można ten problem sprowadzić do problemu najkrótszych dróg z jednym źródłem.



Najkrótsza droga między parą wierzchołków: szukamy najkrótszej drogi prowadzącej z wierzchołka

u do wierzchołka v. Rozwiązanie problemu najkrótszych dróg ze źródłem w u rozwiązuje również

ten problem. Okazuje się, że w pesymistycznym przypadku żaden algorytm znajdujący najkrótszą

116

Analiza algorytmów - ćwiczenia

drogę między parą wierzchołków nie jest szybszy od najlepszego algorytmu dla problemu z jednym

źródłem.



Najkrótsze drogi między wszystkimi parami wierzchołków: szukamy najkrótszych dróg dla wszyskich

par wierzchołków grafu G. Rozwiązanie problemu z jednym źródłem dla wszystkich wierzchołków

grafu rozwiązuje również ten problem, jednak istnieją efektywniejsze algorytmy.

9.5.

Algorytm Floyda-Warshalla

Algorytm Floyda-Warshalla (FW) służy do znajdowania najkrótszych dróg między wszystkimi parami

wierzchołków danego grafu skierowanego G = (V, E). Stosowane jest tu programowanie dynamiczne.

Wykorzystywany jest fakt, że każda poddroga najkrótszej drogi łączącej dwa wierzchołki grafu jest

również najkrótszą drogą łączącą końce poddrogi.

Problem znajdowania najkrótszych dróg między wszystkimi parami wierzchołków formułuje się

następująco:

Dane:



G = (V, E, d) - sieć skierowana (lub nieskierowana),



V =

{1, 2, . . . , n} - zbiór wierzchołków,



E

⊆ V × V - zbiór krawędzi,



d : E

→ R - funkcja długości (wag) krawędzi; funkcja ta jest opisywana macierzą długości (wag)

krawędzi D =

{d

ij

}, i, j ∈ V . Dodatkowo zakłada się, że:

– Długości krawędzi d

ij

mogą być ujemne, ale w grafie nie może być cykli o ujemnej dłu-

gości. Gdyby były, nie istniałyby najkrótsze drogi między pewnymi parami wierzchołków,

ponieważ droga rozszerzona o taki cykl zmniejszyłaby swoją długość i operację taką można

byłoby powtarzać nieskończenie wiele razy.

– Jeśli w grafie G nie ma krawędzi (i, j), to przyjmujemy, że d

ij

=

∞.

– Dla każdego d zachodzi d +

∞ = ∞ oraz min(d, ∞) = d.

Szukane:

Szukamy macierzy D

∗

=

{d

∗

ij

}, gdzie d

∗

ij

jest długością najkrótszej drogi prowadzącej od wierzchołka

i do wierzchołka j, i, j

∈ V .

Algorytm Floyda-Warshalla wyznacza ciąg macierzy

D

0

, D

1

, . . . , D

n

= D

∗

Rozdział 9: Algorytmy grafowe

117

takich, że D

n

jest macierzą długości najkrótszych dróg. Każda macierz D

k

, k = 1, 2, . . . , n jest wyzna-

czana następująco:

d

k

ij

= min(d

k−1

ij

, d

k−1

ik

+ d

k−1

kj

)

i, j

∈ V

dla k = 1, 2, . . . , n.

Macierz D

0

jest wyznaczana według zależności:

d

0

ij

=






0

gdy i = j,

d

ij

gdy i

= j.

Wartość d

k

ij

jest długością najkrótszej drogi od wierzchołka i do j nie przechodzącej przez żaden wierz-

chołek o numerze większym niż k, poza ewentualnie początkiem i końcem. Jest to krótsza z dwóch

następujących dróg:



najkrótszej takiej drogi nie przechodzącej przez żaden wierzchołek o numerze większym niż k

− 1,



najkrótszej drogi spośród dróg prowadzących od i do k, a następnie od k do j, nie przechodzących

między tymi wierzchołkami przez żaden wierzchołek o numerze większym niż k

− 1.

Algorytm przedstawia pseudokod 9.3.

Przykład:

Przykładowy graf skierowany i przebieg algorytmu FW przedstawiono na rysunku 9.4.

Złożoność algorytmu jest łatwa do wyznaczenia, wykonujemy n kroków dla macierzy n

× n, T (n) =

O(n

3

).

Powyższy algorytm można łatwo zmodyfikować tak, aby jednocześnie z szukaniem długości mini-

malnych dróg znajdował same drogi. Niech P =

{p

ij

} jest macierzą „następnych” wierzchołków drogi;

dokładniej: p

ij

jest drugim z kolei wierzchołkiem najkrótszej drogi prowadzącej z i do j.

Macierz P jest wyznaczana w następujący sposób:



Początkowo:

p

0

ij

=






j

gdy d

ij

= ∞,

0

gdy d

ij

=

∞.



W i-tej iteracji, jeśli

d

ik

+ d

kj

< d

ij

to przyjmujemy p

ij

:=p

ik

.

118

Analiza algorytmów - ćwiczenia

1

procedure FW;

2

begin

3

f

Dane: macierz długości krawędzi D =

{d

ij

}

g

4

f

Szukane: macierz długości najkrótszych dróg D =

{d

ij

}

g

5

for i := 1 to n do

6

for j := 1 to n do

7

if i = j then

8

d[i,j] := 0;

9

end if;

10

end for;

11

end for;

12

for k := 1 to n do

13

for i := 1 to n do

14

if d[i,k]

= ∞ then

15

for j := 1 to n do

16

d[i,j] := min(d[i,j],d[i,k]+d[k,j]);

17

end for;

18

end if;

19

end for;

20

end for;

21

end.

9.3. Algorytm Floyda-Warshalla

Rozdział 9: Algorytmy grafowe

119

d

1

2

3

1

2

8

5

2

3

∞ ∞

3

∞

2

∞

d

0

1

2

3

1

0

8

5

2

3

0

∞

3

∞ 2

0

d

1

1

2

3

1

0

8

5

2

3

0

8

3

∞ 2 0

d

2

1

2

3

1

0

8

5

2

3

0

8

3

5

2

0

d

3

1

2

3

1

0

7

5

2

3

0

8

3

5

2

0

9.4. Przykładowy przebieg algorytmu FW

Przykład:

Przykładowy graf nieskierowany o jednostkowych wagach krawędzi i wynikowe macierze D oraz P

przedstawiono na rys. 9.5.

Zawartość macierzy P przedstawiona na rys. 9.5 pozwala np. znaleźć najkrótszą drogę z wierzchołka

1 do wierzchołka 7. Element p

17

= 2 wskazuje, że przechodząc z wierzchołka 1 do 7 należy najpierw

skierować się do wierzchołka 2. Po przejściu do wierzchołka 2 pozostaje jeszcze do przejścia droga (2, 7).

Element p

27

= 4, a więc kolejnym wierzchołkiem drogi jest 4. Tam znajdujemy p

47

= 6, dalej p

67

= 7,

co oznacza, że z wierzchołka 6 trafiamy już bezpośrednio do końca drogi, tj. wierzchołka 7.

9.6.

Algorytm Dijkstry

Algorytm Dijkstry rozwiązuje problem najkrótszych dróg z jednym źródłem w ważonym grafie skierowa-

nym G = (V, E) w przypadku, gdy wagi wszystkich krawędzi są nieujemne. Algorytm jest podobny do

algorytmu znajdującego minimalne drzewo rozpinające metodą dołączania do już znalezionego fragmen-

tu drzewa kolejnych krawędzi tak, aby w każdym kroku drzewo było rozszerzane o tę krawędź, której

waga wnosi najmniej do wagi całego drzewa. Tutaj zostanie zdefiniowany początkowo pusty zbiór S, do

którego będą dołączane kolejno te wierzchołki, dla których da się już wyznaczyć najkrótszą drogę ze

źródła do wierzchołka. Dla wszystkich wierzchołków należących na danym etapie do zbioru S długość

drogi jest już wyznaczona i nie zmieni się do końca wykonywania algorytmu.

Tablica d przechowuje bieżące oszacowanie wagi najkrótszej drogi prowadzącej ze źródła s do danego

wierzchołka (d[v] jest oszacowaniem wagi drogi ze źródła do v). Tablica p przechowuje poprzedników na

120

Analiza algorytmów - ćwiczenia



















D

1

2

3

4

5

6

7

8

9

1

0

1

1

2

2

3

4

3

4

2

1

0

2

1

1

2

3

2

3

3

1

2

0

1

2

2

3

3

4

4

2

1

1

0

1

1

2

2

3

5

2

1

2

1

0

2

2

1

2

6

3

2

2

1

2

0

1

2

2

7

4

3

3

2

2

1

0

1

1

8

3

2

3

2

1

2

1

0

1

9

4

3

4

3

2

2

1

1

0

P

1

2

3

4

5

6

7

8

9

1

0

2

3

2

2

2

2

2

2

2

1

0

1

4

5

4

4

5

5

3

1

1

0

4

4

4

4

4

4

4

2

2

3

0

5

6

6

5

6

5

2

2

4

4

0

4

8

8

8

6

4

4

4

4

4

0

7

7

7

7

6

6

6

6

8

6

0

8

9

8

5

5

5

5

5

7

7

0

9

9

8

8

7

7

8

7

7

8

0

9.5. Graf nieskierowany o jednostkowych wagach krawędzi i wynikowe macierze D i P

drodze prowadzącej ze źródła do wierzchołków grafu (p[v] jest poprzednim w stosunku do v wierzchołkiem

na chwilowo najkrótszej drodze ze źródła do v).

W przedstawionym dalej algorytmie występuje operacja relaksacji, nazywana też osłabianiem ogra-

niczeń. Z każdym wierzchołkiem v

∈ V związany jest atrybut d[v], którego wartość jest zawsze górnym

ograniczeniem wagi najkrótszej drogi ze źródła s do wierzchołka v. Wielkość d[v] nazywana jest osza-

cowaniem wagi najkrótszej drogi. Relaksacja krawędzi (u, v) przy źródłowym wierzchołku s polega na

sprawdzeniu, czy przechodząc przez wierzchołek u, można znaleźć krótszą od dotychczasowej najkrót-

szej drogi z s do v i, jeśli taka możliwość istnieje, odpowiedniej aktualizacji d[v] oraz p[v]. Ewentualna

aktualizacja polega na zmniejszeniu oszacowania wagi najkrótszej drogi d[v] oraz zmianie poprzedni-

ka p[v]. Relaksacja krawędzi (u, v) jest realizowana przez procedurę relaksacja(u,v) przedstawioną jako

pseudokod 9.6..

Przykładowo, jeśli d[u] = 5, d[v] = 9 i krawędź (u, v) ma wagę 2, to po przeprowadzeniu relaksacji

relaksacja(u,v) zmniejszy się d[v] do 7, a p[v] stanie się równe u. Gdyby natomiast przed relaksacją d[v]

byłoby równe 6, to relaksacja niczego nie zmieni.

Początkowo przyjmujemy, że dla wszystkich wierzchołków v

∈ V poza źródłem d[v] = ∞, dla źródła

s ustalamy d[s] = 0. Dla wszystkich v

∈ V ustalamy p[v] = 0, co oznacza brak poprzednika (numer 0 nie

jest numerem żadnego wierzchołka ze zbioru V ).

W algorytmie Dijkstry pamiętany jest zbiór S zawierający te wierzchołki, dla których wagi naj-

Rozdział 9: Algorytmy grafowe

121

1

procedure relax(u,v);

2

begin

3

f

u,v: nr wierzchołków

g

4

if d[u]+waga(u,v) < d[v] then

5

d[v] := d[u]+waga(u,v);

6

p[v] := u;

7

end if;

8

end.

krótszych dróg ze źródła s zostały już obliczone. Początkowo zbiór S jest pusty. Następnie wykonywane

są wielokrotnie następujące kroki:



wybór wierzchołka u nie należącego do S o minimalnym oszacowaniu wagi najkrótszej drogi,



dodanie wierzchołka u do S



wykonanie relaksacji dla wszystkich krawędzi o początku w wierzchołku u, czyli wychodzących z u.

Do pamiętania elementów zbioru V

− S można użyć kolejki priorytetowej, oznaczonej w przed-

stawianym algorytmie przez Q. Kluczami są tu wartości d. W implementacji zakłada się, że graf jest

reprezentowany w pamięci przez listy sąsiedztwa. Algorytm przedstawia pseudokod 9.6..

1

f

s: źródło

g

2

procedure dijkstra(V,E,s);

3

begin

4

d[v] :=

∞ dla v należących do V;

5

d[s] := 0;

6

p[v] := 0 dla v należących do V;

7

S := zbiór pusty;

8

Q := wszystkie wierzchołki ze zbioru V;

9

while kolejka Q nie jest pusta do

10

u := wierzchołek z Q o minimalnej wartości d;

11

S := S +

f

u

g

;

12

for lista wierzchołków v sąsiadujących z u

13

relax(u,v);

14

end for;

15

end while;

16

end.

Przykład:

122

Analiza algorytmów - ćwiczenia

Przykładowy graf skierowany i przebieg algorytmu Dijkstry przedstawiono na rys. 9.6.

9.6. Przykładowy przebieg algorytmu Dijkstry. Źródłem jest wierzchołek s. Na rys. (a) tylko on ma

ustaloną wagę drogi, ale jeszcze nie należy do zbioru S. Jest wybierany jako wierzchołek o minimalnej

wadze spoza S i dołączany do S, co uwidoczniono na rys. (b). Wierzchołki należące do S oznaczono

na czarno. Teraz dokonywana jest relaksacja krawędzi wychodzących z s, a więc (s, u) oraz (s, x).

Pierwsza relaksacja powoduje przypisanie wierzchołkowi u wagi 10, ponieważ idąc do u poprzez s

krawędzią o koszcie 10 uzyskujemy łączny koszt 0 + 10 = 10, a 10 <

∞. Podobnie wierzchołek x

uzyskuje wagę 5. W kolejnym obiegu głównej iteracji znowu szukamy wierzchołka z minimalną wagą

spośród wierzchołków nie należących do S. Tym razem jest nim wierzchołek x o wadze 5. Dołączamy

go do zbioru S, co przedstawia rys. (c). Dokonujemy relaksacji krawędzi wychodzących z wierzchołka

x, w wyniku czego zmieniają się wagi wierzchołków u, v, y. W kolejnym obiegu wierzchołkiem o

minimalnej wadze, nie należącym do S jest y itd. Rys. (f) przedstawia ostateczny wynik działania

algorytmu, wszystkie wierzchołki należą do S.

Złożoność algorytmu

Oznaczmy liczbę wierzchołków w zbiorze V przez n, a liczbę krawędzi w zbiorze E przez e. I stotna

dla szybkości działania algorytmu Dijkstry jest implementacja kolejki priorytetowej Q. W najprost-

szym przypadku może ona być zaimplementowana jako tablica jednowymiarowa przeszukiwana liniowo.

Wtedy jednak każda operacja wyboru minimalnego elementu trwa O(n). Każdy z n wierzchołków gra-

fu przechodzi przez tę kolejkę, więc łącznie wybory zajmują czas O(n

2

). Każda z n list sąsiedztwa jest

analizowana dokładnie raz, jeden raz są też analizowane wszystkie krawędzie sąsiadujące z każdym wierz-

Rozdział 9: Algorytmy grafowe

123

chołkiem. Czyli każda krawędź jest analizowana jeden raz, a więc ostatecznie algorytm działa w czasie

O(n

2

+ e) = O(n

2

), ponieważ w pesymistycznym przypadku liczba krawędzi jest rzędu O(n

2

)).

Dla grafów rzadkich efektywniejsze rozwiązanie uzyskuje się implementując kolejkę priorytetową

za pomocą kopca. Taki algorytm nazywany jest czasem zmodyfikowanym algorytmem Dijkstry. Kopiec

budowany jest w czasie O(n). Dalej następuje instrukcja iteracyjna wykonywana n razy (dla wszyst-

kich wierzchołków). Każda operacja wyboru minimalnego elementu zabiera czas O(log n), jest to czas

potrzebny na przywrócenie własności kopca. Łącznie operacje wyboru minimalnych elementów zajmują

czas O(n log n). Dla każdej krawędzi jest przeprowadzana operacja relaksacji, której wynikiem może być

zmiana pewnej wartości w kopcu. Przywrócenie własności kopca zajmuje czas O(log n). Krawędzi jest e,

więc ten etap zajmie czas O(e log n), a cały algorytm O(log n(n + e)).

Stosując tzw. kopiec Fibonacciego można uzyskać dla operacji przywracania własności kopca w

całym algorytmie czas O(1) i łączną złożoność O(n lg n + e).

Literatura

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, WNT,

Warszawa 1997

124

Analiza algorytmów - ćwiczenia

Rozdział 10

Funkcje mieszające

10.1.

Wprowadzenie

W wielu zastosowaniach wykorzystuje się struktury danych, na których są wykonywane tylko operacje

słownikowe: wstaw, usuń i szukaj. W kompilatorach języków programowania wykorzystuje się słowniki

symboli, w których kluczami są dowolne ciągi znaków odpowiadające identyfikatorom. Do reprezentacji

słowników doskonale nadają się tablice z mieszaniem będące uogólnieniem zwyczajnych tablic. Stoso-

wanie tablic z mieszaniem często jest określanie mianem: mieszania, rozpraszania lub hashowania (ang.

hashing). Mieszanie jest bardzo efektywną metodą, średni czas działania podstawowych operacji słowni-

kowych na tablicach z mieszaniem wynosi O(1)

10.2.

Tablice z adresowaniem bezpośrednim

Adresowanie bezpośrednie jest bardzo prostą i skuteczną metodą. Załóżmy, że wykorzystujemy słownik,

którego elementy mają klucze należące do uniwersum U =

{0, 1, 2, 3, ...m − 1}, gdzie m nie jest zbyt

duże. Przyjmijmy, że żadne dwa elementy nie mają identycznych kluczy. W takim przypadku słownik

możemy zrealizować za pomocą tablicy (z adresowaniem bezpośrednim) T [0..m

− 1], którą adresujemy

wartościami kluczy należącymi do uniwersum U .

Implementacja operacji słownikowych w takim przypadku jest trywialna:

125

126

Analiza algorytmów - ćwiczenia

1

procedure wstaw adrbez(T, x);

2

begin

3

T [key(x)] := x;

4

end.

10.1. Algorytm wstawiania do tablicy z adresowaniem bezpośrednim

1

procedure usuń adrbez(T, x);

2

begin

3

T [key(x)] := nil;

4

end.

10.2. Algorytm usuwania z tablicy z adresowaniem bezpośrednim

10.3.

Tablice z mieszaniem

Adresowanie bezpośrednie ma poważną wadę: jeśli uniwersum kluczy U jest zbyt duże, to przechowy-

wanie w pamięci komputera tablicy T o rozmiarze

|U| może być nierealne. Dodatkowo zbiór K kluczy

elementów słownika może być tak mały, że większość pamięci zarezerwowanej dla tablicy T nie będzie

wykorzystana. Rozwiązaniem tego problemu jest zastosowanie tablicy z mieszaniem. W tablicy z adre-

sowaniem bezpośrednim element o kluczu k zostaje umieszczony na pozycji o indeksie k, natomiast w

tablicy z mieszaniem element ten zostaje umieszczony na pozycji o indeksie h(k). Funkcję h(k) nazywamy

funkcją mieszającą, która odwzorowuje uniwersum kluczy U na zbiór indeksów tablicy:

h : U

−→ {0, 1, 2, ...m − 1}

Ogromne oszczędności pamięci uzyskane dzięki zastosowaniu tablicy z mieszaniem okupione są

niebezpieczeństwem wystąpienia kolizji, tj. sytuacji, w której funkcja mieszająca przypisze dwu różnym

kluczom tę samą pozycję w tablicy. Oczywiście istnieją efektywne metody przezwyciężania kolizji, jednak

najlepiej byłoby w ogóle do kolizji nie dopuścić. Możemy to osiągnąć odpowiednio konstruując funkcję

mieszającą h(k).

Jeżeli zbiór K kluczy obiektów podlegających mieszaniu jest stały i z góry zadany, to można dla

takiego zbioru opracować doskonałą funkcję mieszającą h

d

(k) Funkcja h(k) jest doskonała jeśli jest

różnowartościowa:

1

procedure szukaj adrbez(T, k);

2

begin

3

return T [k];

4

end.

10.3. Algorytm szukania w tablicy z adresowaniem bezpośrednim

Rozdział 10: Funkcje mieszające

127

∀

k

1

,k

2

∈K

k

1

= k

2

=

⇒ h(k

1

)

= h(k

2

)

Przy użyciu takiej funkcji możliwe jest wyszukanie dowolnego obiektu w tablicy lub stwierdzenie,

że on w niej nie występuje w dokładnie jednej próbie. Doskonała funkcja mieszająca jest minimalna

jeżeli wszystkie wartości z

{0, 1, 2, ...m − 1} są wykorzystane, czyli:

|K| = n

Dla zbioru nazw funkcji standardowych języka BASIC: K =

{sin, cos, tan, atn, sqr, exp, log,

abs, int, sgn, rnd

} można metodą „prób i błędów” wyznaczyć minimalną doskonałą funkcję mieszającą

postaci:

a. h

d

(x

1

, x

2

, x

3

) = ˆ

x

1

+ ˆ

x

1

+ ˆ

x

2

b. h

d

(x

1

, x

2

, x

3

) = ˆ

x

1

+ ˆ

x

2

+ ˆ

x

2

c. h

d

(x

1

, x

2

, x

3

) = ˆ

x

2

+ ˆ

x

2

+ ˆ

x

3

d. h

d

(x

1

, x

2

, x

3

) = ˆ

x

2

+ ˆ

x

3

+ ˆ

x

3

gdzie x

1

, x

2

, x

3

oznaczają kolejne znaki słowa, natomiast ˆ

x

1

, ˆ

x

2

, ˆ

x

3

to kody znaków. Wyznaczenie funkcji

mieszającej oznacza przyporządkowanie znakom odpowiednich kodów. Zauważmy, że 0

ˆx

i

m−1 = 10

dla każdego znaku x

i

.

ad. a.h

d

(x

1

, x

2

, x

3

) = ˆ

x

1

+ ˆ

x

1

+ ˆ

x

2

Sprawdźmy jakie znaki występują na pozycjach 1 i 2:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

1 2

1

1

1

1

1 3 1

2 1 1

1

1

2 2

1

1

1

Rozwiązaniem będzie tablica kodów znaków występujących na pozycji 1 i 2:

A B C E G I L N O Q R S T X

liczba wystąpień 3 1 1 1 1 2 1 2 2 1 1 3 2 1

kod

Tym znakom, które często występuja przypisujemy 0, na ich podstawie i tak trudno rozróżnić słowa,

a więc:

128

Analiza algorytmów - ćwiczenia

A,I,N,O,S,T=0 T=1

N=3

C=2 Q=5 E=3,X=0 L=4 B=7 G=10 R=3

SIN

2S+I=0

0

COS 2C+O=?

4

4

TAN 2T+A=0(bląd) 2T+A=2

2

ATN

2A+T=1

1

SQR

2S+Q=?

5

5

EXP

2E+X=?

6

6

LOG

2L+O=?

8

8

ABS

2A+B=?

7

7

INT

2I+N=0(błąd) 2I+N=3

3

SGN

2S+G=?

10

10

RND

2R+N=?

9

9

Rozwiązaniem jest otrzymana tablica kodów znaków występujących na pozycji 1 i 2:

A B C E G I L N O Q R S T X

kod 0 7 2 3 10 0 4 3 0 5 3 0 1 0

ad. c.h

d

(x

1

, x

2

, x

3

) = ˆ

x

2

+ ˆ

x

2

+ ˆ

x

3

Sprawdźmy jakie znaki występują na pozycjach 2 i 3:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

2 1 1

1

1

2 2

1

1

1

3

1

1

4

1

1 2 1

Liczba wystąpień znaków na pozycjach 2 i 3:

A B D G I N O P Q R S T X

liczba wystąpień 1 1 1 2 1 6 2 1 1 1 2 2 1

kod

Tym znakom, które często występuja przypisujemy 0, na ich podstawie i tak trudno rozróżnić słowa,

a więc:

G,N,O,S,T=0

N=3

G=2

I=3 A=1 Q=1,R=2 X=0,P=1 B=4 D=4

SIN

2I+N=?

9

9

COS 2O+S=0

0

TAN 2A+N=?

5

5

ATN 2T+N=0(błąd) 2T+N=3

3

SQR

2Q+R=?

4

4

EXP

2X+P=?

1

1

LOG

2O+G=0(błąd) 2O+G=2

2

ABS

2B+S=?

8

8

INT

2N+T=6

6

SGN

2G+N=7

7

RND

2N+D=?

10

10

Rozdział 10: Funkcje mieszające

129

Rozwiązaniem jest otrzymana tablica kodów znaków występujących na pozycji 1 i 2:

A B D G I N O P Q R S T X

kod 1 4 4 2 3 3 0 1 1 2 0 0 0

b. h

d

(x

1

, x

2

, x

3

) = ˆ

x

1

+ ˆ

x

2

+ ˆ

x

2

Stosując metodę „prób i błędów” intuicyjnie postępowaliśmy według zasad wyszukiwania wyczerpujące-

go. Spróbujmy zastosować następującą wersję wyszukiwania wyczerpującego:

A S I N O T B C E G L Q R X S C T A S E L A I S R 1

3 3 2 2 2 2 1 1 1 1 1 1 1 1

I O A T Q X O B N G N 2

N S N N R P G S T N D 0

0 0 0 0

0

0

1 0 0

0

2

1

1 2

2

2 4

3 0

3 6

0

1

2

2 0

0

4

1 0 0

1

0

1

2

2

4

3

6

4 0

0

8

5 0

0

5

5 0

10

2

5 0

0

7

10

10

1 0

4 0

5 0

5 0

5 0

4

9

Podkreślenie oznacza wystąpienie kolizji.

Rozwiązaniem jest otrzymana tablica kodów znaków:

A S I N O T B C E G L Q R X

kod 0 0 0 1 0 2 3 3 1 4 5 5 5 4

Kolejność znaków, dla których wyszukujemy kody ma istotne znaczenie dla przebiegu wyszukiwania.

W powyższym przykładzie decyduje częstotliwość występowania znaków na znaczących pozycjach w

zbiorze słów. Inna metoda wyznaczenia kolejności znaków polega na przypisaniu znakom odpowiednich

wag:

waga znaku

=



współczynnik pozycji

× liczba wystąpień na pozycji

130

Analiza algorytmów - ćwiczenia

dla funkcji postaci:

h

d

(x

1

, x

2

, x

3

) = ˆ

x

1

+ ˆ

x

1

+ ˆ

x

2

= 2

· ˆx

1

+ 1

· ˆx

2

+ 0

· ˆx

3

współczynnik znaku na pozycji pierwszej wynosi 2, na pozycji drugiej 1, trzeciej 0.

Obliczamy tabelę wag:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

1

2

1

1

1

1

1 3 1

2

1 1

1

1

2 2

1

1

1

waga 5 1 2

2

1

3

2

2 2

1 2 6 3

1

Następnie sortujemy nie rosnąco:

S A I T C E L N O R B G Q X

waga 6 5 3 3 2 2 2 2 2 2 1 1 1 1

Następnie stosujemy wyszukiwanie wyczerpujące, tak jak w poprzednim przykładzie:

S A I T C E L N O R B G Q X S C T A S E L A I S R 2

6 5 3 3 2 2 2 2 2 2 1 1 1 1

I O A T Q X O B N G N 1

N S N N R P G S T N D 0

0 0 0 0

0

0

1 0 0 0 0

2 1

0

1

1

2

2

3 0

0

3

10

1 0

0

1

1

2

2

3 0

0

2

3

1

1

3

2

2

4

3

3

5

4 0

4

6

0

4 0

0

8

5 0

5

0

7 0

0

7

9 0

9 0

10

10

Otrzymujemy tablicę kodów znaków:

S A I T C E L N O R B G Q X

kod 0 0 0 1 0 0 1 3 4 4 5 7 9 10

Pewien wpływ na proces wyszukiwania ma kolejność słów, dla których sprawdzamy kolizje. Kolej-

Rozdział 10: Funkcje mieszające

131

ność ta może zostać wyznaczona na podstawie wagi poszczególnych słów.

waga słowa =



współczynnik pozycji

× waga znaku

SIN

COS TAN ATN SQR EXP LOG ABS

INT

SGN RND

2

·6+3 2·2+2 2·3+5 2·5+3 2·6+1 2·2+1 2·2+1 2·5+1 2·3+2 2·6+1 2·2+1

15

6

11

13

13

5

6

11

8

13

6

Następnie stosujemy wyszukiwanie wyczerpujące, jak wyżej:

S A I T C E L N O R B G Q X S A S S T A I C L R E 2

6 5 3 3 2 2 2 2 2 2 1 1 1 1

I T Q G A B N O O N X 1

N N R N N S T S G D P 0

10.4.

Metody przezwyciężania kolizji

10.4.1.

Mieszanie otwarte - metoda „łańcuchowa”

Najprostszą metodą rozwiązywania kolizji jest metoda „łańcuchowa”. W metodzie łańcuchowej wszystkie

elementy, którym odpowiada ta sama pozycja w tablicy, umieszczone zostają na jednej liście. Początek

listy przechowywany jest w tablicy na wskazanej pozycji.

1

procedure wstaw miesz(T, x);

2

begin

f

wstaw x na początku listy T[h(key(x))]

g

3

end.

10.4. Algorytm wstawiania do tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania kolizji

1

procedure usuń miesz(T, x);

2

begin

f

usuń x z listy T[h(key(x))]

g

3

end.

10.5. Algorytm usuwania z tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania kolizji

Wstawianie elementów działa w czasie O(1) natomiast wyszukiwanie i usuwanie elementów działa

w czasie O(α), gdzie α nazywamy współczynnikiem zapełnienia:

α =

liczba elementów w tablicy

rozmiar tablicy

Jeżeli liczba elementów w tablicy z mieszaniem jest co najmniej proporcjonalna do rozmiaru tablicy,

to średni czas wyszukiwania i usuwania jest ograniczony przez stałą.

liczba element

ów w tablicy = O(rozmiar tablicy) =

⇒ α =

O(rozmiar tablicy)

rozmiar tablicy

= O(1)

132

Analiza algorytmów - ćwiczenia

1

procedure szukaj miesz(T, k);

2

begin

f

wyszukaj element o kluczu k na liście T[h(k)]

g

3

end.

10.6. Algorytm szukania w tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania kolizji

10.4.2.

Mieszanie zamknięte

Kolejna metoda rozwiązywania kolizji określana jest mianem mieszania zamkniętego. W tej metodzie

wszystkie elementy przechowywane są wprost w tablicy. W odróżnieniu od metody „łańcuchowej” nie

ma żadnych dodatkowych list, żadne elementy nie są przechowywane poza tablicą. Wynika stąd, że dla

mieszania zamkniętego współczynnik zapełnienia nigdy nie przekroczy 1, α

1 W mieszaniu zamkniętym

funkcja mieszająca zwraca ciąg wartości, permutację wszystkich pozycji w tablicy. W celu wstawienia

elementu do tablicy sprawdzamy kolejne pozycje z ciągu zwróconego przez funkcję mieszająca, aż do

znalezienia wolnej pozycji. Wyszukiwanie elementów polega na sprawdzeniu wszystkich pozycji tablicy

w kolejności określonej przez funkcję mieszającą. Zmodyfikowana funkcja mieszająca będzie teraz dwu-

argumentowa: h : U

× {0, 1, 2, ...m − 1} −→ {0, 1, 2, ...m − 1} h(k, i), gdzie k jest kluczem, a i określa

liczbę kolizji.

1

procedure wstaw zamk(T, x);

2

begin

3

i := 0;

4

repeat

5

j := h(key(x), i);

6

if T[j] = nil then

7

T[j] := k;

8

return;

9

end if;

10

i := i + 1;

11

until i=m;

f

błąd przepełnienie tablicy

g

12

end.

10.7. Algorytm wstawiania do tablicy z mieszaniem zamkniętym

Konstruując funkcję mieszającą dla mieszania zamkniętego dbamy aby, kolejność zwracanych po-

zycji zależała od wartości klucza. Zazwyczaj stosuje się jedną z trzech postaci funkcji mieszających:

Rozdział 10: Funkcje mieszające

133

1

procedure usuń zamk(T, x);

2

begin

3

i := 0;

4

repeat

5

j := h(key(x), i);

6

if T[j] = x then

7

T[j] := nil;

8

return;

9

end if;

10

i := i + 1;

11

until i=m;

f

błąd brak elementu

g

12

end.

10.8. Algorytm usuwania z tablicy z mieszaniem zamkniętym

1

procedure szukaj zamk(T, k);

2

begin

3

i := 0;

4

repeat

5

j := h(k, i);

6

if key(T[j]) = k then

7

return T[j];

8

end if;

9

i := i + 1;

10

until i=m;

f

błąd brak elementu

g

11

end.

10.9. Algorytm szukania w tablicy z mieszaniem zamkniętym

134

Analiza algorytmów - ćwiczenia



liniowa

h(k, i) = (h

1

(k) + i) mod m



kwadratowa

h(k, i) = (h

1

(k) + c

1

· i + c

2

· i

2

) mod m



dwukrotna

h(k, i) = (h

1

(k) + i

· h

2

(k)) mod m

Dla danej funkcji mieszającej h(k, i) = (k + i) mod m podaj postać tablicy mieszającej po wpro-

wadzeniu do niej następującej sekwencji kluczy: 11, 6, 88, 142, 23, 37, 96. Wyznaczyć liczbę prób, jaka

była potrzebna do wprowadzenia podanych kluczy do tablicy oraz spodziewaną liczbę prób wyznaczoną

teoretycznie.

próby

1

2

3

4

5

6

11

4

6

6

88

4

5

142

2

23

2

3

37

2

3

4

5

6

0

96

5

6

0

1

Wykonano 17 prób i otrzymano następujące wypełnienie tablicy:

0

37

1

96

2

142

3

23

4

11

5

88

6

6

Średnia liczba prób wstawienia i-ego klucza wynosi: E

śr

(i) =

1

1−α

=

1

1−

i−1

m

Średnia suma wykonanych prób:

7



i=1

E

śr

(i)

≈ 18, 15

Rozdział 10: Funkcje mieszające

135

10.5.

Zadania

1. Dla danej funkcji mieszającej h(k, i) = (k + i + i

2

) mod m podaj postać tablicy mieszającej po

wprowadzeniu do niej następującej sekwencji kluczy: 44, 16, 39, 105, 23, 4, 80. Wyznaczyć liczbę

prób, jaka była potrzebna do wprowadzenia podanych kluczy do tablicy oraz spodziewaną liczbę

prób wyznaczoną teoretycznie.

Literatura

[1] Cormen, T.H., Leiserson C.E., Rivest R.L.: Wprowadzenie do algorytmów. Wydawnictwa Naukowo-

Techniczne, Warszawa 1997.

[2] Wirth, N.: Algorytmy + struktury danych = programy. Wydawnictwo Naukowo-Techniczne, War-

szawa 2000.

[3] Czech, Z.J.: Analiza algorytmów – materiały dydaktyczne, Gliwice, luty 1997.

Wersja 0.01 (2001-12-20) (AS)

136

Analiza algorytmów - ćwiczenia

Rozdział 11

Generowanie obiektów

kombinatorycznych

11.1.

Wprowadzenie

W wielu algorytmach zachodzi konieczność generowania i sprawdzenia wszystkich albo wybranych ele-

mentów pewnej klasy obiektów kombinatorycznych. W tym rozdziale przedstawiono metody generacji

permutacji, podzbiorów i kombinacji. Algorytmy generujące obiekty kombinatoryczne można podzielić na

trzy klasy:



generujące wszystkie obiekty danej klasy, każdy dokładnie jeden raz,



generujące losowy obiekt danej klasy w taki sposób, aby prawdopodobieństwo generowania każdego

obiektu było jednakowe,



generujące wybrany (k-ty) obiekt danej klasy.

Optymalny czas wykonania algorytmu generującego wszystkie obiekty danej klasy powinien być

rzędu liczby tych obiektów, tj. mocy zbioru tych obiektów. Taki algorytm nazywany jest liniowym. Czas

generacji pojedynczego obiektu nie powinien zależeć od jego numeru n. Wygenerowanie n-tego obiektu

jest zwykle bardziej kłopotliwe niż sukcesywne generowanie wszystkich obiektów.

Algoryty generujące wszystkie obiekty kombinatoryczne danej klasy składa się z reguy z trzech faz:



inicjalizacji, połączonej z wygenerowaniem pierwszego obiektu,



przetworzenia wygenerowanego obiektu,



o ile to możliwe, przekształcania bieżącego obiektu w następny.

137

138

Analiza algorytmów - ćwiczenia

1

procedure generator;

2

begin

3

inicjalizacja(obiekt);

4

while not (ostatni element(obiekt)) do

5

przetwórz(obiekt);

f

wykonanie żądanych operacji na obiekcie

g

6

przekształć na następny(obiekt);

7

end while;

8

end.

Ogólną postać takich algorytmów przedstawia pseudokod 11.1..

Algorytmy generujące wszystkie obiekty mogą je generować w różnych uporządkowaniach. Jeśli

różnice między kolejnymi obiektami są minimalne, to algorytmy takie nazywane są algorytmami mini-

malnych zmian. Inne mogą generować obiekty uporządkowane leksykograficznie.

11.2.

Generowanie permutacji

Permutacje należą do często generowanych obiektów kombinatorycznych. Dowolną permutację elementów

zbioru

{a

1

, a

2

, . . . , a

n

} można zapisać jako ciąg indeksów tych elementów, czyli permutację zbioru liczb

naturalnych

{1, 2, . . . , n}. Dlatego w dalszym ciągu omówione zostaną algorytmy generujące właśnie

permutacje liczb naturalnych, co nie zmniejsza ogólności rozwiązania problemu.

11.2.1.

Permutacje w porządku minimalnych zmian

Minimalną zmianą prowadzącą do przekształcenia jednej permutacji w inną, jest pojedyncza transpozycja,

czyli zamiana pozycji pary elementów. Permutacje n elementów w takim porządku generuje się za pomocą

następującej metody rekurencyjnej:



Dla n = 1 permutacją jest (1).



Dla n > 1 tworzymy uporządkowaną listę permutacji n

− 1 elementów i oznaczamy je przez P

i

i = 1, . . . , (n

− 1)!.



Tworzymy uporządkowaną listę permutacji n elementów generując n nowych permutacji z każdej

permutacji P

i

przez wstawianie liczby n między elementy P

i

. Miejsc, w które można wstawić ten

nowy element jest n. Dla nieparzystych i element n wstawiamy od prawej do lewej strony P

i

, dla

parzystych od lewej do prawej.

Rozdział 11: Generowanie obiektów kombinatorycznych

139

Na rys. 11.1 przedstawiono przykładowy przebieg algorytmu dla n = 4.

Taka procedura generuje permutacje w porządku minimalnych zmian metodą rekurencyjną, nie

znajdujc bezporednio tych zmian (tzn. wynikiem działania algorytmu są permutacje, a nie numery ele-

mentów do zamiany). Jest również możliwe iteracyjne generowanie permutacji.

11.2.2.

Permutacje w porządku leksykograficznym

Przyjmujemy, że permutacja (a

i

1

, a

i

2

, . . . , a

i

n

) poprzedza leksykograficznie permutację (a

j

1

, a

j

2

, . . . , a

j

n

)

wtedy i tylko wtedy, gdy dla pewnego k, 1

k
n, i

p

= j

p

dla 1

p < k i i

k

= j

k

. Na przykad w przy-

padku permutacji cyfr porządek leksykograficzny to taki porządek, w którym permutacje traktowane jako

reprezentacje liczb naturalnych uporządkowane są rosnąco. Dla trzech cyfr 1, 2, 3 będzie to porządek

123, 132, 213, 231, 312, 321.

Najistotniejszą częścią algorytmu generującego wszystkie permutacje jest sposób przekształcenia

bieżącej permutacji w następną. Można opisać ten sposób następująco:



Oznacz kolejne elementy bieżącej permutacji przez (a

1

, a

2

, . . . , a

n

).



Przeglądając elementy od prawej strony, tzn. od a

n

w kierunku a

1

, znajdź pierwszą pozycję, dla

której a

i

< a

i+1

.



Przeglądając elementy położone na prawo od a

i

znajdź element a

j

taki, że jest on najmniejszy

spośród elementów większych od a

i

.



Zamień miejscami element a

i

z a

j

.



Odwróć kolejność elementów (a

i+1

, . . . , a

n

). Elementy te zostaną uporządkowane rosnąco. (indeks

i nie ulega zamianie z j w poprzednim kroku).

Przykładowo, rozważmy permutację ośmiu elementów (1, 7, 8, 3, 6, 5, 4, 2). Przeglądamy elementy od

prawej do lewej i znajdujemy sytuację 3 < 6, czyli a

i

< a

i+1

dla i = 4. Następnie wśród elementów na

prawo od trójki szukamy większych od 3; znajdziemy 6, 5 i 4. Z tych elementów wybieramy najmniejszy.

Jest to czwórka znajdująca się na pozycji 7, czyli j = 7. Teraz zamieniamy j-ty element (czwórkę) z i-tym

(trójką), otrzymując (1, 7, 8, 4, 6, 5, 3, 2). Dalej odwracamy kolejność elementów leżących na prawo od i-

tego, czyli czwartego. Otrzymujemy permutację (1, 7, 8, 4, 2, 3, 5, 6), która jest szukaną kolejną permutacją

w porządku leksykograficznym następującą po (1, 7, 8, 3, 6, 5, 4, 2).

Generację permutacji w porządku leksykograficznym należy zakończyć wtedy, gdy po takim prze-

kształceniu otrzymamy permutację (n, n

− 1, . . . , 1), która jest ostatnią permutacją w tym porządku.

140

Analiza algorytmów - ćwiczenia

11.2.3.

Generowanie n-tej permutacji

Czasem zachodzi konieczność wygenerowania pojedyczej permutacji o zadanym numerze bez generowania

permutacji ją poprzedzających. Numer jest indeksem permutacji w wybranym uporządkowaniu. Omówi-

my przykładową metodę stosująca poznane już wcześniej tablice inwersji. Tablica inwersji odpowiadająca

pewnej permutacji elementów 1, 2, . . . , n ma n elementów. Na i-tej pozycji tablicy znajduje się liczba

informująca, ile elementów permutacji znajdujących się na lewo od jej i-tego elementu jest większych

od tego elementu. Przykładowo, dla permutacji (4, 3, 5, 2, 1) tablica inwersji ma postać (0, 1, 0, 3, 4). Jeśli

numerujemy pozycje od 1 do n, to na i-tej pozycji tablicy inwersji mogą znaleźć się tylko całkowite

liczby nieujemne mniejsze od i. Łatwo policzyć, że różnych n-elementowych tablic inwersji jest dokładnie

n!, czyli tyle, ile jest permutacji n elementów. Istnieje wzajemnie jednoznaczne odwzorowanie zbioru

permutacji w zbiór tablic inwersji.

Wyznaczenie tablicy inwersji dla danej permuacji jest prostym zadaniem. Odwrotna operacja, wy-

znaczenie permutacji na podstawie tablicy inwersji, jest nieco trudniejsza. Elementy permutacji należy

uporządkować rosnąco: (1, 2, . . . , n). Szukaną permutację konstruuje się od ostatniego elementu. W ta-

blicy inwersji na ostatnim, n-tym miejscu znajduje się liczba t

n

= k informująca, ile elementów szukanej

permutacji na pozycjach od 1 do n

− 1 jest większych od n-tego elementu permutacji. Wobec tego na

n-tej pozycji permutacji musi znaleźć się liczba n

− k. Podobnie można znaleźć elementy n − 1, n − 2 itd.

aż do 1.

Pozostaje więc do rozwiązania wyznaczenie n-tej tablicy inwersji, czyli przekształcenie liczby n na

zawartość tablicy inwersji. Pomocne okazują się tu niejednorodne systemy pozycyjne. Przyzwyczajeni

jesteśmy do stosowania pozycyjnego systemu dziesiętnego, który jest systemem jednorodnym, tzn. wagi

kolejnych cyfr różnią się o stały czynnik, nazywany podstawą r (r > 1). Zapisując liczbę N jako ciąg

cyfr d

i

takich, że 0

d

i

< r:

d

k

d

k−1

d

k−2

. . . d

0

,

d

k

= 0

wyznaczamy jej wartość następująco:

N = d

0

+ d

1

r + d

2

r

2

+ . . . + d

k

r

k

.

Dla systemu dziesiętnego r = 10.

W niejednorodnych systemach pozycyjnych zamiast r stosowany jest ciąg liczb naturalnych r

0

, r

1

, . . . , r

k−1

.

Wtedy podanemu wcześniej ciągowi odpowiada wartość

N = d

0

+ d

1

r

0

+ d

2

r

0

r

1

+ d

3

r

0

r

1

r

2

. . . + d

k

k−1



i=0

r

i

gdzie 0

d

i

< r

i

, d

k

= 0 (za wyjątkiem przypadku N = 0, wtedy d

k

= 0). Przykładem takiego systemu

jest zapis czasu w formacie DHMS (dni, godziny, minuty, sekundy). Dla takiego formatu r

0

= 60, r

1

= 60,

r

2

= 24.

Rozdział 11: Generowanie obiektów kombinatorycznych

141

W omawianym problemie wyznaczania tablic inwersji pomocny będzie tzw. silnia-system:

N = d

0

0! + d

1

1! + d

2

2! + . . . + d

k

k!

gdzie 0

d

i

< i + 1, d

k

= 0 (za wyjątkiem przypadku N = 0), d

0

= 0 (zawsze); r

i

= i + 1. Cyfry tak

zapisanej liczby N są elementami N -tej tablicy inwersji. Algorytm przekształcania liczby N na liczbę w

niejednorodnym systemie pozycyjnym (w szczególności silnia-systemie) przedstawia pseudokod 11.2.3..

Tym sposobem mając dany numer permutacji n można najpierw znaleźć zapis n w silnia-systemie,

wypełnić tablicę inwersji „cyframi” tej liczby i na podstawie tablicy inwersji utworzyć permutację.

11.2.4.

Generowanie losowej permutacji

Znając metodę generowania k-tej permutacji, można wylosować liczbę z przedziału od 1 do n! (gdzie n jest

liczbą permutowanych elementów) i utworzyć k-tą permutację. Jeśli każdą liczbę generowaliśmy z takim

samym prawdopodobieństwem, to również każda permutacja jest wtedy jednakowo prawdopodobna.

Inny sposób to dokonanie n

− 1 transpozycji. Zaczynamy od permutacji o uporządkowanych rosną-

co elementach (1, 2, . . . , n). Zamieniamy n-ty element z losowo wybranym elementem spośród 1 do n.

Następnie element n

− 1 zamieniamy z jednym z elementów spośród 1 do n − 1 itd. Można wykazać, że

tutaj również wszystkie permutacje są jednakowo prawdopodobne.

11.3.

Generowanie podzbiorów

Podzbiorów zbioru n-elementowego jest 2

n

, licząc łącznie ze zbiorem pustym. Tworzenie podzbiorów

jest równoważne tworzeniu n-bitowych ciągów binarnych. Element a

i

należy do podzbioru wtedy i tylko

wtedy, gdy i-ty element ciągu jest jedynką.

11.3.1.

Wszystkie podzbiory

Zagadnienie generowania wszystkich podzbiorów sprowadza się do wygenerowania wszystkich n-bitowych

liczb dwójkowych.

11.3.2.

Losowe podzbiory

Generowanie losowego podzbioru to wylosowanie liczby z przedziału od 0 do 2

n

− 1 i zamiana tej liczby

na postać dwójkową.

Aby wygenerować k-elementowy, losowy podzbiór zbioru S =

{a

1

, a

2

, . . . , a

n

}, należy wyloso-

wać jeden z n elementów tego zbioru i uzupełnić losowym podzbiorem k

− 1 elementowym zbioru

142

Analiza algorytmów - ćwiczenia

S pozbawionego wylosowanego elementu. Prawdopodobieństwo wylosowania k-elementowego podzbio-

ru

{a

i

1

, a

i

2

, . . . , a

i

k

} jest równe iloczynowi prawdopodobieństw zdarzeń:

Pr(pierwszy wybrany element jest jednym z

{a

i

1

, a

i

2

, . . . , a

i

k

}) =

k
n

Pr(drugi wybrany element jest jednym z pozostałych k

− 1 elementów) =

k−1
n−1

Pr(drugi wybrany element jest jednym z pozostałych k

− 2 elementów) =

k−2
n−2

. . .

Pr(k-ty wybrany element jest ostatnim pozostającym elementem) =

1

n−k+1

Iloczyn ten jest równy:

k

n

·

k

− 1

n

− 1

· . . . ·

1

n

− k + 1

=

k!(n

− k)!

n!

=

1



n
k



Ponieważ k-elementowych podzbiorów jest dokładnie



n
k



, więc każdy z nich zostanie wylosowany z jedna-

kowym prawdopodobieństwem. Metoda ta pozwala wygenerować k-elementowy podzbiór w czasie O(k).

11.4.

Generowanie kombinacji

Przez kombinacje rozumiemy podzbiory k-elementowe podzbiory zbioru n-elementowego. W sposób naiw-

ny można wygenerować wszystkie kombinacje generując wszystkie możliwe podzbiory (jak w poprzednim

punkcie) i wybierając spośród nich te, które mają dokładnie k elementów. Jednak w ten sposób zawsze

trzeba będzie przetworzyć 2

n

podzbiorów, tymczasem kombinacji jest tylko



n
k



.

11.4.1.

Porządek leksykograficzny

Przedstawimy metodę generowania kombinacji w porządku leksykograficznym. Kombinacja jest tu opi-

sywana przez ciąg numerów tych elementów zbioru, które należą do kombinacji. Na przykład, jeśli ele-

mentami zbioru będą liczby

{1, 2, 3, 4, 5, 6} i mają zostać wygenerowane trzyelementowe kombinacje, to

będą one miały następujący porządek:

123, 124, 125, 126,

134, 135, 136,

145, 146,

156,

234, 235, 236,

245, 246,

256,

345, 346,

356,

456.

Rozdział 11: Generowanie obiektów kombinatorycznych

143

Poniższy algorytm pokazuje, jak przekształcić n-tą kombinację na (n + 1)-wszą:



Początkowa kombinacja to (1, 2, . . . , k).



Kolejną kombinację tworzymy z bieżącej w następujący sposób:

– Przeglądamy bieżącą kombinację od prawej do lewej strony. Znajdujemy element, który jeszcze

nie osiągnął maksymalnej wartości.

– Element ten zwiększamy o 1, a wszystkie elementy po jego prawej stronie otrzymują kolejno

najmniejsze z dopuszczalnych wartości.

Powracając do przykładu załóżmy, że bieżącą kombinacją jest 156. Aby wygenerować następną kombi-

nację, przeglądamy bieżącą kombinację od prawej strony, znajdując dopiero na pierwszej pozycji liczbę,

która nie osiągnęła jeszcze wartości maksymalnej, w tym przypadku 4. Zwiększamy ją o 1 uzyskując 2.

Elementy po prawej stronie, czyli na pozycjach 2 i 3, mają przyjąć najmniejsze możliwe wartości, czyli

3 i 4. Ostatecznie otrzymujemy kombinację 234.

11.4.2.

Porządek minimalnych zmian

Przy generowaniu kombinacji w porządku minimalnych zmian korzysta z kodu Gray’a. W zwykle stosowa-

nej odmianie jest to sekwencja ciągów binarnych, w której kolejne dwa ciągi binarne różnią się dokładnie

na jednej pozycji. Na przykład dla dwóch bitów może to być sekwencja:

00, 01, 11, 10

dla trzech bitów:

000, 001, 011, 010, 110, 111, 101, 100.

Zauważmy, że sekwencje takie można tworzyć rekurencyjnie: przy trzech bitach wystarczy przepisać ciąg

sekwencji dwubitowych najpierw w normalnym porządku dopisując na początku zera, potem w odwrot-

nym porządku dopisując jedynki. Możliwe jest też tworzenie sekwencji o długościach innych niż 2

n

, np.

przez znajdowanie zamkniętych dróg w tzw. tablicach Karnaugha.

Podczas generowania kombinacji korzysta się z nieco innego rodzaju kodu Gray’a. Kolejne cią-

gi różnią się na dokładnie dwóch bitach i mają zawsze tę samą liczbę jedynek, równą k. Koncepcja

generowania takich sekwencji jest podobna do przedstawionego wcześniej rekurencyjnego generowania

„zwykłych” kodów. Przez G(n, k) oznaczymy sekwencję ciągów n-bitowych o k jedynkach. Wtedy:

G(n, k) =




0

G(n

− 1, k)

1

G(n

− 1, k − 1)

R


 .

Zapis G(n

−1, k−1)

R

oznacza, że chodzi o sekwencję G(n

−1, k−1), ale w odwróconej kolejności. Zgodnie

z oznaczeniem, G(n, 0) jest (jednym) ciągiem n zer, natomiast G(n, n) (jednym) ciągiem n jedynek:

G(n, 0) = 0000 . . . 0,

144

Analiza algorytmów - ćwiczenia

G(n, n) = 1111 . . . 1.

Zachęcamy Czytelnika do przeanalizowania tego wzoru rekurencyjnego na prostym przykładzie, np. dla

G(4, 2). Wynikową sekwencją jest:

0011, 0110, 0101, 1100, 1010, 1001.

Czytelnik zechce również sprawdzić, że kolejne ciągi binarne różnią się dokładnie na dwóch pozycjach.

11.4.3.

Generowanie i-tej kombinacji

Generowanie dowolnego podzbioru w czasie niezależnym od liczby wszystkich podzbiorów, a jedynie

od mocy podzbioru, jest przydatne zarówno przy generowaniu wszystkich podzbiorów, jak i losowego

podzbioru bądź pewnej liczby podzbiorów. Opisany dalej generator przekształca liczbę naturalną i

∈



0,



n
k



− 1



na i-ty podzbiór w pewnym uporządkowaniu. Istnieje wiele metod generacji podzbiorów

w ten sposób, w tym rozdziale zostanie przedstawiona jedna z nich. Rys. 11.2 przedstawia tzw. trójkąt

Pascala. Potraktujmy elementy tego trójkąta jako wierzchołki grafu skierowanego. Łuki grafu łączą każdy

wierzchołek grafu tylko z bezpośrednio „nad nim” leżącymi wierzchołkami: dwoma, jednym lub żadnym

w przypadku najwyższego wierzchołka (łuki te nie zostały zaznaczone na rysunku). Nazwijmy najwyżej

leżący wierzchołek korzeniem. Zauważmy, że z wierzchołka znajdującego się na pozycji (n, k) istnieje

dokładnie



n
k



dróg prowadzących do korzenia, czyli tyle, ile wynosi wartość odpowiedniego elementu

trójkąta. Własność tę można udowodnić przez indukcję: jeśli była prawdziwa dla wierzchołków (n, k

− 1)

i (n, k), to będzie też prawdziwa dla wierzchołka (n + 1, k), ponieważ można z niego przejść do (n, k

− 1)

i dalej wykorzystać wszystkie ścieżki stamtąd do korzenia, albo do (n, k). Liczba dróg jest sumą liczb

dróg z tych dwóch wierzchołków i tyle jest też równa wartość elementu (n + 1, k):



n+1

k



=



n

k−1



+



n
k



dla k = 1, . . . , n.

Z każdą drogą prowadzącą z wierzchołka (n, k) do korzenia możemy związać dokładnie jeden k-

elementowy podzbiór zbioru n-elementowego. Aby ustalić, które spośród n elementów należą do pod-

zbioru, prześledźmy drogę z wierzchołka (n, k) do wierzchołka (0, 0). Przechodzimy więc z poziomu i = n

do poziomu i = 0. W każdym przypadku, kiedy przechodząc na poziom „wyższy” (z i do i

− 1) wybierze-

my lewy wierzchołek, przyjmiemy, że element i-ty należy do pozbioru. W przeciwnym razie nie należy.

Oczywiście „zakrętów w lewo” jest dokładnie tyle, ile jest równe k (rys. 11.2).

Pozostaje więc do rozwiązania numerowanie dróg w taki sposób, aby na podstawie numeru dało

się wygenerować drogę bez konieczności generowania wszystkich poprzednich dróg. Tutaj przyda się

poprzednia obserwacja: z wierzchołka (n, k) możemy przejść do wierzchołka (n

− 1, k − 1) lub (n − 1, k).

Przyjmiemy, że



n−1

k−1



początkowych numerów oznacza drogi skręcające do (n

−1, k−1), a pozostałe (czyli



n−1

k



numerów) drogi skręcające do (n

− 1, k). Mając numer drogi wystarczy więc porównać go z



n−1
k−1



i w zależności od wyniku porównania przejść do lewego lub prawego wierzchołka na wyższym poziomie.

Przy przechodzeniu do prawego wierzchołka należy numer drogi do dalszych obliczeń zmodyfikować tak,

Rozdział 11: Generowanie obiektów kombinatorycznych

145

aby ścieżki wychodzące z tego wierzchołka były numerowane od jedynki (bądź zera, zależnie od założeń),

czyli odjąć od niego



n−1

k



. W ten sposób uzyskujemy algorytm przedstawiony jako pseudokod 11.4.3..

Zamiast wyznaczania



S

p



w każdym obiegu iteracji można również skorzystać z zależności:

n

− 1

k

=

n

k

·

n

− k

n

,

n

− 1

k

− 1

=

n

k

·

k

n

,

unikając w ten sposób wielokrotnego wyznaczania wartości



S

p



. Złożoność takiego algorytmu jest rzędu

O(n), czyli liczby elementów zbioru.

Literatura

[1] Edward M. Reingold, Jurg Nievergelt, Narsingh Deo, Alorytmy kombinatoryczne, Państwowe Wy-

dawnictwo Naukowe, Warszawa 1985

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, WNT,

Warszawa 1997

146

Analiza algorytmów - ćwiczenia

1














































































































































































































































































1 2






























































































































1 2 3






























1 2 3 4

1 2 4 3

1 4 2 3

4 1 2 3

1 3 2






























4 1 3 2

1 4 3 2

1 3 4 2

1 3 2 4

3 1 2






























3 1 2 4

3 1 4 2

3 4 1 2

4 3 1 2

2 1






























































































































3 2 1






























4 3 2 1

3 4 2 1

3 2 4 1

3 2 1 4

2 3 1






























2 3 1 4

2 3 4 1

2 4 3 1

4 2 3 1

2 1 3






























4 2 1 3

2 4 1 3

2 1 4 3

2 1 3 4

11.1. Generowanie permutacji w porządku minimalnych zmian. Podkreślone zostały elementy wstawiane

w kolejnych krokach. Zależnie od parzystości numeru iteracji, elementy wstawiane są od prawej do

lewej bądź od lewej do prawej strony poprzedniej permutacji.

Rozdział 11: Generowanie obiektów kombinatorycznych

147

1

procedure SilniaSystem;

2

begin

3

f

Dane wejściowe: liczba N

g

4

f

Dane wyjściowe: ciąg cyfr d

0

, d

1

, . . . , d

k

będący zapisem N w silnia-systemie

g

5

d

0

:= 0;

f

najstarsza cyfra zawsze równa 0

g

6

q := N ;

7

k := 0;

8

while q

= 0 do

9

d

k

:= q mod r

k

;

f

kolejna cyfra

g

10

q := q div r

k

;

11

k := k + 1;

12

end while;

13

if k

= 0 then

14

k := k

− 1;

15

end if;

16

end.

11.2. Generowanie kombinacji na podstawie trójkąta Pascala

148

Analiza algorytmów - ćwiczenia

1

procedure gen komb(n, S, p: integer);

2

begin

3

f

n: nr kombinacji od 0, S: liczba elementów zbioru, p: liczba elementów podzb.

g

4

f

v, lewy r, prawy r, i: zmienne cakowite

g

5

n := n + 1;

f

...teraz kombinacje są numerowane od 1

g

6

i := 0;

f

nr pierwszego elementu zbioru

g

7

while S > 0 do

8

v :=



S

p



;

f

wartość bieżącego elementu trójkąta

g

9

prawy r :=



S−1

p



;

f

„prawy rodzic”

g

10

if p < S then

11

lewy r := v

− prawy r;

12

else

13

lewy r := 1;

f

„lewy rodzic”

g

14

end if;

15

S := S

− 1;

f

„piętro” w górę

g

16

if n > lewy r then

f

idziemy w prawo do góry

g

17

n := n

− lewy r;

18

writeln(’element ’,i, ’nie należy do podzbioru’);

19

else

f

idziemy w lewo do góry

g

20

writeln(’element ’,i, ’należy do podzbioru’);

21

p := p

− 1;

f

zmniejszamy liczbę elementów podzbioru („k”)

g

22

end if;

23

i := i + 1;

f

nr kolejnego elementu zbioru

g

24

end while;

25

end.

Rozdział 12

Algorytmy geometryczne: wypukła

otoczka

12.1.

Wprowadzenie

Wypukłą otoczką zbioru punktów Q nazywamy najmniejszy wielokąt wypukły P taki, że każdy punkt

ze zbioru Q leży na brzegu P albo w jego wnętrzu. Rys. 12.1 przedstawia przykładowy zbiór punktów i

jego otoczkę. Wypukłą otoczkę zbioru Q oznaczamy przez CH(Q) (ang. convex hull).

12.1. Zbiór punktów Q wraz z zaznaczoną swoją wypukłą otoczką CH(Q). Źródło: [1].

Dalej zostaną przedstawione dwa algorytmy wyznaczające wierzchołki wypukłej otoczki w kolejności

przeciwnej do ruchu wskazówek zegara: algorytm Grahama działający w czasie O(n lg n) i algorytm

Jarvisa działający w czasie O(nh), gdzie n jest liczbą punktów zbioru Q, a h jest liczbą punktów na

otoczce.

W obu algorytmach stosuje się metodę zwaną „zamiataniem obrotowym”, polegającą na przeglą-

149

150

Analiza algorytmów - ćwiczenia

daniu wierzchołków w kolejności wzrastających kątów, jaki tworzy ustalona półprosta z półprostą o

tym samym początku, przechodząca przez analizowany wierzchołek. Istnieją też inne metody, również

działające w czasie O(n lg n).

12.2.

Algorytm Grahama

Algorytm Grahama korzysta ze stosu S, zawierającego kandydatów na wierzchołki otoczki. Każdy

punkt zbioru Q jest raz wkładany na stos. Punkty nie będące wierzchołkami CH(Q) są podczas reali-

zacji algorytmu zdejmowane ze stosu. Po zakończeniu działania algorytmu na stosie S pozostaną tylko

wierzchołki CH(Q).

Algorytm działa dla co najmniej trzyelementowych zbiorów Q,

|Q|  3. Poza stadnardowymi funk-

cjami operującymi na stosie, Push(S) i Pop(S), używane są jeszcze funkcja Top(S) zwracająca element

na szczycie stosu S bez zdejmowania go ze stosu oraz funkcja Next to top(S), zwracająca element leżący

bezpośrednio pod szczytowym elementem stosu, również bez modyfikowania stanu S. Po zakończeniu

działania algorytmu stos S będzie zawierał (od dołu do góry) wszystkie wierzchołki CH(Q) w kolejności

przeciwnej do ruchu wskazówek zegara. Algorytm przedstawia pseudokod 12.2..

1

procedure Graham Scan(Q);

2

begin

3

znajdź w zbiorze Q punkt p

0

o minimalnej współrzędnej y;

4

jeśli jest więcej punktów o tej współrzędnej, wybierz punkt o najmniejszej współrzędnej x;

5

pozostałe punkty Q posortuj rosnąco ze względu na współrzędną kątową w biegunowym układzie współrzędnych

6

oznacz kolejno przez p

1

, p

2

, . . . , p

n−1

;

7

wyzeruj stos S;

8

Push(S, p

0

);

9

Push(S, p

1

);

10

Push(S, p

2

);

11

for i := 3 to n

− 1 do

12

while kąt (Next to top(S), Top(S), p

i

) nie oznacza skrętu w lewo do

13

Pop(S);

14

end while;

15

Push(S, p

i

);

16

end for;

17

return S;

f

w S jest szukana otoczka

g

18

end.

W jaki sposób sprawdzić, czy przechodząc z punktu A przez B do C skręcamy w lewo, opisano

Rozdział 12: Algorytmy geometryczne: wypukła otoczka

151

w poprzedniej części ćwiczeń

1

. Działanie algorytmu Graham Scan dla przykładowego zbioru Q można

prześledzić na rysunkach 12.2 i 12.3.

Bieżący wynik, tzn. fragment otoczki opisany ciągiem punktów znajdujących się na stosie S, jest

zaznaczony na kolejnych rysunkach linią łamaną. Rysunek (a) przedstawia najniżej położony punkt

oznaczony p

0

i pozostałe, ponumerowane w kolejności rosnących kątów w biegunowym układzie współ-

rzędnych o początku w p

0

. Zaznaczone są też trzy początkowe punkty p

0

, p

1

i p

2

odłożone na stos S.

Rysunek (b) przestawia sytuację po próbie odłożenia na S kolejnego punktu, p

3

. Przed jego odłożeniem

sprawdzono, czy przechodząc z p

1

przez p

2

do p

3

skręcamy w lewo. Okazało się, że nie. Wobec tego ze

stosu został zdjęty jeden punkt (p

2

). Ponownie sprawdzono, czy przechodząc z przedostatniego punktu

na stosie (p

0

) przez ostatni (p

1

) do p

3

skręcamy w lewo. Tym razem okazało się, że tak. Dlatego punkt

p

2

został odłożony na stos. Kolejne rysunki (b-l) przedstawiają następne kroki algorytmu. Za każdym

razem, kiedy skręt nie jest skrętem w lewo (co powoduje usuwanie punktów ze stosu), zaznaczono odpo-

wiedni kąt przerywaną linią. Ostatni rysunek (l) przedstawia wynik działania algorytmu, czyli znalezioną

wypukłą otoczkę CH(Q).

Złożoność algorytmu Graham Scan

można wyznaczyć badając czas wykonania kolejnych eta-

pów algorytmu. Punkt o minimalnej współrzędnej y można znaleźć w czasie O(n). Sortowanie n punktów

wymaga czasu O(n lg n). Każdy punkt jest dokładnie raz odkładany na stos i najwyżej raz z niego zdej-

mowany. Związane z tym operacje, m.in. sprawdzanie kątów, łącznie zajmują czas O(n) (analizujemy

tu tzw. koszt zamortyzowany). Najwyższy rząd złożoności ma więc sortowanie, czyli rząd złożoności

całego algorytmu jest także równy O(n lg n).

12.3.

Algorytm Jarvisa

Zauważmy, że do znalezienia dwóch początkowych punktów CH(Q), tj. punktów p

0

i p

1

, wystarczyłoby

odnalezienie p

0

i wybór punktu o minimalnym kącie w biegunowym układzie współrzędnych (bez sorto-

wania). Algorytm Jarvisa w podobny sposób, nazywany owijaniem, znajduje kolejne punkty wypukłej

otoczki. Po znalezieniu punktu p

1

przesuwa do niego początek układu współrzędnych i ponownie wy-

szukuje wśród pozostałych punktów Q taki, który ma minimalną współrzędną biegunową. Znaleziony

zostanie p

2

. Tym sposobem znajdziemy prawą część CH(Q), tzn. część wypukłej otoczki łączącą „le-

woskrętnie” najniżej z najwyżej położonym punktem. Tę część nazwiemy prawym łańcuchem. Drugą

część CH(Q), lewy łańcuch, znajdziemy w podobny sposób, zaczynając od najwyżej położonego punk-

tu (oznaczmy go przez p

k

). Tym razem jednak kąty będziemy odmierzać od ujemnej części osi x. Możliwe

jest też połączenie obu etapów przyjmując, że ciąt kątów związanych z bokami otoczki musi być ściśle

rosnący (od 0 do 2π).

1

której tu jeszcze nie ma

152

Analiza algorytmów - ćwiczenia

Przykładową realizację algorytmu Jarvisa przestawia rysunek 12.4.

Złożoność algorytmu Jarvisa jest rzędu O(nh), gdzie h jest liczbą punktów otoczki. Dla każdego

punktu otoczki znajdujemy wierzchołek o minimalnej współrzędnej kątowej, co wymaga czasu O(n).

Łącznie dla h punktów mamy więc O(nh).

Literatura

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Wprowadzenie do algorytmów, WNT,

Warszawa 1997

Rozdział 12: Algorytmy geometryczne: wypukła otoczka

153

12.2. Działanie algorytmu Graham Scan, cz. 1. Źródło: [1].

154

Analiza algorytmów - ćwiczenia

12.3. Działanie algorytmu Graham Scan, cz. 2. Źródło: [1].

Rozdział 12: Algorytmy geometryczne: wypukła otoczka

155

12.4. Przykładowa realizacja algorytmu Jarvisa. Źródło: [1].

156

Analiza algorytmów - ćwiczenia

Spis rysunków

1.1

Świątynia Pura Ulu Danau, Bali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.2

Wieże w Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.3

Szacowanie od dołu wartości H

n

: ln n < H

n

. . . . . . . . . . . . . . . . . . . . . . . . . .

20

1.4

Szacowanie od góry wartości H

n

: H

n

< ln n + 1 . . . . . . . . . . . . . . . . . . . . . . . .

20

2.1

Algorytm znajdowania elementu minimalnego i maksymalnego (minmax1) . . . . . . . . .

26

2.2

Algorytm znajdowania elementu minimalnego i maksymalnego (minmax2) . . . . . . . . .

27

2.3

Algorytm znajdowania elementu minimalnego i maksymalnego (minmax3) . . . . . . . . .

29

2.4

Prosty algorytm sortowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.1

Algorytm sortowania przez proste wybieranie . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.2

Ilustracja działania algorytmu sortowania przez proste wybieranie (pionowa kreska od-

dziela fragment tablicy, który jest już posortowany) . . . . . . . . . . . . . . . . . . . . . .

37

3.3

Ilustracja działania algorytmu sortowania przez proste wstawianie

. . . . . . . . . . . . .

38

3.4

Szkic algorytmu sortowania przez proste wstawianie

. . . . . . . . . . . . . . . . . . . . .

38

3.5

Algorytm sortowania przez proste wstawianie bez wartownika . . . . . . . . . . . . . . . .

39

3.6

Algorytm sortowania przez proste wstawianie z wartownikiem . . . . . . . . . . . . . . . .

41

3.7

I lustracja działania algorytmu sortowania Shella

. . . . . . . . . . . . . . . . . . . . . . .

43

3.8

Algorytm sortowania Shella . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.9

Algorytm sortowania bąbelkowego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.10 Algorytm wyszukiwania binarnego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

4.1

Ogólna wersja algorytmu sortowania szybkiego . . . . . . . . . . . . . . . . . . . . . . . .

52

4.2

I lustracja działania algorytmu sortowania szybkiego

. . . . . . . . . . . . . . . . . . . . .

52

4.3

Algorytm sortowania szybkiego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.4

Algorytm wyboru k-tego co do wielkości elementu w oczekiwanym czasie liniowym . . . .

60

5.1

Rekurencyjny algorytm obliczania liczb Fibonacciego . . . . . . . . . . . . . . . . . . . . .

66

5.2

Drzewo wywołań procedury Fib1 dla parametru 6 . . . . . . . . . . . . . . . . . . . . . . .

67

157

158

Analiza algorytmów - ćwiczenia

5.3

Nierekurencyjny algorytm wyznaczania liczb Fibonacciego . . . . . . . . . . . . . . . . . .

68

5.4

Algorytm wyznaczania długości najdłuższego wspólnego podciągu (NWP) . . . . . . . . .

70

5.5

I lustracja działania algorytmu wyznaczania NWP . . . . . . . . . . . . . . . . . . . . . . .

71

5.6

Algorytm drukowania najdłuższego wspólnego podciągu . . . . . . . . . . . . . . . . . . .

72

6.1

Przykładowe drzewo binarne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

6.2

Przykładowe drzewo poszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . . . . . .

78

6.3

Wyszukiwanie elementu o podanym kluczu w drzewie poszukiwań binarnych . . . . . . . .

79

6.4

Wyszukiwanie minimalnego elementu w drzewie poszukiwań binarnych . . . . . . . . . . .

79

6.5

Wyszukiwanie maksymalnego elementu w drzewie poszukiwań binarnych . . . . . . . . . .

80

6.6

Wyszukiwanie następnika elementu w drzewie przeszukiwań binarnych . . . . . . . . . . .

80

6.7

Wstawianie nowego elementu do drzewa poszukiwań binarnych. . . . . . . . . . . . . . . .

81

6.8

Niezrównoważone drzewo poszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . . . .

82

6.9

Usuwanie klucza z drzewa poszukiwań binarnych. We wszystkich przypadkach usuwany

element jest zaznaczony jasno szarym kolorem, a element faktycznie wycinany (przypadek

c) jest zaznaczony ciemnoszarym kolorem. . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

6.10 Usuwanie elementu z drzewa poszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . .

84

6.11 Przykładowe drzewo czerwono-czarne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

6.12 Zamiany wykonywane przez rotacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

6.13 Przykład działania operacji rotacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

6.14 Drzewo statystyk pozycyjnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

6.15 Operacja wyszukiwania elementu o zadanej randze . . . . . . . . . . . . . . . . . . . . . .

89

6.16 Wyznaczanie rangi elementu w dynamicznej statystyce pozycyjnej . . . . . . . . . . . . .

89

6.17 Zmiany wykonywane w trakcie rotacji. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

7.1

Szukanie wyjścia z labiryntu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

7.2

Ilustracja możliwości obcinania gałęzi drzewa wyszukiwania. Bez obcinania przeanalizowa-

ne musiałyby być wszystkie węzły. Obcięcia znacznie redukują liczbę węzłów, tym bardziej,

im wyżej (bliżej korzenia) są dokonywane. . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

7.3

Przykładowe drzewo z odciętymi gałęziami i kolejność przeszukiwania węzłów drzewa przez

algorytm wyszukiwania wyczerpującego, zaznaczona przerywaną linią. . . . . . . . . . . .

97

7.4

Labirynt ilustrujący możliwość łączenia gałęzi drzewa wyszukiwania . . . . . . . . . . . . 100

7.5

Reorganizacja drzewa. Obydwa drzewa mają jednakową liczbę liści, ale drzewo (a) można

efektywniej przeszukać niż (b), ponieważ odcięcie gałęzi wyeliminuje naraz więcej liści. . . 101

7.6

Szacowanie wielkości drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

7.7

Fragmenty drzewa gry w kółko i krzyżyk. Źródło: [1]. . . . . . . . . . . . . . . . . . . . . . 104

7.8

Ilustracja α–β obcięcia. Źródło: [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Rozdział 12: Algorytmy geometryczne: wypukła otoczka

159

9.1

Dwie reprezentacje grafu nieskierowanego: (a) graf nieskierowany, (b) listy sąsiedztwa, (c)

macierz sąsiedztwa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

9.2

Dwie reprezentacje grafu skierowanego: (a) graf skierowany, (b) listy sąsiedztwa, (c) ma-

cierz sąsiedztwa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

9.3

Algorytm Floyda-Warshalla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

9.4

Przykładowy przebieg algorytmu FW

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

9.5

Graf nieskierowany o jednostkowych wagach krawędzi i wynikowe macierze D i P . . . . . 120

9.6

Przykładowy przebieg algorytmu Dijkstry. Źródłem jest wierzchołek s. Na rys. (a) tylko on

ma ustaloną wagę drogi, ale jeszcze nie należy do zbioru S. Jest wybierany jako wierzchołek

o minimalnej wadze spoza S i dołączany do S, co uwidoczniono na rys. (b). Wierzchołki

należące do S oznaczono na czarno. Teraz dokonywana jest relaksacja krawędzi wychodzą-

cych z s, a więc (s, u) oraz (s, x). Pierwsza relaksacja powoduje przypisanie wierzchołkowi

u wagi 10, ponieważ idąc do u poprzez s krawędzią o koszcie 10 uzyskujemy łączny koszt

0 + 10 = 10, a 10 <

∞. Podobnie wierzchołek x uzyskuje wagę 5. W kolejnym obiegu

głównej iteracji znowu szukamy wierzchołka z minimalną wagą spośród wierzchołków nie

należących do S. Tym razem jest nim wierzchołek x o wadze 5. Dołączamy go do zbioru S,

co przedstawia rys. (c). Dokonujemy relaksacji krawędzi wychodzących z wierzchołka x, w

wyniku czego zmieniają się wagi wierzchołków u, v, y. W kolejnym obiegu wierzchołkiem

o minimalnej wadze, nie należącym do S jest y itd. Rys. (f) przedstawia ostateczny wynik

działania algorytmu, wszystkie wierzchołki należą do S. . . . . . . . . . . . . . . . . . . . 122

10.1 Algorytm wstawiania do tablicy z adresowaniem bezpośrednim . . . . . . . . . . . . . . . 126

10.2 Algorytm usuwania z tablicy z adresowaniem bezpośrednim . . . . . . . . . . . . . . . . . 126

10.3 Algorytm szukania w tablicy z adresowaniem bezpośrednim . . . . . . . . . . . . . . . . . 126

10.4 Algorytm wstawiania do tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania

kolizji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

10.5 Algorytm usuwania z tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania kolizji131

10.6 Algorytm szukania w tablicy z mieszaniem, z „łańcuchową” metodą przezwyciężania kolizji132

10.7 Algorytm wstawiania do tablicy z mieszaniem zamkniętym

. . . . . . . . . . . . . . . . . 132

10.8 Algorytm usuwania z tablicy z mieszaniem zamkniętym . . . . . . . . . . . . . . . . . . . 133

10.9 Algorytm szukania w tablicy z mieszaniem zamkniętym . . . . . . . . . . . . . . . . . . . 133

11.1 Generowanie permutacji w porządku minimalnych zmian. Podkreślone zostały elementy

wstawiane w kolejnych krokach. Zależnie od parzystości numeru iteracji, elementy wsta-

wiane są od prawej do lewej bądź od lewej do prawej strony poprzedniej permutacji. . . . 146

11.2 Generowanie kombinacji na podstawie trójkąta Pascala . . . . . . . . . . . . . . . . . . . . 147

160

Analiza algorytmów - ćwiczenia

12.1 Zbiór punktów Q wraz z zaznaczoną swoją wypukłą otoczką CH(Q). Źródło: [1]. . . . . . 149

12.2 Działanie algorytmu Graham Scan, cz. 1. Źródło: [1]. . . . . . . . . . . . . . . . . . . . . . 153

12.3 Działanie algorytmu Graham Scan, cz. 2. Źródło: [1]. . . . . . . . . . . . . . . . . . . . . . 154

12.4 Przykładowa realizacja algorytmu Jarvisa. Źródło: [1]. . . . . . . . . . . . . . . . . . . . . 155

Spis tabel

2.1

Porównanie czasów działania algorytmów wyszukiwania minimum i maksimum (czasy sta-

nowią średnią ze 100 wykonań) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

3.1

Porównanie własności prostych algorytmów sortowania . . . . . . . . . . . . . . . . . . . .

45

3.2

Porównanie czasów działania prostych algorytmów sortowania (czasy stanowią średnią ze

100 wykonań) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.3

Porównanie czasów działania algorytmu sortowania Shella dla różnych ciągów przyrostów

46

4.1

Porównanie metod wyboru klucza osiowego dla algorytmu quick sort . . . . . . . . . . .

58

4.2

Porównanie wydajności algorytmów sortowania (czasy stanowią średnią ze 100 wykonań) .

58

161

Skorowidz

algorytm

sortowania

stabilny, 35

zachowanie naturalne, 35

czynnik sumacyjny, 55

klucz osiowy, 51

sortowanie, 35

tablica inwersji, 27

162