Publikacja w serwisie

Bookmark and Share

5014  odsłona

Paszkiel Szczepan: Teoria grafów w algorytmice

Wykład z Teorii grafów w algorytmie. Eksploracja grafów.

Grafy to struktura danych, która odgrywa ważną rolę w algorytmie. Grafy są bardzo często używane do przedstawiania różnego rodzaju problemów algorytmicznych. Stosuje się je do znajdywaniu optymalnych dróg, obmyślania strategii gry, rozwiązywaniu łamigłówek oraz rozwiązywania wielu złożonych problemów technicznych. Grafy powstały dzięki niemieckiemu matematykowi Eulerowi. Za ich pomocą rozwiązał on problem miasta, w którym mieszkańcy zastanawiali się jak pokonać wszystkie 7 mostów znajdujących się w mieście, bez przechodzenia dwukrotnie przez ten sam most.

 

Euler wyjaśnił, że jest to nie możliwe stosując w tym, celu model grafu. Powstał tym samym cykl zwany Cyklem Eulera, w którym ten sam wierzchołek grafu może być odwiedzany kilkakrotnie. W grafie można znaleźć cykl Eulera wtedy i tylko wtedy, gdy graf jest spójny i każdy jego wierzchołek ma parzysty stopień ( liczba krawędzi dochodzących do wierzchołka określa ich stopień). Poniżej przedstawiłem przykład grafu:

Uogólniając Grafem nazywamy parę liczb G(X,Y) gdzie

X to liczba węzłów grafu,

Y to liczba krawędzi grafu.

 

Grafy Dzielimy na skierowane i niekierowane. Skierowany graf odpowiada grafowi przedstawionemu powyżej, graf nie skierowany to natomiast taki, w którym krawędzie nie są określone kierunkowo. Podstawowymi prawami rządzącymi w algorytmie grafów są ich cykle, Cykl Eulera, oraz cykl Hamiltona, który jest przeciwieństwem cyklu Eulera. Mówi on nam, że gdy przechodzimy od pierwszego węzła grafu do ostatniego nie możemy, dwukrotnie odwiedzać tego samego węzła.

 

Metody reprezentowania grafów w pamięci komputera:

  1. Tablica dwuwymiarowa.
  2. Słownik węzłów.

 

Tablica dwuwymiarowa.

W tablicy dwuwymiarowej wiersze to węzły początkowe, a kolumny to węzły końcowe. Dla poniższego grafu implementacja tablicowa została zaprezentowana w postaci tabeli.

 

Poniższa tabela przedstawia zasadę tablicowej implementacji grafu, w pamięci komputera:

 

 

A

B

C

D

E

F

A

0

1

0

0

0

0

B

0

0

1

1

0

0

C

0

0

1

0

1

0

D

0

0

0

0

1

1

E

0

0

0

0

0

1

F

0

0

0

0

0

0

 

„1” na pozycji (x,y) oznacza, że pomiędzy węzłami istnieje krawędź skierowana w stronę Y. Pola, w których znajdują się wartości „0” symbolizują, że między tymi węzłami nie istnieją krawędzie. Zaleta jest prostota w implementacji, a wadą to, że grafy o ustalonej z góry liczbie węzłów mogą być łatwo reprezentowane

 

Słownik węzłów

Może dotyczyć dwóch typów węzłów:

1. Następników- węzłów odchodzących.

2. Poprzedników- węzłów dochodzących.

 

Dla poniższego grafu implementacja za pomocą słownika została zaprezentowana w postaci dwóch tabel, których zebrano węzły nadchodzące i dochodzące.

Tabela węzłów następników - odchodzących:

 

A

B

B

C,D

C

C,E

D

E,F

E

F,

F

NULL

 

Tabela węzłów poprzedników - dochodzących:

 

A

NULL

B

A

C

B,C

D

B

E

C,D

F

D,E

 

Zaleta to liczba węzłów, która może ulegać zmianie w trakcie wykonywania programu. Słownik może być łatwo zrealizowany za pomocą listy list.

 

Eksploracja grafów.

Dużo interesujących zadań, w których użyto grafu do modelowania pewnej sytuacji wymaga systematycznego przeszukiwania grafu. Przeszukiwanie grafów stosowane jest w celu odnalezienia optymalnej strategii gry, rozwiązaniu łamigłówki lub konkretnemu problemu technicznego przedstawionego za pomocą grafów.

 

Techniki eksploracji grafów:

  1. Strategia „W głąb” DFS - (DEPTH FIRST)
  2. Strategia „Wszerz” BFS - (BREADTH FIRST)

 

Strategia przeszukiwania „W głąb” – DFS.

Strategia „W głąb” bada daną drogę aż do jej całkowitego wyczerpania, przed wybraniem następnej w celu uzyskania kolejności przeszukiwania grafu. Procedurę zastosowaną przeze mnie do analizy algorytmu nazwałem zwiedzaj przeszukuje ona listę wierzchołków, przylegających do wierzchołka i, i jeśli któryś z tych przyległych wierzchołków nie był jeszcze badany, wywołuje dla niego funkcje zwiedzaj, która zaznacza ten wierzchołek jako zbadany a następnie szuka wierzchołków, przyległych do niego, i sprawdza kolejno, które z nich były już badane. Dla pierwszego z niebadanych wywoływana jest ponownie procedura zwiedzaj, i tym sposobem algorytm „idzie w głąb” grafu, aż do całkowitego wyczerpania raz obranej drogi. Poniżej zamieściłem graf na podstawie, którego analizowałem strategie „w głąb” DEPTH FIRST.

Lista przyległych wierzchołków:

0 - 1,3,4

1 - 0,2,4

2 - 1,6

3 - 0,4,6

4 - 0,1,3,5

5 - 4

6 - 2,3

 

Poniżej przedstawiłem treść wykonywania algorytmu w pseudokodzie:

zwiedzaj(i)

{

zaznacz i jako zbadany;

dla  każdego k przylegającego do i

jeśli k nie był jeszcze zbadany;

zwiedzaj (k);

}

 

Uruchomienie programu poinformuje nas, że kolejność przeszukiwanych wierzchołków jest następująca: 0, 1, 2, 6, 3, 4, 5. Algorytm według powyższego pseudokodu działa następująco:

 

Zwiedzamy

0

1

2

6

3

4

5

Zbadaliśmy

0

1

2

6

3

4

5

Przyległe k=

1,3,4

0,2,4

1,6

2,3

0,4,6

0,1,3,5

4

 

Fragment kodu programu realizującego strategie przeszukiwania „w głąb” w C++:

 

int i, j, g[n][n], v[n];

// g[n][n] – graf [n][n],

// v[n] – przechowuje informacje czy badany wierzchołek był już badany jak tak to 1 jak nie to 0.

void szukaj(int g[n][n], int v[n])

{

int i;

for(i=0;  i<n;  i++)

v[i]=0; // wierzcholek nie byl jeszcze badany.

for(i=0; i<n;  i++)

if(v[i]==0)

zwiedzaj(g,v,i)

}

void zwiedzaj( int g[n][n], v[n] int i)

{

v[i]=1;    // zaznaczamy wierzchołek jako zbadany

for( int k=0;  k<n; k++)

  if ( g[i][k]!=0)    //czy istnieje przejscie

       if (v[k]==0) 

           zwiedzaj(g,v,k);

}

 

Strategia przeszukiwania Wszerz – BFS.

W myśl strategii przeszukiwania WSZERZ, najpierw badamy wszystkie poziomy grafu o jednakowej głębokości.

Lista wierzchołków przyległych:

 

0 – 1,3,4

 

 


0,2,4       0,4,6     1,3,5

 

2 – 1,6

5 – 4

6 – 2,3

 

Problemem, jaki pojawia się w tym algorytmie to konieczność zapamiętywania przeszukiwania danego wierzchołka oraz uwzględniania, że mamy jeszcze ewentualnie inne wierzchołki czekające na przebadanie na tym samym poziomie grafu. Okazuje się ze najlepiej jest do tego wykorzystać zwykłą kolejkę FIFO, która sprawiedliwie obsłuży wszystkie wierzchołki, zgodnie z kolejności ich wchodzenia do kolejki.

 

Poniżej przedstawiłem treść wykonywania algorytmu w pseudokodzie:

 

szukaj(i)

{

 wstaw i do kolejki;

 dopóki kolejka nie jest pusta wykonaj:

   {

     wyjmij  wierzchołek s z kolejki

     zaznacz s że był już zbadany;

     dla każdego wierzchołka k przyległego do wierzchołka s

     jeśli k nie był jeszcze przebadany

        {

        zaznacz k jako zbadany;

        wpisz k do kolejki;

        }

   }

}

 

Dla grafu na podstawie, którego analizowałem powyżej zapisany algorytm, pierwszym wyszukanym wierzchołkiem był wierzchołek 0. Zgodnie z algorytmem zapisałem go do kolejki, następnie za każdym razem sprawdzałem warunek czy kolejka nie jest pusta, jeśli był on spełniony, wówczas wykonywałem dalszą część algorytmu. Struktura kolejki FIFO, która była mi pomocna w celu poprawnego wykonania algorytmu, i nie pominięcia żadnego z węzłów na tym samym poziomie, polegała na kolejnym cyklicznym wyjmowaniu z kolejki jej wierzchołka. Odbywało się to za każdym razem dla innego punktu węzłowego. Następnie wyszukiwane były punkty, które przylegały do danego wierzchołka, jeśli nie były one uprzednio badane, wstawiałem je do kolejki, zachowując tym samym sens działania algorytmu opartego na kolejce FIFO. Cała procedura odbywała się cyklicznie aż do momentu przejścia przez wszystkie węzły grafu. Poniższy schemat przedstawia kolejność wpisywania danych wierzchołków do kolejki, oś pionowa opisuje zawartość kolejki, a oś pionowa etap wykonywania kolejki.

 

 

 

4

 

2

 

6

 

5

 

 

 

 

 

3

4

4

2

2

6

6

5

 

 

-

0

1

3

3

4

4

2

2

6

5

-

 

Poniższa tabela przedstawia, zestawienie wykonywania operacji, dla przykładowego podanego przeze mnie grafu są to operacje: „wyjęcia” z kolejki wierzchołka, zbadania węzła oraz wypisania tych węzłów, które są dla danego wierzchołka przyległe. Przedstawia też kolejność wstawiania do kolejki FIFO poszczególnych węzłów.

 

Zawartość kolejki FIFO

 

 

4

 

2

 

6

 

5

 

 

 

 

 

 

3

4

4

2

2

6

6

5

5

 

 

_

0

1

3

3

4

4

2

2

6

6

5

_

Wyjęte z kolejki

 

0

 

1

 

3

 

4

 

2

 

6

 

Zbadane węzły

 

0

 

1

 

3

 

4

 

2

 

6

 

Przyległe węzły

 

1,3,4

 

0,2,4

 

0,4,6

 

0,1,3,5

 

1,6

 

2,3

 

Zbadane węzły

 

1,3,4

 

2

 

6

 

5

 

 

 

 

 

 

Fragment kodu programu realizującego strategie przeszukiwania „wszerz” w C++:

 

void szukaj( int g[n][n], int v[n], int i)

// rozpoczynamy od wierzchołka i

// g[n][n] - graf n na n

// v[n] przechowuje informacje czy dany wierzchołek był już badany (1) czy tez nie (0)

{

FIFO<int> kolejka(n);

kolejka.wstaw(i);                //wprowadź dane do kolejki

int s;

while(!kolejka.pusta())       // dopóki kolejka pusta

{

   kolejka.obsluz(s);             // usuń z kolejki pewien wierzchołek s

   v[s]=1;                             // zaznacz wierzcholek s jako zbadany

   for( int k=0; k<n;  k++)

      if(g[s][k]!=0)                 //istnieje przejscie

         if(v[k]==0)                 // k nie był jeszcze badany

         {

          v[k]=1;                      // k jako zbadany

          kolejka.wstaw(k);

          }

 }

}

 

Algorytmy obliczania optymalnych dróg w grafie.

Do tego typu algorytmów zaliczyć należy algorytmy Roy-Warshalla, Floyda-Warshalla oraz algorytm Dijkstry. Podczas wykonywania różnego rodzaju operacji na grafach przydatne okazują się algorytmy znajdywania najbardziej optymalnych dróg przechodzenia po grafie.

Jednym z takich algorytmów jest algorytm Floyda - Warshalla.

D[i,j]=min(D[i,j], D[i,k]+D[k,j])

 

Działanie algorytmu można wyjaśnić na przykładzie poniżej zaprezentowanego przeze mnie grafu:

Dla powyżej zaprezentowanego grafu obliczenie, która z dróg od danego punktu węzłowego do drugiego jest najbardziej optymalna np.: od 1 do 4, polega na badaniu poszczególnych krawędzi grafu. Bierzemy wówczas pod uwagę przydzielone im wagi i sumujemy je w celu konkretnego określenia kosztu, jaki poniesieni przechodząc daną drogą. Przykładowo przechodząc po grafie od punktu 0 do 4, mamy do wyboru dwie drogi, z czego jedna jest bardziej optymalna, a druga mniej.

 

Droga 1 od punktu -> 1 do 4:   0 – 1 – 2 – 4   koszt 45

Droga 2 od punktu -> 1 do 4:   0 – 1 – 4     koszt 50

 

Poniższy algorytm zapisany w kodzie c++, wyłącznie oblicza wartość optymalnej drogi, ale jej nie zapamiętuje.

 

void floyd( int g[n][n] )

{

    for (int k=0; k<n; k++)

      for ( int i=0; i<n; i++)  

       for ( int j=0; j<n; j++)

         g[i][j]=min(g[i][j], g[i][k]+g[k][j])

}

 

Aby algorytm mógł nie tylko obliczać drogę, ale także zapamiętywać która z nich była bardziej optymalna należy wprowadzić następującą poprawkę do algorytmu Floyda:

 

if (g[i][k]+g[k][j] < g[i][j])

{

g[i][j] = g[i][k]+g[k][j];

R[i][j]=k;                         //tablica kierowania ruchem

}

 

Optymalna droga będzie zapamiętywana w matrycy kierowania ruchem R. Aby odtworzyć optymalną drogę od wierzchołka i do wierzchołka j, patrzymy na wartość R[I][J]. Jeśli jest ona równa zero, to mamy do czynienia z przypadkiem elementarnym, tzn. z krawędzią którą należy przejść. Jeśli nie, to droga wiedzie od i do R[I][J] i następnie od R[I][J] do j. Z uwagi na to, że powyższe drogi mogą nie być elementarne, łatwo zauważyć rekurencyjny charakter procedury.

 

void droga (int i, int j)

{

int k=R[i][j];

if (k!=0)

{

droga (i,k);

cout << k <<”   ”;

droga(k,j);

}

}

 

Szczepan Paszkiel

Serwis ODA - Strona główna > Wykaz publikacji  |  

Zamknij okno

góra