Rozdział 7
Wyszukiwanie wyczerpujÄ…ce
7.1. Wprowadzenie
Rozwiązanie wielu problemów wymaga odpowiedzi na pytania typu:  jak wiele jest możliwości. . .  ,
 znalez
ć 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 1010. 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(n2), 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 (a1, a2, . . . ak) o skoń-
czonej, ale nie znanej z góry długości, spełniający pewne warunki. Każda  współrzędna ai jest ele-
mentem skończonego, liniowo uporządkowanego zbioru Ai, oznaczającego możliwe wartości ai, być
może różne dla różnych i.
W wyszukiwaniu należy wiÄ™c jako potencjalne rozwiÄ…zania rozważyć elementy zbioru A1×A2×. . . Ak
dla k =0, 1, 2, . . . .
W przykładzie z labiryntem wszystkie zbiory Ai będą jednakowe:
Ai = {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 A1 są kandydatami na
współrzędną a1. Taki podzbiór zbioru A1 oznaczymy przez S1. Wybieramy jako a1 pierwszy element ze
zbioru S1 otrzymując w ten sposób rozwiązanie częściowe (a1).
Ogólnie, różne ograniczenia opisujące rozwiązania mówią, jaki podzbiór Sk zbioru Ak jest zbiorem
kandydatów na roszerzenie rozwiązanie częściowego (a1, . . . ak-1) do (a1, . . . ak-1, ak). Jeśli Sk = ", to
96 Analiza algorytmów - ćwiczenia
 wracamy i wybieramy jako ak-1 inny element Sk-1. Jeśli znowu Sk-1 = ", to cofamy się do ak-2. Jeśli
wycofamy się aż do a1 i też okaże się, że nie ma już innych elementów S1 do rozszerzenia rozwiązania,
to skończyliśmy przeszukiwanie.
Dzięki ograniczaniu możliwych ruchów do elementów zbioru Sk zamiast Ak, mamy możliwość znacz-
nego okrojenia tzw. drzewa wyszukiwania. Bez ograniczania musielibyśmy przeanalizować drzewo o
|A1| · |A2| · . . . · |Ad| 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 (a1, a2, . . . , ai).
Ogólny algorytm wyszukiwania wyczerpującego (z powrotami) można zapisać następująco:
Powyższa wersja wymaga jednoczesnego zapamiętywania wielu zbiorów Sk, 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 (a1, a2, . . . , ak)) potrzebna jest informacja o możliwościach  ele-
mentach zbiorów Sk-1, Sk-2 itd., które nie zostały jeszcze przeanalizowane. Stąd konieczność jawnego
przechowywania wielu Sk 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:
(a1, a2, . . . , ak) || (b1, b2, . . . , bl) =(a1, a2, . . . , ak, b1, b2, . . . , bl)
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 S1 na podstawie A1 i ograniczeń ;
4 k := 1;
5 while k >0 do
6 while Sk = " do

7 ak := element z Sk;
8 Sk := Sk -{ak};
9 if  (a1, a2, . . . , ak) jest rozwiÄ…zaniem then
10  wypisz (a1, a2, . . . , ak) ;
11 end if;
12 k := k +1; następny  poziom
13  wyznacz Sk na podstawie Ak i ograniczeń ;
14 end while;
15 k := k - 1; powrót
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(a1, a2, . . . , ak-1) koszt(a1, a2, . . . , ak-1, ak)
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 := "; nieskończoność, bieżące minimum
4 koszt := 0; aktualny koszt
5  wyznacz S1 na podstawie A1 i ograniczeń ;
6 k :=1;
7 while k > 0 do
8 while (Sk = ") and (koszt < min koszt) do

9 ak := element z Sk;
10 Sk := Sk -{ak};
11 koszt := koszt(a1, a2, . . . , ak);
12 if  (a1, a2, . . . , ak) jest rozwiÄ…zaniem and koszt < min koszt then
13 min koszt := koszt((a1, a2, . . . , ak));
14 end if;
15 k :=k +1; następny  poziom
16  wyznacz Sk na podstawie Ak i ograniczeń ;
17 end while;
18 k := k - 1; powrót
19 koszt := koszt((a1, a2, . . . , ak));
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łtu1. 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

|Ai|
i=1
liści, gdzie |Ai| jest liczbą elementów w zbiorze A. Nawet przy szerokim zastosowaniu wykluczania i
sklejania można się spodziewać, że |Si| będzie stałą  pewnym ułamkiem |Ai|.
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 ai.
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 x1, x2, . . . , xd, gdzie d jest
długością ścieżki, to całkowita liczba węzłów W drzewa (bez korzenia) zostanie oszacowana przez:
d d i

W = x1 + x1x2 + x1x2x3 + . . . + xj = xj
j=1 i=1 j=1
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 Si 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 N oznacza liczbę eksperymentów do przeprowadzenia
4 średnia := 0;
5 for i :=1 to N do
6 iloczyn := 1; na iloczyn x1x2x3 . . .
7 suma := 0; na sumę iloczynów x1 + x1x2 + . . .
8  wyznacz S1 na podstawie A1 i ograniczeń ;
9 k :=1;
10 while Sk = " do

11 iloczyn := iloczyn * |Sk|;
12 suma := suma + iloczyn;
13 ak := losowy element z Sk;
14 nie musimy usuwać ak z Sk, bo i tak nie będzie powrotu
15 k :=k +1; następny  poziom
16  wyznacz Sk na podstawie Ak i ograniczeń ;
17 end while;
18 dotarliśmy do liścia, mamy oszacowanie liczby węzłów w tym eksperymencie
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. y
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 N1, N2, . . . , Nk wartość v(N) definiujemy w następujący sposób:
Å„Å‚
òÅ‚
max(v(N1), . . . , v(Nk)) jeśli poziom węzła N jest nieparzysty
v(N) =
ół
min(v(N1), . . . , v(Nk)) 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
korzenia2.
Wyznaczenie wartości węzła jest istotne, ponieważ na podstawie tej wartości można ustalić, który
ruch (gałąz
) 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 znalez
ć odpowiedz
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. y
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 szachownicy3, 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 Eratostenesa4 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
Znalez
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ędz
(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 wgrafie G =(V, E) jest ciągiem wierz-
chołków v0, v1, . . . , vk takich, że p = v0, q = vk i (vi-1, vi) " 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
v0, v1, . . . , vk tworzy cykl, jeśli v0 = vk oraz droga zawiera co najmniej jedną krawędz
. Cykl jest pro-
sty, jeśli wszystkie wierzchołki v1, . . . , vk są różne. Pętla jest cyklem o długości 1. Cykl v0, v1, . . . , vk
oraz v1, v2, . . . , vk, v0 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 V1 i V2 takie, że wierzchołki każdej krawędzi tego grafu należą odpowiednio do
podzbioru V1 i V2.
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 = {aij} o wymiarach |V | ×|V | takÄ…, że aij = 1 jeÅ›li w grafie istnieje krawÄ™dz
(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 = v1, v2, . . . , vk 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:
k

w(p) = w(vi-1, vi)
i=2
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 z
ródłem: wyróżniamy jeden wierzchołek s (nazywany z
ródłem, ang. sour-
ce) grafuG 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 z
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 z
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
z
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 z
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 = {dij}, i, j " V . Dodatkowo zakłada się, że:
 Długości krawędzi dij 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 dij = ".
 Dla każdego d zachodzi d + " = " oraz min(d, ") =d.
Szukane:
Szukamy macierzy D" = {d" }, gdzie d" jest długością najkrótszej drogi prowadzącej od wierzchołka
ij ij
i do wierzchołka j, i, j " V .
Algorytm Floyda-Warshalla wyznacza ciÄ…g macierzy
D0, D1, . . . , Dn = D"
Rozdział 9: Algorytmy grafowe 117
takich, że Dn jest macierzą długości najkrótszych dróg. Każda macierz Dk, k =1, 2, . . . , n jest wyzna-
czana następująco:
dk = min(dk-1, dk-1 + dk-1) i, j " V
ij ij ik kj
dla k =1, 2, . . . , n.
Macierz D0 jest wyznaczana według zależności:
Å„Å‚
òÅ‚
0 gdy i = j,
d0 =
ij
ół
dij gdy i = j.

Wartość dk jest długością najkrótszej drogi od wierzchołka i do j nie przechodzącej przez żaden wierz-
ij
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(n3).
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 = {pij} jest macierzą  następnych wierzchołków drogi;
dokładniej: pij 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:
Å„Å‚
òÅ‚
j gdy dij = ",

p0 =
ij
ół
0 gdy dij = ".
W i-tej iteracji, jeśli
dik + dkj to przyjmujemy pij:=pik.
118 Analiza algorytmów - ćwiczenia
1 procedure FW;
2 begin
3 Dane: macierz długości krawędzi D = {dij}
4 Szukane: macierz długości najkrótszych dróg D = {dij}
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 d0 1 2 3
1 2 8 5 1 0 8 5
2 3 " " 2 3 0 "
3 " 2 " 3 " 2 0
d1 1 2 3 d2 1 2 3 d3 1 2 3
1 0 8 5 1 0 8 5 1 0 7 5
2 3 0 8 2 3 0 8 2 3 0 8
3 " 2 0 3 5 2 0 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. znalez
ć najkrótszą drogę z wierzchołka
1 do wierzchołka 7. Element p17 = 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 p27 = 4, a więc kolejnym wierzchołkiem drogi jest 4. Tam znajdujemy p47 =6, dalej p67 =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 z
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ędz
, 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
z
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 z
ródła s do danego
wierzchołka (d[v] jest oszacowaniem wagi drogi ze z
ródła do v). Tablica p przechowuje poprzedników na
120 Analiza algorytmów - ćwiczenia
2
5
1
8
4
9
3
6
7
D 1 2 3 4 5 6 7 8 9 P 1 2 3 4 5 6 7 8 9
1 0 1 1 2 2 3 4 3 4 1 0 2 3 2 2 2 2 2 2
2 1 0 2 1 1 2 3 2 3 2 1 0 1 4 5 4 4 5 5
3 1 2 0 1 2 2 3 3 4 3 1 1 0 4 4 4 4 4 4
4 2 1 1 0 1 1 2 2 3 4 2 2 3 0 5 6 6 5 6
5 2 1 2 1 0 2 2 1 2 5 2 2 4 4 0 4 8 8 8
6 3 2 2 1 2 0 1 2 2 6 4 4 4 4 4 0 7 7 7
7 4 3 3 2 2 1 0 1 1 7 6 6 6 6 8 6 0 8 9
8 3 2 3 2 1 2 1 0 1 8 5 5 5 5 5 7 7 0 9
9 4 3 4 3 2 2 1 1 0 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 z
ródła do wierzchołków grafu (p[v] jest poprzednim w stosunku do v wierzchołkiem
na chwilowo najkrótszej drodze ze z
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 z
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 z
ródłowym wierzchołku s polega na
sprawdzeniu, czy przechodząc przez wierzchołek u, można znalez
ć 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ędz
(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 z
ródłem d[v] =", dla z
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 u,v: nr wierzchołków
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 z
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 s: z
ródło
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 + u ;
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. y
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. Wnajprost-
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(n2). 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ędz
jest analizowana jeden raz, a więc ostatecznie algorytm działa w czasie
O(n2 + e) =O(n2), ponieważ w pesymistycznym przypadku liczba krawędzi jest rzędu O(n2)).
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. A
ą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ą hd(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 ,k2"Kk1 = k2 =Ò! h(k1) = h(k2)

1
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. hd(x1, x2, x3) =Ć +Ć +Ć
x1 x1 x2
b. hd(x1, x2, x3) =Ć +Ć +Ć
x1 x2 x2
c. hd(x1, x2, x3) =Ć +Ć +Ć
x2 x2 x3
d. hd(x1, x2, x3) =Ć +Ć +Ć
x2 x3 x3
gdzie x1, x2, x3 oznaczają kolejne znaki słowa, natomiast x1, x2, x3 to kody znaków. Wyznaczenie funkcji
Ć Ć Ć
mieszającej oznacza przyporządkowanie znakom odpowiednich kodów. Zauważmy, że 0 xi m-1 =10
Ć
dla każdego znaku xi.
ad. a.hd(x1, x2, x3) =Ć +Ć +Ć
x1 x1 x2
Sprawdz
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.hd(x1, x2, x3) =Ć +Ć +Ć
x2 x2 x3
Sprawdz
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. hd(x1, x2, x3) =Ć +Ć +Ć
x1 x2 x2
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:
hd(x1, x2, x3) =Ć +Ć +Ć =2 · x1 +1· x2 +0· x3
x1 x1 x2 Ć Ć Ć
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
wstaw x na poczÄ…tku listy T[h(key(x))]
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
usuń x z listy T[h(key(x))]
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łą.
O(rozmiar tablicy)
liczba elementów w tablicy = O(rozmiar tablicy) =Ò! Ä… = = O(1)
rozmiar tablicy
132 Analiza algorytmów - ćwiczenia
1 procedure szukaj miesz(T, k);
2 begin
wyszukaj element o kluczu k na liście T[h(k)]
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;
błąd przepełnienie tablicy
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;
błąd brak elementu
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;
błąd brak elementu
11 end.
10.9. Algorytm szukania w tablicy z mieszaniem zamkniętym
134 Analiza algorytmów - ćwiczenia
liniowa
h(k, i) =(h1(k) +i) mod m
kwadratowa
h(k, i) =(h1(k) +c1 · i + c2 · i2) mod m
dwukrotna
h(k, i) =(h1(k) +i · h2(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
1 1
Średnia liczba prób wstawienia i-ego klucza wynosi: Eśr(i) = =
i-1
1-Ä… 1-
m
Średnia suma wykonanych prób:
7

Eśr(i) H" 18, 15
i=1
Rozdział 10: Funkcje mieszające 135
10.5. Zadania
1. Dla danej funkcji mieszającej h(k, i) = (k + i + i2) 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); wykonanie żądanych operacji na obiekcie
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 {a1, a2, . . . , an} 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 Pi
i =1, . . . , (n - 1)!.
Tworzymy uporządkowaną listę permutacji n elementów generując n nowych permutacji z każdej
permutacji Pi przez wstawianie liczby n między elementy Pi. Miejsc, w które można wstawić ten
nowy element jest n. Dla nieparzystych i element n wstawiamy od prawej do lewej strony Pi, 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 (ai , ai , . . . , ai ) poprzedza leksykograficznie permutację (aj , aj , . . . , aj )
1 2 n 1 2 n
wtedy i tylko wtedy, gdy dla pewnego k, 1 k n, ip = jp dla 1 p 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 (a1, a2, . . . , an).
PrzeglÄ…dajÄ…c elementy od prawej strony, tzn. od an w kierunku a1, znajdz
pierwszÄ… pozycjÄ™, dla
której ai Przeglądając elementy położone na prawo od ai znajdz
element aj taki, że jest on najmniejszy
spośród elementów większych od ai.
Zamień miejscami element ai z aj.
Odwróć kolejność elementów (ai+1, . . . , an). 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 ai 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Ä… znalez
ć się tylko całkowite
liczby nieujemne mniejsze od i. A
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 tn = 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 znalez
ć się liczba n - k. Podobnie można znalez
ć 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 di takich, że 0 di dkdk-1dk-2 . . . d0, dk =0

wyznaczamy jej wartość następująco:
N = d0 + d1r + d2r2 + . . . + dkrk.
Dla systemu dziesiętnego r = 10.
W niejednorodnych systemach pozycyjnych zamiast r stosowany jest ciÄ…g liczb naturalnych r0, r1, . . . , rk-1.
Wtedy podanemu wcześniej ciągowi odpowiada wartość
k-1

N = d0 + d1r0 + d2r0r1 + d3r0r1r2 . . . + dk ri
i=0
gdzie 0 di
jest zapis czasu w formacie DHMS (dni, godziny, minuty, sekundy). Dla takiego formatu r0 = 60, r1 = 60,
r2 = 24.
Rozdział 11: Generowanie obiektów kombinatorycznych 141
W omawianym problemie wyznaczania tablic inwersji pomocny będzie tzw. silnia-system:
N = d00! + d11! + d22! + . . . + dkk!
gdzie 0 di
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 znalez
ć 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 2n, licząc łącznie ze zbiorem pustym. Tworzenie podzbiorów
jest równoważne tworzeniu n-bitowych ciągów binarnych. Element ai 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 2n - 1 i zamiana tej liczby
na postać dwójkową.
Aby wygenerować k-elementowy, losowy podzbiór zbioru S = {a1, a2, . . . , an}, 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 {ai , ai , . . . , ai } jest równe iloczynowi prawdopodobieństw zdarzeń:
1 2 k
k
Pr(pierwszy wybrany element jest jednym z {ai , ai , . . . , ai }) =
1 2 k
n
k-1
Pr(drugi wybrany element jest jednym z pozostałych k - 1 elementów) =
n-1
k-2
Pr(drugi wybrany element jest jednym z pozostałych k - 2 elementów) =
n-2
. . .
1
Pr(k-ty wybrany element jest ostatnim pozostajÄ…cym elementem) =
n-k+1
Iloczyn ten jest równy:
k k - 1 1 k!(n - k)! 1
n
· · . . . · = =
n n - 1 n - k +1 n!
k
n
Ponieważ k-elementowych podzbiorów jest dokładnie , więc każdy z nich zostanie wylosowany z jedna-
k
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
n
trzeba będzie przetworzyć 2n podzbiorów, tymczasem kombinacji jest tylko .
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ż 2n, 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:
ëÅ‚ öÅ‚
0 G(n - 1, k)
Å‚Å‚
G(n, 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Ä…giemn 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Ä…dz
pewnej liczby podzbiorów. Opisany dalej generator przekształca liczbę naturalną i "
n
0, - 1 na i-ty podzbiór w pewnym uporządkowaniu. Istnieje wiele metod generacji podzbiorów
k
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. A
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
n
dokładnie dróg prowadzących do korzenia, czyli tyle, ile wynosi wartość odpowiedniego elementu
k
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
n+1 n
n
dróg z tych dwóch wierzchołków i tyle jest też równa wartość elementu (n +1, k): = +
k k-1 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śledz
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).
n-1
Przyjmiemy, że początkowych numerów oznacza drogi skręcające do (n-1, k-1), a pozostałe (czyli
k-1
n-1 n-1
numerów) drogi skręcające do (n - 1, k). Mając numer drogi wystarczy więc porównać go z
k 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ądz
zera, zależnie od założeń),
n-1
czyli odjąć od niego . W ten sposób uzyskujemy algorytm przedstawiony jako pseudokod 11.4.3..
k
S
Zamiast wyznaczania w każdym obiegu iteracji można również skorzystać z zależności:
p

n - 1 n n - k
= · ,
k k n

n - 1 n k
= · ,
k - 1 k n
S
unikając w ten sposób wielokrotnego wyznaczania wartości . Złożoność takiego algorytmu jest rzędu
p
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
Å„Å‚ Å„Å‚ Å„Å‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
1234
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ òÅ‚
ôÅ‚ ôÅ‚
1243
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
123
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
1423
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ół
ôÅ‚ ôÅ‚
4 123
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ Å„Å‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
4 132
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ òÅ‚ òÅ‚
ôÅ‚
1432
ôÅ‚
ôÅ‚
ôÅ‚ 12 132
ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
1342
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ół
ôÅ‚ ôÅ‚
1324
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ Å„Å‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
3124
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ òÅ‚
ôÅ‚ ôÅ‚
3142
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ 3 12
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
3412
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
òÅ‚ ół ół
4 312
Å„Å‚ Å„Å‚
1
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
4 321
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ òÅ‚
ôÅ‚ ôÅ‚
3421
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ 3 21
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
3241
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ół
ôÅ‚ ôÅ‚
3214
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ Å„Å‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
2314
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ òÅ‚ òÅ‚
ôÅ‚
2341
ôÅ‚
ôÅ‚
2 1 231
ôÅ‚
ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
2431
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ół
ôÅ‚ ôÅ‚
4 231
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ Å„Å‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
4 213
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ òÅ‚
ôÅ‚ ôÅ‚
24 13
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ 213
ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
2143
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ôÅ‚ ôÅ‚ ôÅ‚
ół ół ół
2134
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Ä…dz
od lewej do prawej strony poprzedniej permutacji.
Rozdział 11: Generowanie obiektów kombinatorycznych 147
1 procedure SilniaSystem;
2 begin
3 Dane wejściowe: liczba N
4 Dane wyjściowe: ciąg cyfr d0, d1, . . . , dk będący zapisem N w silnia-systemie
5 d0 := 0; najstarsza cyfra zawsze równa 0
6 q := N;
7 k := 0;
8 while q =0 do

9 dk := q mod rk; kolejna cyfra
10 q := q div rk;
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 n: nr kombinacji od 0, S: liczba elementów zbioru, p: liczba elementów podzb.
4 v, lewy r, prawy r, i: zmienne cakowite
5 n := n +1; ...teraz kombinacje sÄ… numerowane od 1
6 i := 0; nr pierwszego elementu zbioru
7 while S > 0 do
S
8 v := ; wartość bieżącego elementu trójkąta
p
S-1
9 prawy r := ;  prawy rodzic
p
10 if p 11 lewy r := v - prawy r;
12 else
13 lewy r := 1;  lewy rodzic
14 end if;
15 S := S - 1;  piętro w górę
16 if n >lewy r then idziemy w prawo do góry
17 n := n - lewy r;
18 writeln( element  ,i,  nie należy do podzbioru );
19 else idziemy w lewo do góry
20 writeln( element  ,i,  należy do podzbioru );
21 p := p - 1; zmniejszamy liczbę elementów podzbioru ( k )
22 end if;
23 i := i +1; nr kolejnego elementu zbioru
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). y
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) wkolejności
przeciwnej do ruchu wskazówek zegara. Algorytm przedstawia pseudokod 12.2..
1 procedure Graham Scan(Q);
2 begin
3 znajdz
w zbiorze Q punkt p0 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 p1, p2, . . . , pn-1;
7 wyzeruj stos S;
8 Push(S, p0);
9 Push(S, p1);
10 Push(S, p2);
11 for i := 3 to n - 1 do
12 while kąt (Next to top(S), Top(S), pi) nie oznacza skrętu w lewo do
13 Pop(S);
14 end while;
15 Push(S, pi);
16 end for;
17 return S; w S jest szukana otoczka
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 p0 i pozostałe, ponumerowane w kolejności rosnących kątów w biegunowym układzie współ-
rzędnych o początku w p0. Zaznaczone są też trzy początkowe punkty p0, p1 i p2 odłożone na stos S.
Rysunek (b) przestawia sytuację po próbie odłożenia na S kolejnego punktu, p3. Przed jego odłożeniem
sprawdzono, czy przechodząc z p1 przez p2 do p3 skręcamy w lewo. Okazało się, że nie. Wobec tego ze
stosu został zdjęty jeden punkt (p2). Ponownie sprawdzono, czy przechodząc z przedostatniego punktu
na stosie (p0) przez ostatni (p1) do p3 skręcamy w lewo. Tym razem okazało się, że tak. Dlatego punkt
p2 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 znalez
ć 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 p0 i p1, wystarczyłoby
odnalezienie p0 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 p1 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 p2. 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 pk). 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).
A
ą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. y
ródło: [1].
154 Analiza algorytmów - ćwiczenia
12.3. Działanie algorytmu Graham Scan, cz. 2. y
ródło: [1].
Rozdział 12: Algorytmy geometryczne: wypukła otoczka 155
12.4. Przykładowa realizacja algorytmu Jarvisa. y
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 Hn: ln n1.4 Szacowanie od góry wartości Hn: Hn < 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 Ilustracja 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 Ilustracja 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 Ilustracja 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. y
ródło: [1]. . . . . . . . . . . . . . . . . . . . . . 104
7.8 Ilustracja Ä… ² obciÄ™cia. y
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. y
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Ä…dz
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). y
ródło: [1]. . . . . . 149
12.2 Działanie algorytmu Graham Scan, cz. 1. y
ródło: [1]. . . . . . . . . . . . . . . . . . . . . . 153
12.3 Działanie algorytmu Graham Scan, cz. 2. y
ródło: [1]. . . . . . . . . . . . . . . . . . . . . . 154
12.4 Przykładowa realizacja algorytmu Jarvisa. y
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