70

Grafy – podstawowe pojęcia

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. 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.

Przykładowe zastosowania grafów:

• 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. 42. Przykładowy graf

1

2

3

5

4

6

71

Podstawowe pojęcia:

1. Graf, w którym wszystkie krawędzie są krawędziami

skierowanymi, nazywamy 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

.

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.

72

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. 42, 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.

6. 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.

7. 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. 42 jest takim grafem płaskim.

Grafy – metody reprezentacji w pamięci

Poniżej zostaną przedstawione trzy, najczęściej spotykane,

najważniejsze reprezentacje grafów.

Macierz sąsiedztwa

Macierz sąsiedztwa (adjacency matrix) jest reprezentacją

tablicową, 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 łatwego przetwarzania (dodawania lub usuwania)
węzłów.

73

1 2 3 4 5 6

1

2
3
4
5
6

Rys. 43. Reprezentacja przykładowego grafu, którego

model przedstawiono na rys. 42, 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.

Ponieważ zajętość pamięci w tej reprezentacji zależy tylko

od ilości węzłów (jest proporcjonalna do n

2

), 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.

Lista krawędzi

Lista krawędzi, jak sama nazwa wskazuje, przechowuje

informacje tylko o krawędziach, podobnie zresztą jak macierz

1

1

1

1

1

1

1

74

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. 44. Reprezentacja przykładowego grafu,

przedstawionego na rys. 42, w postaci listy
krawędzi. Każdy z elementów listy zawiera etykiety
krawędzi: węzła wyjściowego (górny wiersz), oraz
docelowego (dolny wiersz),.

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.

75

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:

76

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. 42

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

old

Rys. 45 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,

1

2

graf

ptr

k

77

• dodawanie, lub usuwanie zarówno węzłów, jak i

krawędzi, jest możliwe i łatwe,

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

• 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.

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 dalszej części wykładu.

Poza tym, algorytm szukania w głąb jest kolejnym

przykładem rekurencyjnego algorytmu typu „dziel i
zwyciężaj”. Jego zasada została już 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.

78

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
rekurencyjnej 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 = 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 ?
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 !).

79

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.

Dzięki utrzymywaniu wszystkich węzłów grafu w liście

węzłów możemy w niżej podany sposób

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

→

→

→ nextv; }

zapobiec omijaniu niektórych węzłów. Nie należy jednak,
przed każdym cyklem przeglądania grafu, zapominać o
wyzerowaniu pola old.

Algorytm szukania w głąb dla grafu, mimo swoich

skromnych rozmiarów (tylko 6 linii poleceń !), posiada wielką
siłę i możliwości. Na jego kanwie można zaproponować wiele
algorytmów obsługujących grafy. Oto przykłady:

80

• wyszukiwanie węzła o zadanych cechach,

• wyszukiwanie węzła o najmniejszej (największej)

wartości klucza,

• wyszukiwanie najkrótszej ścieżki do węzła o zadanych

cechach,

• wyszukiwanie wszystkich ścieżek do węzła o zadanych

cechach,

• badanie cykliczności grafu,

• badania spójności i silnej spójności grafu,

• badanie płaskości grafu,

• itd.

Poza tym, lista incydencji umożliwia łatwe, dynamiczne
dostawianie i usuwanie węzłów grafu.

Wszystko to uzyskujemy dzięki stosowaniu algorytmów
rekurencyjnych do rekurencyjnych struktur danych.

Zadania do samodzielnego rozwiązania:

1. Wykaż, że metoda preorder dla drzewa binarnego jest

szczególnym przypadkiem algorytmu szukania w głąb
dla grafu, gdy ten ostatni degeneruje się do takiego
drzewa.

2. Jaka będzie kolejność wykonywania wybranej operacji

w poniższym grafie, po wywołaniu procedury szukania
w głąb, począwszy od węzła o etykiecie 7 ? Rozważ
wszelkie możliwe rozwiązania.

3. Dodaj minimalną ilość krawędzi do poniższego grafu
tak, aby graf ten stał się grafem silnie spójnym.

81

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

10

, to jest około

1.5 * 10

15

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,
szufladkując każdego z nich do odrębnych przegródek.

graf

7

1

9

3

82

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 pewnym uniwersum, tj. 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, musi być

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.

83

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.

Poniższy rysunek przedstawia ideę implementacji metody

kodowania mieszającego z wykorzystaniem list liniowych.

H

”

1
2






m

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

Tablica H, indeksowana numerami katalogów, przechowuje

wskaźniki do list liniowych z elementami uniwersum U.

Null

Null

Null

Null

Null

”dobrze”

Null

”całość”

Null

”kot”

84

Wstawienie nowego elementu do tej struktury sprowadza się

do obliczenia, za pomocą funkcji haszującej, wartości indeksu
i ∈

∈

∈

∈{ 1, 2, 3, . . . , m }, a następnie umieszczenia tego elementu

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.

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 warunkowych wywołań rekurencyjnych, pętlę
iteracyjną, z której wnętrza następują dopiero wywołania
rekurencyjne.

Pojedyncze

wywołanie

algorytmu

rekurencyjnego może więc 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,

85

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

opisana w literaturze, gdzie została zilustrowana szeregiem
klasycznych problemów, takich jak: szukanie wyjścia z
labiryntu, problem ośmiu hetmanów, droga skoczka
szachowego, problem komiwojażera, problem doboru,
problem plecakowy.

Klasę algorytmów z powrotami omówimy na przykładzie

problemu szukania wyjścia z labiryntu.

Rys. 47 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. 47 można przechodzić

między sąsiednimi polami po liniach prostych. Zadanie polega
na szukaniu drogi między dwoma dowolnymi polami
labiryntu.

Tak

postawiony

problem

trzeba

jednak

uszczegółowić, można bowiem szukać 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 ?

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

86

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.

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.

87

Dla

przykładowego

pola

o

numerze

13

labiryntu,

przestawionego na rys. 47 będzie:

A

13

= { 8, 12, 14, 18} O

13

= { 8 } S

13

= { 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

1

, a

2

, . . . , a

k

), zawierający nie powtarzające się numery

punktów i reprezentujący częściową, dopuszczalną drogę z
punktu wyjściowego a

1

do punktu a

k

. Przykładem rozwiązania

częściowego dla rozważanego labiryntu może być wektor
( 1, 2, 7, 12, 13, 14, 19, 20 ).

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

1

, a

2

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

.

88

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 pseudokodzie ogólną postać

algorytmu

z

powrotami.

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.

void próbuj( )
{ zapoczątkuj wybieranie kandydatów;

do
{ wybierz następnego kandydata;
if (dopuszczalny)
{ zapisz go;
if (rozwiązanie niepełne)
{ próbuj( );
// próba wykonania następnego kroku
if (nie ma następnego kandydata)
usuń poprzedni zapis;
}
}
} while ( rozwiązanie niepełne
and jest następny kandydat);

}

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

pseudokodzie

89

Ćwiczenia do samodzielnego wykonania:

1. W jaki sposób i dlaczego przy pomocy algorytmu z

powrotami można stwierdzić, że między dwoma polami
labiryntu nie istnieje żadna droga ?

2. W jaki sposób należy zmodyfikować algorytm z

powrotami, aby:
a) znajdował on wszystkie drogi miedzy dwoma
dowolnymi polami labiryntu,
b) znajdował on najkrótszą drogę spośród
wszystkich możliwych dróg labiryntu.

3. Zastąp w ogólnym algorytmie z powrotami wszystkie

sformułowania w języku naturalnym przez odpowiednie
polecenia w języku programowania tak, aby algorytm
ten znajdował drogę między dwoma dowolnymi polami
a i b labiryntu.