Sprawozdanie

Laboratorium 6

Adam Dubiel gr. 3T1

Warunki początkowe:

Zadanie polega na zbadaniu oczekiwanej złożoności obliczeniowej algorytmu bfs_tss w funkcji liczby krawędzi, przyjmując za operacje dominujące:

1. porównanie atrybutu color

2. podstawienie atrybutu color

3. suma obu powyższych

Liczba wierzchołków jest stała i wynosi N=10. Jako wartość MMAX przyjąłem 50. Wartość oczekiwana liczona jest na podstawie LPROB=50 próbek. Takie wartości zmiennych pozwalają na uzyskanie zadowalających wykresów, jednocześnie zachowując krótki czas wykonania się skryptu.

Wartości liczników liczby porównań i podstawień są zwracane przez algorytm bfs_tss.

Jako wierzchołek startowy dla algorytmu przyjąłem wierzchołek nr 1.

Wykres:

Wnioski:

1. zgodnie z teorią, algorytm BFS dla operacji dominującej podstawienia atrybutu color ma oczekiwaną złożoność obliczeniową liniową ( złożoność O( |V| + |E| );

2. funkcja porównania wartości color jest funkcją kwadratową i dopiero dla wielu krawędzi przekracza wartość funkcji podstawień; wynika to z faktu, że dla grafu o dużej gęstości chcąc przetworzyć wierzchołek algorytm musi sprawdzać bardzo dużą ilość jego sąsiadów (istnieje wiele połączeń), z kolei dla małej gęstości grafu średnia ilość porównań jest zdecydowanie mniejsza

3. funkcja ilości podstawień jest funkcją liniową, jako że ilość zmian kolorów ograniczona jest jedynie liczbą wierzchołków, do których algorytm może dotrzeć poruszając się po krawędziach, a liczba ta rośnie wraz ze wzrostem liczby krawędzi

4. wykres sumy ilości podstawień i porównań zmienia swoją charakterystykę w zależności od czynnika dominującego - dla małej ilości krawędzi mała jest ilość porównań, więc dominuje ilość podstawień, dla dużych ilości krawędzi sytuacja się odwraca

MMAX=50;

LPROB = 50;

N=10;

ileKolor = zeros(1, MMAX);

ilePorw = zeros(1, MMAX);

ileKiP = zeros(1, MMAX);

ileKolor_tmp = 0;

ilePorw_tmp = 0;

for m=1:MMAX

for i=1:LPROB

[adj, adj_t] = graphgen(N, m, 1, i);

[tKolor, tPorw, tmp1, tmp2 ] = bfs_tss(adj, 1, N-1 );

ileKolor_tmp = ileKolor_tmp + tKolor;

ilePorw_tmp = ilePorw_tmp + tPorw;

end

ileKolor(m) = ileKolor_tmp/LPROB;

ilePorw(m) = ilePorw_tmp/LPROB;

ileKiP(m) = ileKolor(m) + ilePorw(m);

end

z=1:MMAX;

hold on

grid on

plot( z, ileKolor(z), 'b-', z, ilePorw(z), 'g-', z, ileKiP(z), 'black-' );

legend( 'podstawienie wartosci atrybutu color', 'porownanie wartosci atr. color', 'suma podstawien i porownan');

xlabel( 'ilosc krawedzi' );

ylabel( 'ilosc operacji' );

title( 'Badanie zlozonosci obliczeniowej alg. bfs-tss w funkcji liczby krawedzi');

function [ileKolor, ilePorw, distance,predecessor]=bfs_tss(adj,s,len)

ileKolor = 0; ilePorw = 0;

% inicjalizacja

[Q,head,tail]=startqueue(len);

for i=1:length(adj) color(i)=0; distance(i)=Inf; predecessor(i)=0; ileKolor = ileKolor + 1; end

% zaznaczenie wezla zrodlowego

ileKolor = ileKolor + 1;

color(s)=1; distance(s)=0; predecessor(s)=0;

[Q,tail,err]=enqueue(Q,s,head,tail,len);

if (err==1) %display('enqueue: kolejka pelna');

return; end

% pobieranie z kolejki dopóki nie jest pusta

while (head~=tail)

[u,head,err]=dequeue(Q,head,tail,len);

if (err==1) %display('dequeue: kolejka pusta');

return; end

% wprowadzanie do kolejki nowych wierzchołków szarych

for j=1:size(adj(u).sasiedzi,2)

v=adj(u).sasiedzi(j);

ilePorw = ilePorw + 1;

if (color(v)==0)

ilekKolor = ileKolor + 1;

color(v)=1; distance(v)=distance(u)+1; predecessor(v)=u;

[Q,tail,err]=enqueue(Q,v,head,tail,len);

if (err==1) %display('enqeue: kolejka pelna');

return; end

end

end

color(u)=2;

ileKolor = ileKolor + 1;

%display(['wezel: ',int2str(u),' predecessor= ',int2str(predecessor(u)),' d= ', int2str(distance(u))]);end

---