10. Drzewa i lasy

10.1. Rekurencyjna definicja drzewa

Drzewo, podobnie jak omawiana w rozdziale poprzednim lista, jest strukturą, którą możemy zdefiniować w sposób rekurencyjny.

Oto ta definicja:

Niech wierzchołek w (element drzewa) będzie typ T, wtedy:

1. Jeżeli dowolna, skończona, rozłączna i nie należąca do
drzewa liczba wierzchołków typu T, do niego dowiązanych

jest drzewami, to w jest drzewem.

2. Zbiór pusty wierzchołków jest drzewem.

Jest to typowa definicja rekurencyjna, w której punkt 2 stanowi warunek stopu definicji.

Pojęcie wierzchołek (węzeł) i dowiązanie (łuk) zostały zapożyczone z teorii grafów. Poniższy rysunek objaśnia podaną definicję.

root

root

a)

. . .

b)

Rys. 2.9 Rekurencyjna definicja drzewa: a) drzewo puste, b) drzewo niepuste.

Zbiór pusty wierzchołków uznajemy za drzewo. Podobnie drzewem jest pojedynczy wierzchołek w, do którego jednakże, podobnie jak do pustego wierzchołka, dowiązać możemy dowolną (ale skończoną) ilość wierzchołków w₁, w₂, . . . , w_n . Żądamy, aby wszystkie te wierzchołki były rozłączne, tzn. aby nie było między nimi bezpośrednich wskazań. Żądamy też, aby nie należały już do drzewa, tzn. aby nie były wskazywane przez jakikolwiek wierzchołek należący już do drzewa. Każdy z wierzchołków w₁, w₂, . . . , w_n może zawierać elementy dowiązane według powyższej zasady. Każdy z wierzchołków (np. w₁, w₁₂), niezależnie od tego czy jest pojedynczym wierzchołkiem, czy też zawiera elementy do niego dowiązane, możemy nazywać drzewem (chociaż lepiej używać określenia poddrzewo), rezerwując pojecie drzewa dla wierzchołka w a jeszcze lepiej dla wskazania root.

Wracając do podanego wcześniej stwierdzenia, że lista liniowa jednokierunkowa jest szczególnym przypadkiem drzewa, możemy teraz uściślić, że taka lista jest drzewem, w którym dla każdego wierzchołka liczba dowiązanych elementów jest nie większa niż 1.

Na koniec zauważmy jeszcze, że podobnie jak dla listy, aby wierzchołki były rozróżnialne, muszą mieć przynajmniej jedno pole przechowujące etykietę wierzchołka. Wymagania tego nie muszą spełniać struktury zwane wyrażeniami kropkowymi, o których będzie mowa w dalszej części wykładu.

10.2. Problemy związane z reprezentacją drzew

Poniższa, rekurencyjna definicja elementu drzewa spełnia wszystkie, opisane wyżej, warunki bycia wierzchołkiem tak zdefiniowanego drzewa

struct TREE

{ int klucz; ( 1 )

TREE *father;

};

father jest zmienną wskazującą, która może przechowywać wskazania do elementu na poziomie o jeden wyższym.

Rys. 2.10 Przykład drzewa, jakie można wygenerować korzystając z rekurencyjnej
definicji wierzchołka ( 1 )

Definicja wierzchołka drzewa ( 1) wydaje się bardzo atrakcyjną. Pozwala bowiem, przy użyciu tylko jednego wskaźnika, na budowanie drzew o dowolnej strukturze.

Łatwo jednak dostrzegamy jej wady:

• brak wskazania do całego drzewa,

• możliwość poruszania się w drzewie tylko jedną ścieżką, od wybranego wierzchołka w kierunku pojedynczego węzła na szczycie drzewa.

Wady te są tak poważne, że w praktyce niesłychanie rzadko sięga się do takiej reprezentacji. Zauważmy, że reprezentacja ze wskazaniami odwrotnymi, od węzła głównego do węzłów dowiązanych, też nastręcza trudności. Wymagałaby bowiem użycia w definicji węzła nieskończonej liczby wskaźników aby sprostać żądaniu dowolnie dużej ilości węzłów dowiązanych

struct TREE

{ int klucz;

TREE *p1;

TREE *p2; ( 2 )

. . . . . . . . .

TREE *pn;

};

Pojawia się problem omawiany przy okazji statyczności tablic. Przyjęcie, jako maksymalnej ilości węzłów dowiązanych, pewnej stałej wartości n jest niewygodnym ograniczeniem, ilość ta bowiem może okazać się niewystarczająca. Z kolei, przyjęcie zbyt dużej wartości n obciąża niepotrzebnie pamięć - każdy z wierzchołków posiada wtedy wiele wskaźników, z których większość nie będzie wykorzystywana.

Na szczęście, w praktyce używa się zwykle drzew, w których maksymalna ilość wierzchołków dowiązanych jest stała a wartość n niewysoka, np. dwa (mówimy wtedy o drzewie stopnia drugiego, tzw. drzewie binarnym), lub trzy (drzewo stopnia trzeciego), itd.

root

Rys. 2.11 Przykład drzewa binarnego ( ptr - wskazanie dowolnego węzła drzewa)

10.3. Definicje podstawowych pojęć

W rozdziale tym zdefiniujemy sobie szereg podstawowych pojęć, które stanowią swoisty język porozumiewania się ludzi zajmującymi się drzewami i lasami (nie drwali oczywiście !). Przyjmiemy reprezentacje jak dla drzewa na rys. .

1. Wierzchołki, które są bezpośrednio dowiązane do danego wierzchołka, nazywamy jego bezpośrednimi potomkami, albo bezpośrednimi następnikami (synami węzła).
   

2. Z kolei - wierzchołek taki nazywać będziemy bezpośrednim poprzednikiem (ojcem) tych węzłów.

3. Synów tego samego ojca nazywamy braćmi.

4. Wierzchołek, który nie ma bezpośredniego poprzednika nazywamy korzeniem drzewa. Korzeniem drzewa nazywa się też wskazanie do tego elementu. Jest to jednocześnie wskazanie do całego drzewa.

5. Wierzchołki, które nie mają bezpośrednich następników, nazywamy liśćmi drzewa. Na rys. 2.11 są to węzły o etykietach 8, 2 i 5.

6. Elementy nie będące liśćmi nazywamy węzłami wewnętrznymi drzewa.

7. Drzewem uporządkowanym nazywamy drzewo, w którym dla każdego węzła wewnętrznego na jego synach określona jest ta sama relacja liniowego porządku. Drzewo przedstawione na rys. 2.11 jest przykładem drzewa uporządkowanego z relacją mniejszości <. Wszystkie drzewa, którymi będziemy się zajmować w dalszej części wykładu będą drzewami uporządkowanymi.

8. Jeżeli dany węzeł ma poziom i, to wszystkie jego bezpośrednie następniki mają poziom i+1_­­­. Założymy, że korzeń drzewa ma poziom 1.

9. Maksymalny poziom wierzchołków drzewa nazywamy wysokością albo głębokością drzewa.

10. Stopniem drzewa nazywamy maksymalną liczbę wierzchołków, jakie można dowiązać do każdego z węzłów. Drzewo przedstawione na rys. jest stopnia drugiego (jest drzewem binarnym). Można rozpatrywać drzewa, w których maksymalna liczba wierzchołków dowiązanych jest różna dla różnych węzłów. Dla takich drzew nie określa się stopnia drzewa a jedynie stopień jego wierzchołków.
    

11. Ścieżką w drzewie jest ciąg jego wierzchołków a₁, a₂, . . . ,a_n taki, że dla każdego i = 2, 3, . . . , n para (a_i-1, a_i ) jest krawędzią, łączącą dany wierzchołek wewnętrzny z jego bezpośrednim potomkiem. Wierzchołki wewnętrzne to zbiór wszystkich wierzchołków drzewa za wyjątkiem liści.
    

12. Liczba krawędzi, jaką trzeba przejść od korzenia do poziomu danego wierzchołka w nazywamy długością drogi wierzchołka w. Długość drogi korzenia wynosi 1. Ogólnie - długość drogi wierzchołka na poziomie i wynosi i.
    

13. Długością drogi wewnętrznej drzewa nazywamy sumę długości dróg wszystkich jego wierzchołków. Można ją przedstawić za pomocą wzoru
    i=1
    d = ∑ n_i * i
    g
    gdzie i - oznacza poziom węzła,
    n_i - jest liczbą węzłów na poziomie i,
    g - jest głębokością drzewa.
    
    Drzewo z rys. 2.5 ma długość drogi wewnętrznej d = 1 + 2*2 + 3*3 = 14.

14. Lasem nazywać będziemy uporządkowany zbiór drzew uporządkowanych. Uporządkowanie drzew w lesie polega na uporządkowaniu korzeni kolejnych drzew. Spina się je w las poprzez umieszczenie wskaźników do ich korzeni w tablicy, albo w liście wskaźników.

10.4. Algorytm tak zwanego naturalnego przekształcenia dowolnego lasu w drzewo

binarne

Jest zupełnie naturalnym, że algorytmy obsługi drzew o ustalonym, niewysokim stopniu, będą prostsze i bardziej efektywne niż algorytmy dotyczące drzew charakteryzujących się dość dużą dowolnością.

Dlatego bardzo atrakcyjnym wydaje się być algorytm, który umożliwia przekształcenie dowolnego lasu, złożonego z dowolnej ilości drzew o różnych stopniach, w pojedyncze drzewo binarne.

las 0 1 2 ... N-1

Rys. 2.12 Las złożony z dwóch drzew. N-elementowa tablica wskaźników las przechowuje
wskazania do kolejnych drzew w lesie.

Algorytm ten można skonstruować, wg. niżej podanych kroków:

1. Przyjmij za korzeń drzewa binarnego korzeń pierwszego drzewa w lesie.

2. Przenoś kolejne węzły drzew lasu do drzewa binarnego w ten sposób, aby:
   2.1. ich pola left wskazywały listę wiązaną synów tego węzła w drzewie
   oryginalnym
   2.2. lista ta była wiązana poprzez pola right każdego z przenoszonych węzłów
   2.3. zasada ta dotyczy również wiązania korzeni poszczególnych drzew lasu

Po przekształceniu lasu w drzewo binarne i wykonaniu na nim wszystkich niezbędnych operacji, takich jak: wyszukanie węzła, modyfikacja jego zawartości, bądź nawet usunięcie lub wstawienie nowego węzła, drzewo binarne można z powrotem przekształcić do pierwotnej, naturalnej postaci.

root

Rys. 2.13 Drzewo binarne powstałe z przekształcenia lasu przedstawionego na rys.2.12.

10.5. Algorytmy obsługi drzew binarnych

Szczególnie dużo miejsca poświęcimy drzewu binarnemu, gdyż jest to najczęściej wykorzystywana postać drzewa. Przyjmijmy następującą definicję typu dla węzłów drzewa binarnego

struct BIN

{ int klucz;

BIN *left;

BIN *right;

};

Z faktu, że każde drzewo można zdefiniować w sposób rekurencyjny, a także rekurencyjna jest definicja jego węzłów, wynika łatwość zapisu algorytmów obsługi drzewa w postaci rekurencyjnej.

10.5.1. Przeglądanie drzewa binarnego

Niech Q(ptr) będzie operacją, którą trzeba wykonać na węźle wskazywanym przez ptr, oraz wszystkich węzłach leżących poniżej węzła wskazywanego przez ptr (patrz rys. 2.11 ). Jeśli ptr=root, czyli wywołamy procedurę Q dla wskazania korzenia drzewa, wtedy procedura ta wykonana zostanie dla całego drzewa.

Rys. 2.14 Węzły drzewa binarnego

Rekurencyjną metodę zapewniającą przejrzenie całego drzewa o dowolnym kształcie i rozmiarach począwszy od węzła wskazywanego przez ptr (węzeł A na rys. 2.14) sformułować można następująco:

Wykonaj żądaną operację na węźle, w którym się znajdujesz a następnie zgodnie z przyjętą zasadą odwiedź lewy wierzchołek dowiązany, następnie zgodnie z przyjętą zasadą odwiedź prawy wierzchołek dowiązany.

W tym opisie metody najważniejszym jest sformułowanie „zgodnie z przyjętą zasadą”. Tutaj bowiem ukryte jest rekurencyjne wywołanie metody. Uzyskany efekt najlepiej obrazuje poniższy rysunek.

root

Rys. 2.15 Kolejność wykonywania operacji Q(ptr) na węzłach drzewa binarnego przy

użyciu metody preorder.

Mamy tu do czynienia ze schematem odwiedzania węzłów drzewa binarnego, który naz-wany został metodą zstępującą, albo metoda porządku poprzedzającego (z ang. preorder ).

Jest to schemat A - B - C.

Dwa dalsze możliwe schematy odwiedzania węzłów to:

• B - A - C inorder - metoda wstępująca lub porządek następujący,

• B - C - A postorder - metoda symetryczna lub porządek wewnętrzny.

Rekurencyjna funkcja zapewniająca, przy zastosowaniu metody preorder, wykonanie procedury Q(ptr) dla całego poddrzewa wskazywanego przez ptr będzie miała w notacji języka C/C++ postać:

void preorder ( BIN *ptr)

{

if (ptr)

{

Q(ptr);

preorder(ptr → left); preorder(ptr → right);

}

}

10.6. Drzewa binarnych poszukiwań

Podobnie jak w przypadku listy liniowej, bardzo opłacalnym jest wstawianie kolejnych wierzchołków do drzewa binarnego w sposób zapewniający jego uporządkowanie.

Dzięki uporządkowaniu listy liniowej średni czas wyszukania elementu w takiej liście skracał się o połowę. Korzyści, jakie osiągamy dla drzewa binarnego uporządkowanego są nieporównywalnie większe.

Niech poniższy ciąg nie powtarzających się liczb całkowitych będzie ciągiem kluczy, które chcemy wstawić do drzewa binarnego w sposób uporządkowany.

7 3 6 9 1 8 5

Poszukując liścia, którego następnikiem ma być kolejny wstawiany wierzchołek, zastosujmy następującą rekurencyjną metodę:

1. jeśli wartość wstawiana jest mniejsza od wartości klucza badanego węzła należy poprzez pole left przejść do lewego węzła,

2. jeśli wartość wstawiana jest większa od wartości klucza badanego węzła należy poprzez pole right przejść do prawego węzła,

3. powyższe można zakończyć po napotkaniu węzła, którego lewe, lub prawe wskazanie jest wskazaniem pustym, wskazania tego należy użyć w celu wstawienia węzła.

Zauważmy, że poszukując miejsca wstawienia nowego węzła poruszamy się wzdłuż jednej tylko ścieżki w drzewie i że miejsce wstawienia jest tylko jedno.

Wyżej opisana metoda wstawiania węzłów do drzewa binarnego, chociaż ma w istocie charakter rekurencyjny (pk. 3 metody stanowi warunek stopu), to ze względu na to, że poruszamy się wzdłuż jednej tylko ścieżki, może być łatwo zrealizowana za pomocą algorytmu iteracyjnego.

Otrzymane w ten sposób drzewa binarne, ze względu na swe szczególne, opisane niżej, własności nazywamy drzewami binarnych poszukiwań (DBP).

root

Rys. 2.16 Drzewo binarnych poszukiwań wygenerowane po otrzymaniu ciągu kluczy

7 3 6 9 1 8 5

Generowanie drzew binarnych poszukiwań stanowi jedną z najdoskonalszych metod sortowania informacji. Aby bowiem znaleźć w drzewie wierzchołek o określonej wartości klucza, lub stwierdzić, że klucz o takiej wartości nie występuje w drzewie, wystarczy poruszać się wzdłuż jednej tylko ścieżki. Dla przykładu, aby w drzewie binarnych poszukiwań, przedstawionym na rys. znaleźć węzeł o kluczu 9, potrzeba tylko dwóch porównań, węzeł o kluczu 6 - tylko trzech porównań.

Oto pełna definicja drzewa binarnych poszukiwań:

Drzewem binarnych poszukiwań nazywać będziemy drzewo binarne, w którym dla każdego węzła wewnętrznego klucz jego lewego następnika jest mniejszy, a klucz prawego następnika - większy, od klucza tego węzła.

Bardziej formalnie przedstawimy to następująco:

∀ ( if ptr → left <> 0 then ptr → left → klucz < ptr → klucz;

ptr<>0 if ptr → right <> 0 then ptr → right → klucz > ptr → klucz; )

Maksymalna liczba porównań, jakie trzeba wykonać, aby znaleźć jakikolwiek wierzchołek, jest równa wysokości DBP.

Oczywiście im drzewo jest mniej zrównoważone (ma mniejszą wysokość), tym maksymalna liczba porównań jest większa. Stopień zrównoważenia drzewa będzie (co nie występuje w liście uporządkowanej), silnie zależał od kolejności, w jakiej pojawiają się klucze węzłów wstawianych. Im ciąg kluczy jest mniej uporządkowany, tym generuje lepsze drzewo (bardziej zrównoważone). Drzewa binarnych poszukiwań mają więc cechę jak gdyby odwrotnej wrażliwości na uporządkowanie, co jest cechą bardzo pozytywną.

W idealnym przypadku - drzewa dokładnie wyważonego (definicję takiego drzewa podamy później), drzewo binarne o wysokości n zawiera aż 2ⁿ - 1 węzłów. Korzyści, jakie osiągamy z użycia DBP do sortowania danych, wzrastają więc nieprawdopodobnie szybko ze wzrostem ilości tych danych, co jest kolejną pozytywną cechą DBP. Obrazuje to poniższa tabela

Ilość węzłów w DBP	Maksymalna liczba porównań
1 3 15 1023 16383 65535	1 2 4 10 14 16

Rys.2.17 Zależność między ilością węzłów w DBP a maksymalną ilością porównań, jakich

trzeba dokonać, aby znaleźć wierzchołek o żądanym kluczu w dokładnie wywa-

żonym DBP.

10.7. Drzewa wyważone i dokładnie wyważone

Jak już zauważyliśmy, korzyści jakie wynosimy, używając drzew binarnych poszukiwań, są tym mniejsze, im bardziej uporządkowany jest ciąg kluczy kolejno wstawianych węzłów. W skrajnym przypadku, uporządkowanego ciągu kluczy, drzewo binarnych poszukiwań degeneruje się do uporządkowanej listy liniowej, gdzie średni czas wyszukiwania jest tylko rzędu n/2 (n jest ilością węzłów).

W takich sytuacjach warto konstruować tak zwane drzewa wyważone (niekiedy zwane zrównoważonymi) i drzewa dokładnie wyważone.

Drzewem wyważonym (zrównoważonym) nazywamy drzewo binarne, w którym dla każdego węzła wysokość jego lewego i prawego poddrzewa różni się nie więcej niż o jeden. Od nazwisk odkrywców zostały one również nazwane drzewami AVL-wyważonymi.

a) b)

Rys. 2.18 Przykłady drzew: a) drzewo wyważone (zrównoważone), b) drzewo dokładnie
wyważone

Z kolei drzewem dokładnie wyważonym nazywać będziemy drzewo binarne, w którym dla każdego węzła liczba węzłów w jego lewym i prawym poddrzewie różni się nie więcej niż o jeden. Tak więc nie każde drzewo wyważone musi być drzewem dokładnie wyważonym.

Zajmijmy się nieco szczegółowiej drzewami dokładnie wyważonymi. Ich zasadniczą cechą jest to, że mają one (dla danej ilości węzłów) najmniejszą wysokość, a co za tym idzie najkrótszy czas wyszukiwania spośród wszystkich drzew binarnych nieuporządkowanych. Jest on rzędu log n (gdzie n jest liczbą węzłów drzewa).

Szczegółowa analiza, poparta badaniami empirycznymi, pokazała, że drzewa wyważone dają średnio nieco tylko gorsze wyniki czasu wyszukiwania w porównaniu z drzewami dokładnie wyważonymi [3]. Tymczasem algorytmy wyważania drzewa, po każdym losowym wstawieniu nowego węzła, lub usunięciu istniejącego, są znacznie prostsze dla drzewa wyważonego, niż dla dokładnie wyważonego.

Wniosek końcowy jest następujący. Tam, gdzie stosunek liczby odczytów wartości z węzłów drzew do ilości wstawień, lub usunięć węzłów istniejących, jest duży, warto dla bardzo dużych drzew, utrzymywać drzewo w postaci dokładnie wyważonego, lub nawet tylko wyważonego. Bowiem czas, jaki zostanie stracony na skomplikowane i bardzo kosztowne (ale rzadko wykonywane) procedury wyważania drzewa, zostanie z nawiązką zwrócony w postaci bardzo skróconego czasu wyszukiwania.

Pamiętajmy, że drzewo binarnych poszukiwań jest bardzo atrakcyjną formą przechowywania danych, pod warunkiem jednak, że ciąg pojawiających się kluczy ma wysoki stopień nieuporządkowania, co pozwala generować dość dobrze wyważone drzewa DBP. Jeśli jednak tak nie jest, drzewo DBP może mieć dość znaczną wysokość, i długie czasy wyszukiwania. Dlatego dla dużych drzew warto, aby były one w postaci drzew wyważonych, bądź dokładnie wyważonych.

10.8. Drzewa z prioritetem (HPO-drzewa albo Kopce)

W rozdziale poświęconym listom omówiliśmy listy z prioritetem (HPO-kolejki). Zupełnie podobne zastosowania mają drzewa z prioritetem, zwane również HPO-drzewami, lub kopcami.

Rys. 2.19 Przykładowy kopiec. „Dymki” z wartością 11 w środku wskazują dopuszczalne
miejsca wstawienia węzła o wartości prioritetu równej 11.

HPO-drzewa są to drzewa binarne uporządkowane według prioritetów i zbudowane według zasady:

Dla każdego węzła wewnętrznego prioritety jego następników są nie większe od prioritetu tego węzła.

W drzewie takim węzeł o najwyższym prioritecie znajduje się zawsze w korzeniu. Podobnie jak w HPO-kolejce do węzła tego istnieje bezpośredni (a więc bardzo szybki) dostęp poprzez wskazanie do całego drzewa.

W praktycznych zastosowaniach, zwłaszcza tam, gdzie ilość węzłów jest znaczna, chętniej korzysta się z kopców, niż z HPO-kolejek. Wynika to z sumarycznie mniejszych kosztów obsługi drzewa w porównaniu z kosztami obsługi kolejki.

Tę pozorną sprzeczność łatwo uzasadnić. Większość operacji, takich jak: wstawienie nowego węzła, usunięcie węzła, zmiana jego prioritetu, poprzedzone jest wyszukiwaniem. Operacja wyszukiwania, o czym już mówiliśmy, jest bardziej efektywna w drzewie binarnym, niż w liście liniowej (zwłaszcza w drzewie binarnym wyważonym).

Warto więc, przy dużej ilości węzłów, pakować je do kopca, starając się przy tym robić to w ten sposób, aby zachowywać duże zrównoważenie kopca. Nie jest to zbyt trudne z uwagi na fakt, że odwrotnie niż w drzewie binarnych poszukiwań, miejsc wstawienia nowego węzła może być więcej. Dotyczy to również węzłów, które na skutek zmiany prioritetu muszą być wypięte ze swojego dotychczasowego miejsca i wstawione w nowe miejsce. Na rys. 2.19, prezentującym przykładowy kopiec, pokazano możliwe miejsca wstawienia nowego węzła o prioritecie 11.

10.9. Wyrażenia kropkowe

Bardzo szczególną postacią drzew są drzewa przechowujące tzw. wyrażenia kropkowe. Nazwa pochodzi od tradycyjnego sposobu ich przedstawiania przy użyciu nawiasów okrągłych i kropek, chociażby z języku LISP. Jest to język deklaratywny, w którym podstawowymi strukturami danych są właśnie wyrażenia kropkowe oraz listy. Stąd nazwa języka - LIStProcessor.

Reprezentantem wyrażenia kropkowego jest drzewo binarne uzupełnione (w którym wszystkie węzły wewnętrzne mają dwóch następników), posiadające etykiety (wartości) tylko na liściach.

( ( a . ( b . c ) ) . d )

a) b)

Rys. 2.20. Przykład wyrażenia kropkowego: a) reprezentacja w postaci drzewa, b) zapis „kropkowy”

Drzewa takie mają dwa rodzaje węzłów: węzły wewnętrzne bez etykiet (nazwijmy je węzłami kropkowymi), przechowujące informacje o strukturze całego wyrażenia kropkowego, oraz „normalne” węzły na liściach drzewa.

Możemy więc przy ich pomocy przedstawić, na przykład, strukturę rozgrywek piłkarskich: (( Wisła . ( Legia . Widzew ) ) . Amica ), albo też przypisując węzłom kropkowym operatory arytmetyczne, przedstawić strukturę wyrażenia arytmetycznego: (( a * ( b + c )) - d ).

W pierwszym z dwóch wyżej wymienionych przykładów zastosowań, kropka pełnić może role operatora wyłaniającego zwycięzcę lewego i prawego argumentu, w drugim - operatora pozwalającego znaleźć wartość wyrażenia arytmetycznego lewego i prawego argumentu. Jest to więc bardzo wygodna, w pełni dynamiczna, forma przechowywania informacji o strukturze.

Ćwiczenia:

1. Przy założeniu niżej podanej definicji węzła wyrażenia kropkowego
   struct WKROP

{enum rodzaj
{ _atom, _wkrop };

int klucz;

WKROP * lwkrop;

WKROP * pwkrop;

};

zapisz podstawowe funkcje obsługi wyrażeń kropkowych, tzw. funkcje czystego LISP'u. W powyższej definicji wartość _atom pola rodzaj oznaczać będzie liść drzewa, natomiast _wkrop - że jest to węzeł kropkowy.

Zapisz funkcje o niżej podanych nagłówkach i znaczeniach:

a) int atom( WKROP * ptr) - funkcja zwraca wartość 1, gdy węzeł, do którego
wskazanie przekazano do funkcji, jest liściem, lub 0, w przeciwnym przypadku,

b) WKROP * lwyr( WKROP * ptr) - funkcja zwraca wskazanie do lewego nas-
tępnika węzła kropkowego,

c) WKROP * pwyr( WKROP * ptr) - funkcja zwraca wskazanie do prawego nas-
tępnika węzła kropkowego,

d) WKROP * const( WKROP * ptr1, *ptr2) - konstruktor nowego wyrażenia
kropkowego, złożonego z dwóch wskazanych wyrażeń.

11. Grafy

Graf jest najbardziej złożoną strukturą dynamiczną. W przeciwieństwie do drzewa i listy, które są szczególnymi przypadkami grafów, nie nakładamy tu żadnych ograniczeń, jeśli chodzi o łuki łączące węzły grafu, mogą one występować w dowolnej ilości, łącząc poszczególne węzły w dowolny sposób.

Dodatkowo w grafach dopuszczamy przetwarzanie (dodawanie i usuwanie) łuków, niezależnie od przetwarzania węzłów. W drzewach i listach przetwarzanie dotyczyło wyłącznie węzłów, łuki pełniły rolę podrzędną, spinając węzły w drzewo, lub listę.

Wszystko to stwarza duże problemy, jeśli chodzi o reprezentacje grafów w pamięci komputera. Istnieje wiele reprezentacji o różniących się własnościach. Wybór należy do użytkownika, który wybiera reprezentację najbardziej odpowiednią do zagadnienia, którym się zajmuje.

Krąg zagadnień, w których w zupełnie naturalny sposób, nasuwa się konieczność sięgnięcia do teorii grafów, jest ogromny. Wymieńmy kilka typowych zagadnień:

• analiza sieci elektrycznych, ale też sieci komputerowych,

• zagadnienia segmentacji programów i wieloprzetwarzania,

• zagadnienia planowania w badaniach operacyjnych,

• identyfikacja struktur molekularnych w chemii organicznej.

Rys. 2.21 Przykładowy graf

Rys. 2.21 przedstawia schemat przykładowego grafu, który zawiera takie charak-terystyczne elementy, jak: krawędź zapętloną (jedna z krawędzi zaczyna się i kończy na węźle z etykietą 2), krawędzie równoległe ( dwie krawędzie łączą w taki sam sposób węzły o etykietach 3 i 4), wreszcie jeden z węzłów ( o etykiecie 6 ) nie ma w ogóle połączeń z resztą grafu.

Wszystkie te sytuacje są dopuszczalne. W dalszych rozważaniach musimy jednak ograniczyć się, ze względu na rozmiary wykładu, do sytuacji najprostszych, dlatego założymy, że w analizowanych grafach krawędzie zapętlone i równoległe nie występują

Wprowadźmy dalsze, potrzebne nam, pojęcia:

1. Graf, w którym wszystkie krawędzie będą krawędziami skierowanymi, nazywać będziemy grafem skierowanym, albo zorientowanym, w przeciwnym przypadku - grafem nieskierowanym.

2. Ścieżką w grafie nazywać będziemy ciąg możliwych do przejścia, wierzchołków, np. (2, 3, 4).

3. Cyklem będzie ścieżka, zaczynająca się i kończąca tym samym wierzchołkiem, np. (2, 3, 4, 2).

4. Graf nie zawierający żadnych cykli nazywać będziemy grafem acyklicznym, w przeciwnym przypadku - grafem cyklicznym. Acykliczność grafu jest ważną jego cechą, braną pod uwagę przy wielu algorytmach. Oczywiście grafy zawierające krawędzie zapętlone są z natury cykliczne.

5. Kolejną, ważną z punktu widzenia wielu algorytmów grafowych, jest spójność grafu. Oto definicje:

Graf nieskierowany nazywać będziemy spójnym, jeśli między dwoma dowolnymi węzłami istnieje przynajmniej, jedna łącząca je ścieżka. W przeciwnym przypadku - graf nieskierowany nazywać będziemy niespójnym.

Graf skierowany nazywać będziemy spójnym, jeśli po odrzuceniu skierowania, między dwoma dowolnymi węzłami istnieje przynajmniej, jedna łącząca je ścieżka.

Graf skierowany nazywać będziemy silnie spójnym, jeśli między dwoma dowolnymi węzłami istnieje przynajmniej, jedna łącząca je ścieżka.

Przykładowy graf skierowany z rys. 2.21, po odrzuceniu węzła z etykietą 6, jest
grafem spójnym, natomiast nie jest grafem silnie spójnym - brak, na przykład,
ścieżki od węzła 5 do 3 (mimo, iż istnieje ścieżka od węzła 3 do 5).

5. Graf, w którym każdej krawędzi przypisano pewną wartość (wagę), nazywać będziemy grafem ważonym. Waga może reprezentować, na przykład, koszt przejścia między dwoma węzłami. Uzasadnia to używanie krawędzi równoległych, z których każda będzie mieć inną wagę.
   Inną sytuacją, uzasadniającą użycie krawędzi równoległych w grafie, który nie jest grafem ważonym, jest przekazanie pewnej informacji (np. ilość możliwych połączeń) za pomocą ilości krawędzi łączących te same wierzchołki.

6. Grafem płaskim nazywać będziemy narysowany na płaszczyźnie graf, w którym między dwoma dowolnymi wierzchołkami narysować można przynajmniej jedną krawędź. Przykładowy graf z rys. 2.21 jest takim grafem płaskim.

11.1. Metody reprezentacji grafów

W poniższym podrozdziale zostaną przedstawione trzy, najczęściej spotykane, najważniejsze reprezentacje grafów.

Macierz sąsiedztwa

Macierz sąsiedztwa (adjacency matrix) jest reprezentacją tablicową, a więc statyczną. Jej zaletą jest szybki, bezpośredni dostęp do krawędzi (a więc możliwość łatwego ich przetwarzania), wielką wadą natomiast, wynikający ze statyczności - brak możliwości przetwarzania (dodawania lub usuwania) węzłów.

1 2 3 4 5 6

	1
	1	1		1
			1
	1			1

1

2

3

4

5

6

Rys. 2.22 Reprezentacja przykładowego grafu, którego model przedstawiono na rys. 2.21,
w postaci bitowej macierzy sąsiedztwa

Oznaczmy przez n ilość węzłów grafu, oraz przez m - ilość jego krawędzi. Bitowa macierz sąsiedztwa będzie macierzą kwadratową o rozmiarach n x n zawierającą jedynki na skrzyżowaniu odpowiednich wierszy i kolumn (dla reprezentowania krawędzi) i zera w pozostałych miejscach.

Oczywiście taka reprezentacja przechowuje informacje tylko o krawędziach grafu i tylko krawędzie pozwala przetwarzać. Informacje zawarte w węzłach (etykiety węzłów i inne dane) przechowuje się w odrębnej tablicy węzłów. Dla reprezentowania grafu, mogącego zawierać węzły równoległe, trzeba przejść od macierzy bitowej do macierzy liczb całkowitych. Natomiast, aby reprezentować graf ważony - do macierzy liczb rzeczywistych.

Ponieważ zajętość pamięci w tej reprezentacji zależy tylko od ilości węzłów (jest proporcjonalna do n² ), reprezentacja dobrze nadaje się do przechowywania informacji o grafach gęstych, dla których (n/m) << 1.

W reprezentacji grafu nieskierowanego w postaci macierzy sąsiedztwa jedynki występują symetrycznie względem głównej przekątnej, dlatego też zwykle przechowuje się tylko informacje zawarte nad, lub pod główną przekątną, co pozwala zmniejszyć zajętość pamięci prawie o połowę, kosztem niewielkiego wydłużenia czasu dostępu. Załóżmy, że przechowujemy tylko część macierzy pod główną przekątną, wtedy aby dotrzeć do elementu t[i,j], trzeba wykonać instrukcję if i<j then t[i,j] else t[j,i].

Lista krawędzi

Lista krawędzi, jak sama nazwa wskazuje, przechowuje informacje tylko o krawędziach, podobnie zresztą jak macierz sąsiedztwa. Jest to jednak struktura dynamiczna, jej rozmiary są wyznaczone przez rzeczywistą ilość krawędzi.

1		2		2		2		3		4		4
2				2		3		5		4		2		5

Rys. 2. 23 Reprezentacja przykładowego grafu, którego model przedstawiono na rys. 2.21,
w postaci listy krawędzi. Każdy z elementów listy zawiera etykiety: węzła
wyjściowego (górny wiersz), oraz docelowego (dolny wiersz), krawędzi.

Oto jak wyglądają zalety i wady tej reprezentacji, pokazane w sposób skondensowany:

• zajętość pamięci zależy tylko od ilości krawędzi i jest proporcjonalna do m, reprezentacja nadaje się więc wybitnie do przechowywania informacji o grafach rzadkich, dla których (n/m) >>1,

• dodawanie, lub usuwanie węzłów jest możliwe, pociąga za sobą jedynie konieczność modyfikacji listy krawędzi (usunięcie elementów listy krawędzi odpowiadających krawędziom wychodzącym i dochodzącym do usuwanego węzła),

• istnieje możliwość reprezentacji krawędzi zapętlonych i równoległych (każdej krawędzi odpowiada bowiem odrębny element listy krawędzi), podobnie dodając do elementów listy krawędzi pole, przechowujące wagę krawędzi, można reprezentować grafy ważone,

• zajętość pamięci dla grafów nieskierowanych wzrasta natomiast dwukrotnie w stosunku do grafów skierowanych, trzeba bowiem w liście krawędzi reprezentować możliwość poruszania się w obu kierunkach miedzy węzłami grafu.

Lista incydencji

Najbardziej uniwersalną, o najlepszych własnościach, wydaje się być reprezentacja, którą nazwiemy listą incydencji. Jest to struktura w pełni dynamiczna, z możliwością przechowywania (i przetwarzania) w jednej strukturze wszystkich informacji, dotyczących zarówno krawędzi, jak i węzłów.

Za taką uniwersalność płacimy jednak względnie dużym stopniem skomplikowania struktury, z czym jednak nie musi wiązać się, jak zobaczymy, skomplikowanie algorytmów.

W strukturze, przechowującej pełną informację o grafie, występują dwa rodzaje rekordów. Zdefiniujmy najpierw postać rekordów, przechowujących informacje dotyczące węzłów grafu:

struct VERT

{ int klucz;

int old;

ELEM * eref;

VERT * nextv;

};

Zawierają one, oprócz etykiety węzła o nazwie klucz, wskazanie eref do początku listy rekordów, opisujących krawędzie wychodzące z danego węzła (rekordy odpowiadające krawędziom są typu ELEM), oraz wskazanie nextv do następnego węzła w liście węzłów. Znaczenie pola old zostanie wyjaśnione później.

Rekordy drugiego rodzaju przechowują informacje dotyczące krawędzi. Są one typu:

struct ELEM

{ VERT * vref;

ELEM * nexte;

};

gdzie: vref jest wskazaniem węzła, do którego wiedzie dana krawędź,

nexte jest wskazaniem kolejnego rekordu w liście krawędzi wychodzących z tego
samego węzła.

Poniższy rysunek przedstawia początkowa część struktury przykładowego grafu z rys. 2.21

old do węzła 3 do węzła 5

old

Rys. 2.24 Reprezentacja części przykładowego grafu w postaci listy incydencji

Oto cechy tej reprezentacji:

• zajętość pamięci zależy w równym stopniu od ilości węzłów grafu, jak i od ilości jego krawędzi, i jest proporcjonalna do sumy ( n + m ), taka reprezentacja nadaje się więc do przechowywania dowolnych grafów, o ile rozmiary grafu nie są zbyt duże, wtedy bowiem zaczyna odgrywać rolę czas dostępu sekwencyjnego,

• dodawanie, lub usuwanie zarówno węzłów, jak i krawędzi, jest możliwe i łatwe,

• istnieje możliwość reprezentacji wszelkich postaci grafów - definicje rekordów opisujących węzły, jak również krawędzi, można bowiem dowolnie zmieniać i rozszerzać,

• zajętość pamięci dla grafów nieskierowanych wzrasta i jest proporcjonalna do ( n + 2 * m ), dwukrotnie bowiem wzrasta ilość rekordów reprezentujących krawędzie, aby umożliwić poruszanie się w obu kierunkach miedzy węzłami grafu,

• najważniejszą jednak zaletą tej reprezentacji jest jej listowy charakter (w istocie jest to lista list), co daje szansę stosowania prostych algorytmów obsługi, i to zarówno rekurencyjnych, jak też iteracyjnych.

11.2. Algorytm szukania w głąb dla grafu

Algorytm szukania w głąb jest podstawowym algorytmem grafowym. Jego konstrukcja oparta jest o schemat ogólny tak zwanych algorytmów z powrotami, zwanych niekiedy wyszukiwaniem wyczerpującym. Schemat ten zostanie bardziej szczegółowo omówiony w rozdziale III.10 skryptu.

Poza tym algorytm szukania w głąb jest kolejnym przykładem rekurencyjnego algorytmu typu „dziel i zwyciężaj”. Jego zasada została omówiona przy okazji algorytmu sortowania tablic QuickSort.

Poniżej przedstawiono pełną postać algorytmu szukania w głąb dla grafu w formie rekurencyjnej funkcji, zapisanej w notacji C/C++ i wykorzystującej podane wcześniej definicje struktur. Przy okazji zauważmy, że cechą charakterystyczną tych algorytmów jest umieszczona wewnątrz ciała funkcji pętla iteracyjna, zawierająca rekurencyjne wywołanie.

Załóżmy, że podobnie jak w drzewie binarnym, chcemy wykonać pewną operację Q(ptr) na wszystkich węzłach zupełnie dowolnego grafu skierowanego. W tym celu należy dokonać wywołania SEARCH ( graf ); niżej zdefiniowanej funkcji

void SEARCH( VERT * ptr)

{

if ( not old ) // 1

{ ptr → old =1; Q( ptr ); // 2

ELEM * k = ptr → eref; // 3

while (k) // 4

{ SEARCH( k → vref ); // 5

k = → nexte; // 6

}

}

}

Szczegółowa analiza działania tego algorytmu wykaże, że odwiedzenie wszystkich węzłów grafu zawsze powiedzie się, jeśli będzie to graf silnie spójny, w przeciwnym przypadku, może się nie powieść.

W jaki sposób działa ten algorytm ? Częściowo wyjaśnia to jego nazwa. Kolejne węzły są wybierane z listy krawędzi danego węzła (linia 5). Jeśli wybrany węzeł nie był jeszcze odwiedzony (linia 1), zaznaczamy jego odwiedzenie wpisując jedynkę w jego pole old i wykonując na nim operację Q (linia 2), a następnie zabieramy się do przeglądania jego listy krawędzi (linie 3 i 4), nie kończąc przeglądania listy krawędzi węzła poprzedniego (sic !).

W ten sposób poruszamy się w głąb grafu. Po zakończeniu przeglądania jednak każdej listy krawędzi, wycofujemy się rekurencyjnie, powracając do przeglądania listy incydencji węzła poprzedniego.

Zauważmy, że kolejność występowania węzłów w liście węzłów nie ma żadnego znaczenia. Dalej - powiązanie węzłów w listę wydaje się zbyteczne (nie korzystaliśmy przecież ze wskaźnika nextv). Ale to tylko pozór. Jest ono konieczne, ponieważ w trakcie przetwarzania grafu może, po kolejnej operacji, okazać się, że do któregoś z węzłów nie dochodzi żadna krawędź, ani żadna z niego nie wychodzić (węzeł o etykiecie 6 w naszym przykładowym grafie), albo też po prostu graf przestanie być grafem silnie spójnym (nawet jeśli przedtem był). Sytuacje takie powodują „omijanie” niektórych węzłów w trakcie rekurencyjnego wywoływania algorytmu.

Trzymanie wszystkich węzłów grafu w liście węzłów pozwala w niżej podany sposób

VERT * k = graf; while ( k ) { SEARCH( k ); k = k → nextv; }

zapobiec omijaniu niektórych węzłów. Poza tym - umożliwia dynamiczne dostawianie i usuwanie węzłów grafu. Nie należy również zapominać, przed każdym cyklem przeglądania grafu, o wyzerowaniu pola old.

Algorytm szukania w głąb dla grafu, mimo swoich skromnych rozmiarów (tylko 6 linii !), posiada wielką siłę i możliwości. Na jego kanwie można zaproponować wiele algorytmów obsługujących graf (patrz Ćwiczenia). Takie efekty uzyskujemy stosując algorytmy rekurencyjne do rekurencyjnych struktur danych.

Część III - Inne jeszcze algorytmy

12. Algorytmy przeszukiwania

Przeszukiwanie struktur danych w celu znalezienia obiektów o określonych własnościach jest jednym z podstawowych zadań systemów informatycznych. Nie jest więc sprawą przypadku, że problem przeszukiwania pojawia się od początku niniejszego wykładu i jest omawiany przy okazji prawie każdej struktury danych.

Przeszukiwaniem zajmowaliśmy się zarówno omawiając struktury o nieskomplikowanej budowie (tablice, pliki), jak również struktury w pełni dynamiczne: listy, drzewa, grafy.

W niniejszym rozdziale dokonamy pewnego podsumowania metod przeszukiwania, jak również wskażemy na inne jeszcze algorytmy przeszukiwania.

12.1. Przeszukiwanie liniowe i połówkowe

Cały szereg zaprezentowanych dotychczas algorytmów miało cechy przeszukiwania liniowego. Jego schemat jest prosty i naturalny:

1. Pobierz pierwszy element rozpatrywanej struktury,

2. Sprawdź, czy analizowany element jest elementem poszukiwanym
   Jeśli TAK - zakończ działanie algorytmu,
   Jeśli NIE - pobierz kolejny element i rozpocznij realizację tego punktu
   od początku.

Powyższy schemat sugeruje rekurencyjną wersję algorytmu. W odniesieniu jednak do struktur o nieskomplikowanej budowie, takich jak: tablice, pliki, czy nawet listy liniowe, stosowanie rekurencji nie jest potrzebne. Wystarczy zwykły proces iteracyjny.

Struktury bardziej złożone (drzewa, grafy) można było łatwo przeglądać przy pomocy algorytmów rekurencyjnych opartych na rekurencyjnych definicjach tych struktur. (Nie bez powodu nazwaliśmy je rekurencyjnymi strukturami danych.)

Przykłady takich algorytmów to metody preorder, inorder i postorder w odniesieniu do drzew binarnych oraz algorytm szukania w głąb dla grafów. Wystarczy niewielkie uzupełnienie aby te algorytmy przeglądania przekształcić w algorytmy wyszukiwania.

Jeśli struktura, którą przeszukujemy zawiera elementy uporządkowane, średni czas wyszukania elementu ulega skróceniu. Nie ma bowiem sensu szukanie elementu w tych obszarach struktury, co do których mamy pewność, że element taki nie może tam wystąpić.

Jeżeli szukamy elementu o określonej wartości w tablicy, pliku czy liście liniowej uporządkowanych rosnąco, to element taki na pewno nie wystąpi w tej części przeglądanej struktury, która zaczyna się od elementu o kluczu większym od wartości poszukiwanej.

Podobnie w drzewie binarnych poszukiwań - szukamy elementu tylko w tych gałęziach, które zawierają klucze, w zależności od potrzeby, mniejsze lub większe od klucza napotkanego węzła.

Przypomnijmy, że dla struktur liniowych uporządkowanych, takich jak: tablice, pliki i listy, średni czas wyszukania elementu skraca się o połowę, natomiast dla drzewa binarnego uporządkowanego (takim jest drzewo binarnych poszukiwań), skrócenie czasu wyszukiwania jest bardzo znaczne.

Poznamy teraz algorytm przeszukiwania połówkowego zwany czasem przeszukiwaniem binarnym, który podobnie jak omówione wyżej algorytmy wykorzystuje uporządkowanie elementów struktury liniowej, a jednocześnie pomysł , na którym opiera się idea drzewa binarnych poszukiwań.

Poniżej przedstawiono schemat algorytmu przeszukiwania połówkowego dla uporządkowanej rosnąco, jednowymiarowej, N-elementowej (N>1) tablicy liczb całkowitych zadeklarowanej jako t[1 . . N] (szukamy elementu o kluczu równym zadanej wartości x).

1. Jeśli wartość x jest mniejsza od klucza pierwszego elementu rozpatrywanej tablicy, lub większa od klucza ostatniego elementu rozpatrywanej tablicy → element o kluczu x nie istnieje, koniec,
   

2. Jeśli tablica t zawiera co najmniej 2 elementy → podziel tablicę t na połowę (niech middle oznacza indeks pierwszego elementu prawej części tablicy)
   

3. Jeśli x = t[middle] → znaleziono, koniec,
   
   Jeśli x < t[middle], to element o kluczu x znajduje się w lewej części tablicy (jeśli istnieje) → przejdź do punktu 1 przyjmując, że analizowaną tablicą jest lewa jej część, to jest t[1 . . middle-1],
   
   Jeśli x > t[middle], to element o kluczu x znajduje się w prawej części tablicy (jeśli istnieje) → przejdź do punktu 1 przyjmując, że analizowaną tablicą jest prawa jej część, to jest t[middle+1 . . N]

Intuicja podpowiada nam, że korzyści, jakie osiągamy stosując algorytm wyszukiwania połówkowego, zamiast wyszukiwania liniowego, powinny być znaczne. Rzeczywistość przerasta jednak wszelkie oczekiwania, jego złożoność obliczeniowa wynosi bowiem O(log₂N), wobec liniowej złożoności obliczeniowej algorytmu wyszukiwania liniowego.

Załóżmy przykładowo, że uporządkowana tablica zawiera aż 10 000 elementów. Średnia ilość porównań kluczy kolejnych elementów tablicy z wartością poszukiwaną x wynosi przy wyszukiwaniu liniowym 10 000 / 2 = 5 000 porównań, podczas gdy przy wyszukiwaniu połówkowym - nie więcej niż log₂10 000, to jest około 13 porównań. Wynik jest oszałamiający.

Natomiast dla tablic o małych rozmiarach nie warto używać aż tak złożonego algorytmu, gdyż zysk czasowy będzie niewielki. Na przykład, dla tablicy zawierającej 10 elementów, algorytm wyszukiwania liniowego będzie musiał wykonać co najwyżej 10 porównań, podczas gdy algorytm wyszukiwania połówkowego potrzebuje nie więcej niż 3-4 porównań.

12.2 Kodowanie mieszające

Opisana poniżej metoda przechowywania i wyszukiwania elementów będzie miała praktyczny sens, jeśli zbiór potencjalnych kluczy identyfikujących te elementy jest zbiorem o bardzo dużej liczności. W takich sytuacjach bowiem omawiane dotychczas metody, łącznie z drzewem binarnych poszukiwań, nie zapewnią nam dostatecznie dużej efektywności algorytmów wyszukiwania.

Dla przykładu, wspomniane drzewo binarnych poszukiwań, stanie się drzewem silnie nie wyważonym i efektywność wyszukiwania w takim drzewie zbliży się do efektywności wyszukiwania liniowego w liście liniowej.

Wyobraźmy sobie, że w pewnym systemie używa się haseł o długości 10 liter wykorzystując alfabet języka polskiego. Wszystkich możliwych haseł (być może potencjalnych kluczy użytkowników tego systemu) będzie 33¹⁰, to jest około 1.5 * 10¹⁵ haseł. Jeżeli liczba użytkowników nie jest zbyt duża, opłacalnym będzie zastosowanie systemu, który najpierw dokona „wstępnej selekcji” tych użytkowników, szyflatkując każdego z nich do odrębnych przegródek.

Zadanie szufladkowania może być wykonane za pomocą metody, zwanej kodowaniem mieszającym, lub transformacją kluczową. W literaturze można też spotkać terminy mieszanie liniowe, lub haszowanie dla określenia opisywanej teraz metody, lub jej odmian.

Ponieważ jest bardzo wiele różnych zastosowań tej metody, jak również wiele jej odmian, najpierw opiszemy problem możliwie ogólnie a następnie omówimy jedną z jej implementacji, opartej o struktury listowe.

Niech U będzie dowolnym, skończonym zbiorem (na przykład zbiorem haseł) o dużej liczności. Przez A_i ⊂ U oznaczmy dowolny i-ty podzbiór (tzw. katalog) zbioru U, natomiast przez m << | U | oznaczmy liczbę tych katalogów. Wszystkie katalogi są zbiorami rozłącznymi. Nie muszą one zawierać elementów uniwersum U. Natomiast dowolny element x ∈U, jeśli się pojawi, będzie zakwalifikowany w sposób jednoznaczny do jednego i tylko jednego katalogu.

Przez h(x) oznaczmy funkcję o szczególnych własnościach (tak zwaną funkcję transformującą lub funkcję haszującą), której zadaniem będzie przydzielanie w sposób jednoznaczny dowolnemu elementowi x ∈U określonego katalogu A_i. Będzie to więc funkcja

h: U → { 1, 2, 3, . . . , m }

z uniwersum U w zbiór liczb naturalnych, będących numerami katalogów.

Funkcja haszująca powinna spełniać dwa podstawowe warunki:

• przyjmować wartości ze zbioru { 1, 2, 3, . . . , m } w sposób możliwie równomierny,

• koszt liczenia tej funkcji musi być stały, to jest niezależny od x ∈U i możliwie najniższy.

Pierwszy z tych warunków sprowadza się do żądania, aby dla każdego x ∈U prawdopodobieństwo otrzymania określonej wartości i ∈{ 1, 2, 3, . . . , m } było mniej więcej stałe, to jest niezależne od samej wartości i.

Cała trudność w efektywnym zastosowaniu kodowania mieszającego polega na znalezieniu odpowiedniej do danego problemu, a jednocześnie spełniającej oba postawione warunki, funkcji haszującej. Wielu ludzi straciło wiele czasu pracując nad tym zagadnieniem. Wyniki nie są jednak zbyt imponujące.

Nie wdając się w te rozważania, autor niniejszego wykładu przytoczy teraz własną metodę konstruowania funkcji haszujacej, której efektywność z dość dużym powodzeniem badali studenci w czasie ćwiczeń laboratoryjnych. (Jest on zresztą dość oczywisty.)

Elementami uniwersum były hasła o określonej długości złożone z liter alfabetu polskiego. Ponieważ założono, że bardzo często hasła zaczynają się od słów, które coś znaczą, w oparciu o słownik ortograficzny języka polskiego opracowano tabelę częstości występowania słów zaczynających się od określonej litery.

Następnie w taki sposób dobrano grupy liter, aby prawdopodobieństwo pojawienia się dowolnego słowa, zaczynającego się od litery z danej grupy, było mniej więcej takie same dla wszystkich grup. Przy założeniu, że grupa liter musi zawierać co najmniej jedna literę, otrzymano dość rozsądną liczbę grup m = 17 i maksymalną liczbą liter w grupie równą 4.

Mając tak skonstruowaną funkcję haszującą (inaczej mówiąc funkcję transformacji kluczy), można było w sposób jednoznaczny i w miarę równomierny każde pojawiające się słowo „szufladkować” do jednej z 17 grup.

Poniższy rysunek przedstawia ideę pełnej implementacji metody kodowania mieszającego, wykorzystującego listy liniowe.

H

”

1

2

m

Rys. 3.1 Kodowanie mieszające wykorzystujące listy liniowe

Tablica H, z indeksowaniem w postaci numerów katalogów, przechowuje wskaźniki do list liniowych przechowujących elementy z uniwersum U.

Wstawienie nowego elementu do tej struktury sprowadza się do obliczenia na podstawie klucza elementu wstawianego, za pomocą funkcji haszującej, wartości indeksu i ∈{ 1, 2, 3, . . . , m }, a następnie jego umieszczenia w liście wskazywanej przez element tablicy H[i].

Podobnie przebiega wyszukanie elementu o kluczu równym zadanej wartości x. Najpierw oblicza się przy pomocy funkcji haszującej wartość i a następnie przegląda listę wskazywaną przez H[i] w celu ostatecznego wyszukania elementu. W celu przyspieszenia wyszukiwania warto jest poszczególne listy utrzymywać w stanie uporządkowania.

12.3 Przeszukiwanie tekstów

Przeszukiwanie tekstów w celu znalezienia w nich pewnych ciągów znakowych (nazwiemy je wzorcami) jest ważną i bardzo często wykonywaną w systemach informatycznych, operacją. W ten sposób przeszukujemy pewne opisy (na przykład stron internetowych) w celu stwierdzenia, czy zawierają interesujące nas słowa kluczowe, szukamy w nazwach plików i katalogów identyfikujących je ciągów znaków, itd.

Musimy mieć świadomość, że szukać możemy nie tylko ciągów liter, ale i dowolnych znaków, na przykład określonej sekwencji bitów w ciągłym obszarze pamięci.

Opracowano wiele algorytmów przeszukiwania tekstów, ze względu jednak na ograniczone ramy tego wykładu, omówimy tylko najprostszy z nich, znany w literaturze jako algorytm brute-force.

t[1..M]

1 2 3 . . . M

R

o

z

m

o

w

y

n

i

e

k

o

n

t

r

o

l

o

w

a

n

e

w[1..N]

1 2 3 . . . N i

k

o

n

t

r

o

l

a

j

Rys. 3.2 Algorytm brute-force badania zgodności wzorca w z tekstem t. Kolorem szarym

zaznaczono zgodne fragment tekstów.

Zadaniem algorytmu (patrz rys. 3.2 ) będzie stwierdzenie, czy wzorzec o długości N znaków zapisany w tablicy znakowej w[1..N] występuje w badanym tekście, zapisanym w tablicy znakowej t[1..M]. Oczywiście M ≥ N.

W tym celu użyjemy dwóch indeksów: i - do poruszania się w tablicy t, oraz j - do poruszania się w tablicy w. Zwiększając indeks i poruszamy się wzdłuż tablicy t do momentu napotkania w niej znaku identycznego z w[1], wtedy zaczyna również wzrastać indeks j.

Jeśli w tym procesie j osiągnie wartość N, oznacza to wystąpienie wzorca w badanym tekście od pozycji i - N + 1. Jeśli natomiast wystąpi niezgodność dla j < N, oznacza to niepowodzenie w identyfikacji wzorca w w tekście t od pozycji i - j + 1, należy więc rozpocząć proces porównywania kolejnych znaków we wzorcu i badanym tekście od początku, to jest od pozycji i - j + 1 w tekście t oraz od pozycji 1 we wzorcu w, cofając uprzednio indeks i w tekście t do pozycji i - j + 1 oraz indeks j we wzorcu w do pozycji 1.

Wadą tego algorytmu jest następujący fakt. W przypadku stwierdzenia niezgodności rozpoczyna on badanie tekstu od pozycji tylko o jeden większej w stosunku do pozycji od której stwierdził on w poprzednim badaniu częściową niezgodność. To badanie polega oczywiście na porównywaniu znaków obu tekstów, które to porównywania były już w poprzednim badaniu częściowo wykonywane.

Dlatego też w latach 70-tych i 80-tych szereg autorów opracowało różne ulepszenia tego algorytmu, które dla tekstów o pewnych szczególnych własnościach mogą przyspieszyć działanie algorytmu brute-force.

13. Algorytmy z powrotami

Algorytm szukania w głąb dla grafu jest typowym przykładem szerszej klasy algorytmów, zwanych algorytmami z powrotami lub wyszukiwaniem wyczerpującym.

Są to algorytmy rekurencyjne, które w swoim ciele zawierają, zamiast warunkowego wywołania rekurencyjnego, pętlę iteracyjną, z której wnętrza następują dopiero wywołania rekurencyjne.

W prostych algorytmach rekurencyjnych warunek stopu jest realizowany poprzez wywołanie rekurencyjne warunkowe. Nie spełnienie warunku zawsze przerywa ciąg wywołań rekurencyjnych.

Natomiast w algorytmach, o których mówimy, pojedyncze wywołanie algorytmu rekurencyjnego może spowodować ciąg kolejnych wywołań rekurencyjnych (wszystkie wywołania z tego samego poziomu) nadzorowanych przez pętlę iteracyjną. Pętla ta musi być tak skonstruowana, aby dla każdego dopuszczalnego zestawu danych zapewnić spełnienie w pewnym momencie warunku stopu, przerywając ten ciąg wywołań.

Algorytmy z powrotami wykorzystywane są nie tylko do rozwiązywania problemów, dających się łatwo przedstawić w postaci grafu, ale w szeregu innych dziedzinach wiążących się ściśle z informatyką, takich jak: teoria automatów, projektowanie i analiza sieciowych systemów operacyjnych, przetwarzanie równoległe, wykorzystanie logiki w programowaniu, problemy kodowania, czy wreszcie - gry komputerowe.

Klasa algorytmów z powrotami opisana została już dawno w literaturze, gdzie została zilustrowana rozwiązaniem szeregu klasycznych, można powiedzieć „akademickich” problemów, takich jak: szukanie wyjścia z labiryntu, problem ośmiu hetmanów, droga skoczka szachowego. Rozwiązanie tych problemów w oparciu o ideę algorytmu z powrotami, a także wielu innych, jak: problem komiwojażera, problem doboru, problem plecakowy, znaleźć można w literaturze zamieszczonej na końcu skryptu.

Klasę algorytmów z powrotami omówimy na przykładzie problemu szukania wyjścia z labiryntu.

21	22	23	24	25
16	17	18	19	20
11	12	13	14	15
6	7	8	9	10
1	2	3	4	5

Rys. 3.3 Labirynt zawierający 25 ponumerowanych pól z widocznymi przegrodami,

uniemożliwiającymi przejście między niektórymi polami

W labiryncie, przedstawionym na rys.1 poruszać się można między polami po liniach prostych. Umieszczone przegrody uniemożliwiają bezpośrednią komunikację między wybranymi polami.

Zadanie polega na szukaniu drogi między dwoma dowolnymi polami labiryntu. Tak postawiony problem trzeba jednak uszczegółowić, sprowadza się on bowiem do odpowiedzi na następujące pytania:

• czy taka droga w ogóle istnieje ?

• jeśli tak, to czy takich różnych dróg jest więcej ?

• jeśli tak, to która z nich jest najkrótsza ?

Odpowiedzi na pierwsze pytanie z wynikiem w postaci ciągu pól, które trzeba przejść, aby dotrzeć od pola początkowego do pola końcowego, gdy droga między wskazanymi polami istnieje, będziemy szukać wykorzystując ideę algorytmów z powrotami.

Mówiąc ogólnie metoda powrotów polega na próbach rozszerzenia pewnego rozwiązania częściowego. W każdym kroku, jeśli rozszerzenie aktualnego rozwiązania częściowego nie jest możliwe, powraca się do „krótszego” rozwiązania częściowego i ponownie próbuje się je rozszerzyć.

Tak więc można szukać drogi miedzy dwoma dowolnymi polami labiryntu kierując się następującymi zasadami:

1. z danego pola mogę zawsze wybrać dopuszczalne, nie badaną jeszcze pole sąsiednie,

2. jeśli będąc w określonym polu stwierdzę, że nie istnieje dopuszczalne, nie badana jeszcze pole sąsiednie, zmuszony jestem cofnąć się na pole, z którego wykonałem poprzedni ruch i próbować z tego pola realizować punkt 1.

Znane są dwie, różne reprezentacje pozwalające zaimplementować przedstawioną wyżej ideę algorytmu z powrotami:

1. implementacja oparta na zbiorach,

2. implementacja w postaci drzewa.

13.1. Implementacja algorytmu z powrotami oparta na zbiorach

Niech A_i będzie zbiorem kandydatów związanych z punktem i (w naszym przypadku z polem labiryntu o numerze i). Zbiór ograniczeń, związanych z punktem i oznaczmy przez O_i.

Wtedy

S_i = A_i - O_i

jest zbiorem dopuszczalnych kandydatów, związanych z punktem i.

Dla przykładowego pola o numerze 13 labiryntu, przestawionego na rys. 3 będzie:

A₁₃ = { 8, 12, 14, 18} O₁₃ = { 8 }, czyli zbiór dopuszczalnych kandydatów

S₁₃ = { 12, 14, 18}

Na ogół zbiory A_i można generować automatycznie. Tak też jest i w naszym przykładowym labiryncie - są to dwu-, trzy- lub czteroelementowe zbiory o wartościach różniących się o 1, lub o 5 od wartości i.

Natomiast zbiory O_i są albo z góry zadane i na ogół nie zmieniają się w trakcie realizacji algorytmu, albo (w przypadku bardziej ogólnym) są generowane dla punktu i (a często i dla najbliższego jego otoczenia), na bieżąco w trakcie realizacji algorytmu. Tak się dzieje, na przykład, w większości zręcznościowych gier komputerowych.

Rozwiązaniem częściowym jest częściowy wektor rozwiązań (a₁, a₂, . . . , a_k), zawierający nie powtarzające się numery punktów i reprezentujący częściową, dopuszczalną drogę z punktu wyjściowego a₁ do punktu a_k. Przykładem rozwiązania częściowego dla rozważanego labiryntu może być wektor ( 1, 2, 7, 12, 14, 16, 17, 18, 13 ).

Próba rozszerzenia rozwiązania częściowego polegać będzie na wyborze ze zbioru S_k kolejnego kandydata, rozszerzając rozwiązanie częściowe do (a₁, a₂, . . . , a_k, a_k+1 ) a następnie sprawdzenie, czy w ten sposób osiągamy rozwiązanie końcowe ( w naszym przykładzie - dochodzimy do pola docelowego labiryntu ). Jeśli nie - kontynuujemy rozszerzanie rozwiązania częściowego wybierając kolejnego kandydata ze zbioru S_k+1. Dla zaznaczenia, że przejście z punktu a_k, do a_k+1 miało już miejsce i w przyszłości nie powinno już być badane, usuwamy ze zbioru S_k kandydata S_k+1.

Takie poruszanie się w głąb labiryntu musimy przerwać, jeśli napotkamy pusty zbiór S_k. Wtedy algorytm usuwa z rozwiązania częściowego kandydata a_k, wybierając kolejnego kandydata ze zbioru S_k-1. Gdyby i ten zbiór okazał się pusty, trzeba usunąć z rozwiązania częściowego punkt a_k-1, próbując rozszerzyć to rozwiązanie punktem ze zbioru S_k-2.

Poniżej przedstawiono w tak zwanym pseudokodzie opartym na języku TP ogólną postać algorytmu z powrotami. Pojęcie pseudokodu, chociaż może niezbyt zręczne, ma ilustrować fakt używania w opisie algorytmu, obok typowych konstrukcji języka programowania, pewnych sformułowań w języku naturalnym.

Takie postępowanie pozwala zapisywać algorytmy, a raczej ich strukturę, w sposób bardzo ogólny. Przystosowanie algorytmu, zapisanego w pseudokodzie do rozwiązywania pewnych konkretnych problemów polegać będzie na uszczegółowieniu sformułowań zapisanych w języku naturalnym i ich zapisie na poziomie języka programowania. Przedtem należy wybrać oczywiście odpowiednią reprezentację danych.

procedure próbuj;

begin zapoczątkuj wybieranie kandydatów;

repeat

wybierz następnego kandydata;

if dopuszczalny then

begin

zapisz go;

if rozwiązanie niepełne then

begin

próbuj; {próba wykonania następnego kroku}

if próba nieudana then usuń zapis

end

end

until próba udana or nie ma następnego kandydata

end;

Rys. 3.4 Ogólna postać algorytmu z powrotami zapisana w pseudokodzie

13.2 Implementacja algorytmu z powrotami w postaci drzewa

Drzewo jest właściwą strukturą do przechowania informacji o możliwych drogach poszukiwania rozwiązania za pomocą algorytmu z powrotami.

Poniższy rysunek przedstawia początkową część drzewa, tak zwanego drzewa poszukiwań, w którym wszystkie możliwe ścieżki zaczynające się od korzenia drzewa są możliwymi drogami w labiryncie zaczynającymi się od pola o numerze 1. Jest to drzewo stopnia czwartego.

Znając wszystkie zbiory S_i stosunkowo łatwo jest napisać rekurencyjny algorytm generujący takie drzewo.

labirynt

Rys.3.5 Początkowa część drzewa poszukiwań dla labiryntu z rys. 3.1, gdy polem wyjścio-

wym jest pole o numerze 1

Ponieważ drzewo takie przedstawia wszystkie możliwe ścieżki, jego rozległość, a więc i zajętość pamięci, jest znaczna. Pełne drzewo poszukiwań dla labiryntu przedstawionego na rys. 3.3 zawiera bardzo dużo węzłów. Natomiast niewątpliwą zaletą takiej reprezentacji jest możliwość przeglądania drzewa przy użyciu prostych metod, na przykład - metody preorder, w której liczba wywołań rekurencyjnych, jak również głębokość rekurencji, będzie zaledwie równa głębokości drzewa. Raz jeszcze sprawdza się przytaczana już wcześniej zasada „coś za coś”.

Jest oczywistym, że kształt drzewa, będzie zależał od uporządkowania wartości w poszczególnych zbiorach S_i, powinniśmy więc przyjąć uporządkowanie generujące drzewo o możliwie małej wysokości, co zniweluje głębokość rekursji dla algorytmu przeglądającego drzewo.

Pojedyncze drzewo poszukiwań pozwala badać jedynie ścieżki rozpoczynające się w punkcie umieszczonym w korzeniu drzewa. Dlatego dla pełnej reprezentacji labiryntu musimy utworzyć las zawierający drzewa rozpoczynające się od wszystkich punktów labiryntu. Aby więc można było stosować algorytm pozwalający badać ścieżki między dwoma dowolnymi polami labiryntu musimy dysponować strukturą zajmującą ogromny obszar pamięci.

Ponieważ zajętość pamięci rośnie tutaj wykładniczo ze wzrostem rozmiarów labiryntu, dla większych labiryntów stosowanie reprezentacji opartej o drzewa może okazać się niemożliwe. Dla porównania - zajętość pamięci przy wykorzystaniu reprezentacji w postaci zbiorów jest dla naszego labiryntu nie większa niż 25 x 4 słowa pamięci, a co najważniejsze rośnie liniowo ze wzrostem liczby pól labiryntu. Pozostaje problem złożoności czasowej.

14. Metody usprawniania algorytmów o dużej złożoności czasowej

Cały szereg dotychczas poznanych algorytmów charakteryzowało się wykładniczą złożonością czasową. Były to algorytmy, w których czas obliczeń wzrastał nieprawdopodobnie szybko ze wzrostem rozmiarów struktury, której dotyczyły. Związane to było najczęściej z użyciem rekurencji. Przypomnijmy w tym miejscu takie algorytmy, jak: rekurencyjny algorytm obliczający n-tą liczbę Fibonacciego, algorytm sortowania szybkiego, algorytm szukania w głąb dla grafu, ogólny algorytm z powrotami.

Duże zapotrzebowanie na czas obliczeń całkowicie uniemożliwia stosowanie takich algorytmów do rozwiązywania problemów, których rozmiary są dość znaczne. Na szczęście wiele konkretnych problemów posiada specyfikę, pozwalającą na usprawnienie algorytmów, które dotychczas podawaliśmy w „czystej” postaci.

Ogólnie metody usprawniania algorytmów o dużej złożoności czasowej dzielimy na dwie duże grupy:

• metody systematyczne,

• metody heurystyczne.

W kolejnych rozdziałach postaramy się przybliżyć na czym metody te polegają, opierając się na wybranych, charakterystycznych przykładach.

14.1. Metody systematyczne

Cechą charakterystyczną metod systematycznych jest pewność. Ich stosowanie nie wpływa na jakość algorytmu, w szczególności: nie zmniejsza szans na znalezienie rozwiązania, w niczym nie ogranicza ilości rozwiązań, czy ich dokładności.

Istnieje bardzo dużo różnego rodzaju metod usprawniania algorytmów w sposób systematyczny. Prawie zawsze zależą on od specyfiki rozwiązywanego problemu. W niniejszym rozdziale omówimy trzy najczęściej spotykane metody.

14.1.1. Metoda obcinania gałęzi

Metoda ta polega, mówiąc ogólnie, na rezygnacji z pewnych dużych obszarów potencjalnych rozwiązań w oparciu o stwierdzenia zaprzeczające istnieniu rozwiązań w tych obszarach.

Jeśli problem byłby przedstawiony w postaci drzewa ( takiego jak drzewo poszukiwań ), to obcinanie gałęzi będzie polegać na zaniechaniu poszukiwań w gałęzi ( poddrzewie ) zaczynającym się od określonego węzła. Można tego dokonać tylko wtedy, jeśli mamy uzasadnioną pewność, że wybór tego węzła i wszystkich jego następników nie prowadzi do rozwiązań.

Do jak dużych usprawnień algorytmu może prowadzić metoda obcinania gałęzi pokażemy posługując się klasycznym przykładem tak zwanego problemu ośmiu hetmanów.

Problem ten sprowadza się do odpowiedzi na pytanie:

Na ile różnych sposobów można ustawić na szachownicy o rozmiarach 8 x 8 osiem

hetmanów, aby się wzajemnie nie szachowały ?

Algorytm rozwiązania tego problemu w „czystej” postaci, to jest opartej tylko na regułach szachowania, wymaga dla n=8 daje astronomicznej liczby badań ≅ 4.4 x 10⁹.

Stosując metodę obcinania gałęzi wykluczymy przede wszystkim takie ustawienia hetmanów, które zawierają dwie figury w tym samym wierszu, w tej samej kolumnie, na tej samej przekątnej. Taka eliminacja ogranicza liczbę ustawień do zbadania do 2056 ustawień.

14.1.2. Metoda sklejania gałęzi

Metoda sklejania (łączenia) gałęzi jest kolejnym przykładem metody systematycznej. Jeśli szukamy pewnych rozwiązań a w drzewie poszukiwań istnieje więcej poddrzew izomorficznych (takich samych jak badane poddrzewo), to wystarczy zbadać tylko jedno, a otrzymany wynik wykorzystać w innych miejscach wystąpienia takiego poddrzewa.

Okazuje się, że zastosowanie metody sklejania gałęzi do algorytmu rozwiązującego problem ośmiu hetmanów, jako kolejnej metody systematycznej po wcześniejszym zastosowaniu metody obcinania gałęzi, pozwala zredukować liczbę badań już tylko do 801 węzłów.

14.1.3. Metoda dekompozycji

Wśród metod systematycznych szczególnie ważną pozycje zajmuje metoda zwana metodą dekompozycji problemu, lub metodą „dziel i zwyciężaj”. Jej zasadnicza idea została zastosowana w omawianym już algorytmie sortowania szybkiego Quick Sort dla tablic.

Ogólnie mówiąc polega ona na rozłożeniu rozwiązywane problemu na k podproblemów ( jeśli jest to oczywiście możliwe ), rozwiązaniu każdego z nich, a następnie połączeniu rozwiązań cząstkowych w jedną całość. Wzrasta wtedy zapotrzebowanie na pamięć, trzeba bowiem gdzieś przechowywać rozwiązania cząstkowe przed ich zcaleniem, ale może prowadzić do znacznego skrócenia czasu obliczeń.

Załóżmy, że rozwiązanie wymaga czasu C * 2ⁿ , gdzie n jest rozmiarem zadania, a C - pewną stałą. Po zastosowaniu dekompozycji czas obliczeń skraca się do k *C * 2^n/k + T, gdzie T jest czasem potrzebnym na połączenie wszystkich rozwiązań cząstkowych. Jeśli k nie jest duże i połączenie nie jest zbyt kosztowne, metoda ta może dać znaczne skrócenie czasu obliczeń.

14.2. Metody heurystyczne

Metody heurystyczne stosujemy, gdy nie ma możliwości posłużenia się metodami systematycznymi. Idea tych metod polega na przyjęciu pewnych założeń, co do których nie mamy pewności, lub nawet wiemy, że nie są słuszne w całym obszarze działania algorytmu, ale które bardzo wspomagają poszukiwanie rozwiązań. Postępujemy tak mając świadomość, że w pewnych, chociaż mniej prawdopodobnych sytuacjach, zastosowana metoda heurystyczna może utrudnić szybkie znalezienie rozwiązania, a czasem nawet uniemożliwić w ogóle jego znalezienie.

Po metody heurystyczne będziemy więc sięgać, gdy nie zależy nam na znalezieniu wszystkich rozwiązań i możemy zadowolić się jednym rozwiązaniem, które jednak musi być znalezione bardzo szybko (typowa sytuacja z gier komputerowych).

W innych jeszcze przypadkach, gdy istnienie rozwiązań jest bardzo wątpliwe, warto skorzystać z metod heurystycznych i być może w krótkim czasie znaleźć jakieś rozwiązanie.

Jest bardzo wiele rozwiązań heurystycznych, tak jak wiele jest różnych typów algorytmów wymagających usprawnienia. Poniżej omówimy krótko dwie, bardziej ogólne metody heurystyczne.

1. W odniesieniu do algorytmu poszukującego drogi w labiryncie od pola a do pola b, jeśli wartość a jest mała, a wartość b duża, stosowanie heurystyki mo-głoby polegać na ustawieniu wartości we wszystkich zbiorach S_i w porządku malejącym.
   W ten sposób zapewnilibyśmy wybory pól o dużych wartościach w pierwszej kolejności i większe prawdopodobieństwo poruszania się po krótszej ścieżce a co za tym idzie - szybsze osiągnięcie celu.
   Przyjmując taką heurystykę musimy mieć świadomość, że przy pewnych szczególnych ograniczeniach, występujących w labiryncie, przyjęcie takiej heurystyki może utrudnić znalezienie rozwiązania.
   

2. Jeśli problem przedstawiono w postaci drzewa poszukiwań, to warto (jeśli to możliwe) tak przebudować drzewo poszukiwań, aby węzły niskiego stopnia (o najmniejszej liczbie synów) znalazły się bliżej szczytu drzewa. Obrazuje to rys. 3.6.

1. 
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   b)

Rys. 3.6 Drzewo poszukiwań a) w pierwotnej postaci, b) po przebudowie

Drzewo b) na rys. 6 ma lepsze własności od drzewa a), mimo iż na poziomie 3 oba drzewa zawierają 8 węzłów. W metodach heurystycznych sprawdza się bowiem pewną ilość warunków ograniczających, w celu odrzucenia rozwiązań mniej prawdopodobnych. W drzewie b) jeśli nastąpi to na pewnej wysokości (na rys. 3.6 w węźle zaznaczonym strzałką), to większa część poddrzewa zostanie odrzucona i cel szybciej osiągnięty. Tutaj bowiem badanie węzła wskazanego strzałką spowoduje odrzucenie aż sześciu z ośmiu rozwiązań, znajdujących się na liściach, podczas gdy w drzewie a) tylko czterech rozwiązań.

1

w

w_n

w₂

w₁

w₁₁

w₁₂

w₁₃

7

8

1

4

1

6

3

9

5

2

8

ptr

7

1

4

5

2

8

13

1

6

5

4

17

14

18

16

15

19

8

7

3

2

12

9

10

11

12

1

19

17

14

8

7

3

2

18

16

15

12

9

6

5

4

11

10

ptr

A

C

B

ptr

1

8

2

3

5

4

6

7

ptr

7

3

9

8

1

6

5

root

root

3

3

4

5

5

4

7

6

6

root

ptr

20

11

14

17

10

15

17

11

13

3

7

10

11

11

11

root

d

a

c

b

2

3

1

5

4

6

graf

ptr

k

1

2

nil

nil

”całość”

”dobrze”

”kot”

nil

nil

nil

nil

nil

1

2

7

12

13

11

18

14

6

---