1-sprawozdanie.pdf

(108 KB) Pobierz

665005076 UNPDF

Michał Kaczara 181132

Marek Karpiński 181172

Struktury danych i złożoność obliczeniowa

Projekt nr 1:

Badanie efektywności algorytmów grafowych w zależności od

rozmiaru instancji oraz sposobu reprezentacji grafu w pamięci

komputera.

Prowadzący: dr inż. Mateusz Gorczyca

Grupa: poniedziałek, godz. 18:55-20:35

POLITECHNIKA WROCŁAWSKA – MARZEC 2011

1. Wstęp

Celem realizowanego przez nas projektu było zbadanie szybkości podstawowych

algorytmów grafowych w zależności od reprezentacji - lista następników i macierz

sąsiedztwa - oraz rozmiaru instancji - ilości wierzchołków i krawędzi w grafie.

Zaimplementowane zostały dwa rodzaje algorytmów:

• algorytmy wyznaczania minimalnego drzewa rozpinającego(MST) grafu ważonego,

nieskierowanego (algorytm Prima, algorytm Kruskala),

• algorytmy wyznaczania najkrótszej ścieżki w grafie ważonym, skierowanym

(algorytm Dijkstry, algorytm Forda-Bellmana).

Badany był również wpływ złożoności danego algorytmu na czas jego wykonania.

2. Opis warunków testowych i reprezentacji grafów

Programy zawierające implementacje algorytmów wymienionych powyżej zostały

napisane w języku C++ i skompilowane przy pomocy Microsoft Visual Studio 2008.

Wykorzystaliśmy tylko biblioteki standardowe języka C++ oraz biblioteki systemu

Windows. Pomiar czasu wykonania każdego z algorytmów zmierzony został funkcją

QueryPerformanceCounter z biblioteki systemowej, przez pobranie aktualnego czasu

w chwili przed jego wykonaniem i po jego wykonaniu, a następnie obliczeniu ich różnicy

(wynik został podany w milisekundach).

Przeprowadziliśmy pomiary czasu pracy algorytmów dla 25, 50, 100, 200 i 400

wierzchołków. Przy wyższej liczbie wierzchołków, podczas pracy algorytmów na

reprezentacjach listowych grafów, czas pracy był tak długi, że program zawieszał się.

Dodatkowo, dla każdego rozmiaru grafu dokonywaliśmy pomiarów dla trzech

gęstości: małej, średniej oraz dużej. Mała gęstość odpowiadała liczbie krawędzi zbliżonej

do czterokrotności liczby wierzchołków, a duża gęstość prawie że maksymalnej liczbie

krawędzi dla danego grafu. Dzięki temu mogliśmy stwierdzić, jak ilość krawędzi wpływa na

efekty pracy algorytmu na danej reprezentacji grafu.

Każdy pomiar przy danych wielkościach wykonywaliśmy po 10 razy, a wyniki

uśrednialiśmy, aby wyeliminować ryzyko błędów losowych.

Pomiary zostały wykonane na komputerze z systemem Microsoft Windows 7

Professional x86, wyposażonym w procesor Intel Pentium dual-core T3200 i 3 GB pamięci

RAM.

W kolejnych podrozdziałach opisane są nasze komentarze odnośnie implementacji

badanych algorytmów, a także opisy i wyniki testów, zaimplementowanych algorytmów.

2.1 Reprezentacja macierzowa grafu

Do reprezentacji macierzowej grafów, postanowiliśmy wykorzystać macierz

sąsiedztwa zamiast macierzy incydencji. Rozwiązanie było prostsze do implementacji

i wykorzystania w algorytmach oraz oszczędniejsze pamięciowo.

W algorytmach Prima i Dijkstry mogliśmy dzięki temu łatwiej odnajdywać krawędzie

wychodzące z danego wierzchołka, bez konieczności przeglądania wszystkich krawędzi

grafu. W ten sposób zmniejszyła się złożoność obliczeniowa.

Natomiast przy algorytmach Kruskala i Forda-Bellmana złożoność obliczeniowa

wzrosła, gdyż zamiast przechodzić po kolejnych krawędziach musieliśmy sprawdzać

każdą parę wierzchołków w macierzy sąsiedztwa, jednak dla grafów gęstych (E rzędu V 2 )

nie robiło to dużej różnicy.

Macierz zapisywaliśmy w programie w postaci dwuwymiarowej tablicy wartości int.

2

665005076.080.png

2.2 Reprezentacja listowa grafu

W reprezentacji listowej elementami listy były wierzchołki grafu(opisywane przez

indeks wierzchołka oraz liczbę krawędzi z niego odchodzących), a następnikami

wierzchołki incydentne z danym wierzchołkiem. Rozwiązanie to sprawiało, że aby dojść do

zadanego wierzchołka w grafie, musieliśmy przejść cały graf, badając każde istniejące

połączenie(krawędź), przez co znacząco wzrastał czas obliczeń, szczególnie dla grafów

gęstych. Ponadto, dla każdego następnika(krawędzi) należało pamiętać jego wagę.

Oprócz tego, dla różnych algorytmów musieliśmy stosować dodatkowe zmienne(np.

zmienną określającą czy wierzchołek został już dodany do drzewa rozpinającego

w algorytmie Dijkstry).

3. Algorytm Prima

3.1 Opis algorytmu

Algorytm Prima, wyznaczający minimalne drzewo rozpinające(MST), oparty jest

o metodę zachłanną, polegającą na znalezieniu rozwiązania w wyniku podjęcia szeregu

decyzji, z których każda wydaje się być w danym momencie najlepsza. Wśród danych

wejściowych algorytmu znajduje się spójny i ważony graf nieskierowany.

Algorytm Prima przebiega następująco:

1. Wybieramy dowolny wierzchołek, a następnie dodajemy go do drzewa.

2. Krawędzie incydentne umieszczamy na posortowanej według wag liście.

3. Zdejmujemy z listy krawędź o najmniejszej wadze.

4. Sprawdzamy, czy drugi wierzchołek tej krawędzi należy do tworzonego drzewa:

a) W przypadku, gdy warunek jest spełniony, porzucamy tę krawędź i pobieramy

następną z listy.

b) Jeśli wierzchołka nie ma w drzewie, należy go dodać, by znalazł się on

w drzewie rozpinającym.

5. Do posortowanej listy dodajemy wszystkie krawędzie incydentne z dodanym

wierzchołkiem.

6. Pobieramy z listy następną krawędź.

3.2 Wyniki pomiarów – reprezentacja macierzowa

Tabela 1. Wyniki pomiarów czasu dla algorytmu Prima – reprezentacja macierzowa

V 25 50 100 200 400

E 80 120 300 160 340 1100 400 1200 4900 800 3200 18000 1600 9000 40000

1

1

1

1

1

1

2

2

2

11 11 11 92 94 90

1

1

1

1

1

1

2

2

2

10 11 11 89 92 93

1

1

1

1

1

1

2

2

2

11 11 11 93 95 101

1

1

1

1

1

1

2

2

2

10 11 11 95 94 97

czas

[ms]

1

1

1

1

1

1

2

2

2

10 11 11 94 93 93

1

1

1

1

1

1

2

2

2

10 11 10 95 90 90

1

1

1

1

1

1

2

2

2

10 11 10 93 88 95

1

1

1

1

1

1

2

2

2

10 10 10 92 90 94

1

1

1

1

1

1

2

2

2

10 11 10 92 94 97

1

1

1

1

1

1

2

2

2

10 11 10 92 92 90

średni

czas

[ms]

1

1

1

1

1

1

2

2

2 10,2 10,9 10,5 92,7 92,2 94

3

665005076.091.png

665005076.102.png

665005076.113.png

665005076.001.png

665005076.012.png

665005076.023.png

665005076.033.png

665005076.034.png

665005076.035.png

665005076.036.png

665005076.037.png

665005076.038.png

665005076.039.png

665005076.040.png

665005076.041.png

665005076.042.png

665005076.043.png

665005076.044.png

665005076.045.png

665005076.046.png

665005076.047.png

665005076.048.png

665005076.049.png

665005076.050.png

665005076.051.png

665005076.052.png

665005076.053.png

665005076.054.png

665005076.055.png

665005076.056.png

665005076.057.png

665005076.058.png

Wykres 1. Czas działania algorytmu Prima w zależności od liczby wierzchołków i gęstości grafu –

reprezentacja macierzowa

100

92,7

92,2

94

90

80

70

60

50

40

30

20

10,2

10,9

10,5

10

1

1

1

1

1

1

2

2

2

0

25

50

100

200

400

Liczba wierzchołków [V]

Mała gęstość grafu Średnia gęstość grafu Duża gęstość grafu

3.3 Wyniki pomiarów – reprezentacja listowa

Tabela 2. Wyniki pomiarów czasu dla algorytmu Prima – reprezentacja listowa

V 25 50 100 200 400

E 80 120 300 160 340 1100 400 1200 4900 800 3200 18000 1600 9000 9000

1

1

2

2

3

11 13 23 173 20 142 1974 88 898 0

1

2

4

3

9

41 14 69 698 54 446 8653 237 3102 0

1

2

4

3

9

42 14 74 683 58 447 8657 234 3094 0

1

2

4

3

9

41 14 67 691 58 441 8605 245 3077 0

czas

[ms]

1

2

5

3

8

44 14 75 684 58 435 8615 235 3095 0

1

2

5

3

8

44 14 76 694 56 435 8657 240 3069 0

1

2

4

3

8

44 14 67 696 55 433 8600 234 3070 0

1

2

5

3

8

43 14 66 681 55 439 8580 238 3074 0

1

2

4

3

8

42 14 64 691 55 456 8604 235 3078 0

1

2

4

3

8

41 14 64 685 56 451 9188 235 3082 0

średni

czas

[ms]

1 1,9 4,1 2,9 7,8 39,3 13,9 64,5 637,6 52,5 412,5 8013,3 222,1 2863,9 0

Wykres 2. Czas działania algorytmu Prima w zależności od liczby wierzchołków i gęstości grafu –

reprezentacja listowa

9000

8013,3

8000

7000

6000

5000

4000

3000

2863,9

2000

1000

637,6

412,5

222,1

1

1,9

4,1

2,9

7,8

39,3

13,9

64,5

52,5

0

0

25

50

100

200

400

Liczba wierzchołków [V]

Mała gęstość grafu Średnia gęstość grafu Duża gęstość grafu

4

665005076.059.png

665005076.060.png

665005076.061.png

665005076.062.png

665005076.063.png

665005076.064.png

665005076.065.png

665005076.066.png

665005076.067.png

665005076.068.png

665005076.069.png

665005076.070.png

665005076.071.png

665005076.072.png

665005076.073.png

665005076.074.png

665005076.075.png

665005076.076.png

665005076.077.png

665005076.078.png

665005076.079.png

665005076.081.png

665005076.082.png

665005076.083.png

665005076.084.png

665005076.085.png

665005076.086.png

665005076.087.png

665005076.088.png

665005076.089.png

665005076.090.png

665005076.092.png

665005076.093.png

665005076.094.png

665005076.095.png

665005076.096.png

665005076.097.png

665005076.098.png

665005076.099.png

665005076.100.png

665005076.101.png

665005076.103.png

665005076.104.png

665005076.105.png

665005076.106.png

665005076.107.png

665005076.108.png

665005076.109.png

665005076.110.png

665005076.111.png

665005076.112.png

665005076.114.png

665005076.115.png

665005076.116.png

665005076.117.png

665005076.118.png

665005076.119.png

665005076.120.png

3.4 Wnioski

Analizując wyniki pomiarów można zauważyć, iż algorytm Prima pracuje

w zbliżonym czasie niezależnie od gęstości grafu. Na czas wyznaczenia minimalnego

drzewa rozpinającego duży wpływ ma jednak liczba wierzchołków grafu. Najmniejsze

rozbieżności pomiędzy czasami działania algorytmu dla reprezentacji macierzowej

i listowej występują dla grafów o małej gęstości. Dla grafów o gęstości średniej lub dużej

czas działania dla reprezentacji listowej znacznie rośnie i przewyższa nawet

kilkudziesięciokrotnie wyniki dla reprezentacji macierzowej. Dla grafu o dużej gęstości

i 400 wierzchołkach program zwraca błąd, co uniemożliwia zbadanie wyniku.

4. Algorytm Kruskala

4.1 Opis algorytmu

Algorytm Kruskala jest kolejnym przykładem algorytmu zachłannego.

Wyznacza minimalne drzewo rozpinające(MST) dla nieskierowanego grafu spójnego,

ważonego. Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku.

Algorytm Kruskala przebiega następująco:

1. Tworzymy las z wierzchołków oryginalnego grafu – każdy wierzchołek jest na

początku osobnym drzewem.

2. Tworzymy zbiór zawierający wszystkie krawędzie oryginalnego grafu.

3. Sortujemy wszystkie krawędzie względem wag w porządku niemalejącym

i rozpoczynamy proces tworzenia drzewa.

4. Łączymy wiele poddrzew w jedno za pomocą krawędzi o najmniejszej wadze.

a) Wybieramy krawędzie o najmniejszej wadze

b) Usuwamy wybraną krawędź ze zbioru krawędzi

c) Sprawdzamy, czy dana krawędź należy do dwóch różnych drzew:

jeśli tak – scalamy te drzewa,

jeśli nie – odrzucamy tę krawędź.

5. Algorytm kontynuujemy do momentu, aż wszystkie wierzchołki znajdą się w drzewie

docelowym.

4.2 Wyniki pomiarów – reprezentacja macierzowa

Tabela 3. Wyniki pomiarów czasu dla algorytmu Kruskala – reprezentacja macierzowa

V 25 50 100 200 400

E 80 120 300 160 340 1100 400 1200 4900 800 3200 18000 1600 9000 40000

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

6

czas

[ms]

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

6

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

1

1

1

1

1

1

1

1

1

1

1

2

1

2

5

średni

czas

[ms]

1

1

1

1

1

1

1

1

1

1

1

2

1

2 5,2

5

665005076.121.png

665005076.122.png

665005076.123.png

665005076.002.png

665005076.003.png

665005076.004.png

665005076.005.png

665005076.006.png

665005076.007.png

665005076.008.png

665005076.009.png

665005076.010.png

665005076.011.png

665005076.013.png

665005076.014.png

665005076.015.png

665005076.016.png

665005076.017.png

665005076.018.png

665005076.019.png

665005076.020.png

665005076.021.png

665005076.022.png

665005076.024.png

665005076.025.png

665005076.026.png

665005076.027.png

665005076.028.png

665005076.029.png

665005076.030.png

665005076.031.png

665005076.032.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin