Sieci teleinformatyczne Algorytm Prima-Dijkstry ćw2 PDF

Preview

Summary

Jedno z pięciu sprawozdań na przedmiot Sieci teleinformatyczne....

Description

Uniwersytet Technologiczno - Przyrodniczy im. Jana i Jędrzeja Śniadeckich w Bydgoszczy

Wydział Telekomunikacji, Informatyki i Elektrotechniki

Bydgoszcz 2021

Jan Stypczyński (numer albumu 114904) Szymon Kaźmierczak (numer albumu 115855)

Ćwiczenie nr 2 Algorytm Prima-Dijkstry

1. Wstęp 1.1. Cele projekt Celem ćwiczenia było zapoznanie się z działaniem algorytmu Prima-Dijkstry

1.2. Wstęp Teoretyczny 1.1.1. Graf prosty - graf bez pętli własnych i krawędzi wielokrotnych. Często określenie graf (bez przymiotników) oznacza graf prosty.

1.1.2. Algorytm Prima-Dijkstry – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające. Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E′ zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E′ jest najmniejsza możliwa.

1.1.3.Graf ważony - graf, w którym każdej krawędzi przyporządkowana jest liczba rzeczywista zwana wagą tej krawędzi.

1.1.4. Drzewo grafu - graf acykliczny, spójny i nieskierowany 1.1.5. Minimalne drzewo rozpinające - drzewo rozpinające, którego suma wag krawędzi jest najmniejsza ze wszystkich pozostałych drzew rozpinających danego grafu. 1.1.6. Złożoność obliczeniowa - miara służąca do porównywania efektywności algorytmów. Mamy dwa kryteria efektywności: • czas, • pamięć. Przykłady

2

(1,5):1 (1,6):2 (2,5):2 (2,3):2 (4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

3

(1,5):1 (1,6):2 (2,5):2 (2,3):2 (4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

4

(1,5):1

(1,6):2 (2,5):2 (2,3):2 (4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

5

(1,5):1

(1,6):2

(2,5):2 (2,3):2 (4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

6

(1,5):1

(1,6):2

(2,5):2

(2,3):2 (4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

7

(1,5):1

(1,6):2

(2,5):2

(2,3):2

(4,5): 3 (1,2):4 (4,6):6 (5,6):7 (3,4):8

8

Skrypt Matlab function [] = Untitled5 clear all; A = [1 5 1; 1 6 2; 5 2 2; 2 3 2; 4 5 3]; %utworzenie listy krawedzi r1 = A(:, 1); r2 = A(:, 2); r3 = A(:, 3); G = graph([r1], [r2], [r3]); %stworzenie grafu P = adjacency(G); %stworzenie macierzy sąsiedztwa A = full(P); n = size(A); %rozmiar macierzy wdrzewie = 1; %deklaracja zmiennych, wdrzewie - wybrane, niewdrzewie odrzucone, k - liczba wybranych niewdrzewie=1; k = 0; niewdrz = [2:n]'; nnotintree=n-1; while niewdrzewie < n mincost = Inf; for i=1:niewdrzewie for j=1:nnotintree ni = wdrzewie(i); nj= niewdrz(j); if A(ni,nj) < mincost && A(ni,nj)~=0, mincost = A(ni,nj); ei = ni; ej = nj; %zapisanie wybranych krawedzi i punktow end

9

end end k = k + 1; mst(k,:) = [ei,ej]; % dodanie krawedzi do drzewa costs(k,1) = mincost; niewdrzewie = niewdrzewie+ 1; nnotintree = nnotintree-1; wdrzewie = [wdrzewie; ej]; niewdrz = setdiff(niewdrz,ej); end; cost = sum(costs) disp('Krawedzie:'); disp(mst); z = graph(A); %utworzenie grafu poczatkowego scatter = plot(z); disp(scatter); %wyswietlenie stworzonego grafu labeledge(scatter, [r1], [r2], r3); %pokazanie wagi oraz numerów wierzchołlkow Z = graph([mst(:,1)], [mst(:,2)]); %stworzenie listy krawedzi z otrzymanego drzewa highlight(scatter,Z,'EdgeColor','r','LineWidth',1.5); %nalozenie go na narysowany graf end

WYNIKI PROGRAMU

10

Złożoność obliczeniowa algorytmu function [] = funkcja_zlozonosci clc; clear all; t = 0; %czas wykonania algorytmu czas = []; %macierz przechowujaca czasy u = []; %macierz przechowujaca liste wezlow

11

licznik = 1; for n=5:5:100 %generowanie grafu for i=1:30 l = 1; for a=1:1:n-1 for b=a+1:1:n A(l,1)=a; A(l,2)=b; A(l,3)=ceil((rand()*30)+20); l=l+1; end end [s,s] = size(A); tic wdrzewie = 1; %deklaracja zmiennych, wdrzewie - wybrane, niewdrzewie -odrzucone, k - liczba wybranych niewdrzewie=1; k = 0; niewdrz = [2:s]'; nnotintree=s-1; while niewdrzewie < s mincost = Inf; for i=1:niewdrzewie for j=1:nnotintree si = wdrzewie(i); sj= niewdrz(j); if A(si,sj) < mincost && A(si,sj)~=0 mincost = A(si,sj); ei = si; ej = sj; %zapisanie wybranych krawedzi i punktow end end

12

end k = k + 1; mst(k,:) = [ei,ej]; % dodanie krawedzi do drzewa costs(k,1) = mincost; niewdrzewie = niewdrzewie+ 1; nnotintree = nnotintree-1; wdrzewie = [wdrzewie; ej]; niewdrz = setdiff(niewdrz,ej); end end t = t + toc czas(licznik)=t/30; u(licznik)=n; licznik = licznik+1 end plot(u, czas, 'blue'); hold on; a=25/czas(1); licznik = 1; for i=5:5:100 funkcja(licznik)=(i^3)/a; %obliczanie funkcji złożoności obliczeniowej licznik = licznik + 1; end plot(u,funkcja,'red'); xlabel('liczba wezlow'); %dodanie opisu osi ylabel('czas'); legend('czas obliczen','zlozonosc obliczeniowa'); end

13

Wnioski •

• • •

Złożoność algorytmu jest zależna od implementacji kolejki. Niemniej wewnątrz algorytmu przechodzimy po wszystkich n elementach kolejki i za każdym razem aktualizujemy n sąsiadów. Oznacza to, że sam algorytm ma złożoność O(n2). Jednak należy pamiętać, że dodatkowo w każdej pętli należy uaktualnić kolejkę priorytetową, albo przeszukiwać listę w celu znalezienia minimalnego elementu. Złożoność obliczeniowa algorytmu jest funkcją rosnącą nieliniowo Złożoność czasowa algorytmu Prima jest akceptowalna względem ogólnej wydajności w znajdywaniu minimalnego drzewa opinającego. Koncepcja minimalnej rozpiętości drzewa jest stosowana głównie w analizie sieci, sieci transportowej.

14...