Ćwiczenie numer: 5 Data oddania ćwiczenia: Temat: Algorytm dziel i zwyciężaj

1. Treść zadania.

a) Proszę znaleźć najmniejszą odległość pomiędzy dwoma statkami, których pozycje są oznaczone w współrzędnych X i Y (największe prawdopodobieństwo kolizji). Przeszukiwanie należy wykonać dwoma metodami: wyczerpującą oraz dziel i zwyciężaj. Zależności czasowe dla obu metod przedstawić na wykresie. Należy tak dobrać liczbę węzłów aby możliwe było dokonanie pomiarów.

b) Wnioski ogólne dotyczące efektywności obu metod jaka jest ich złożoność oraz do jakiego typu problemów one należą.

2. Metoda wyczerpująca.

Przykładowy rysunek.

Odległość pomiędzy statkami wyznaczamy ze wzoru:

W metodzie wyczerpującej wyznaczając najmniejsza odległość dokonujemy n*n porównań . Spowodowane jest to tym, że w metodzie tej sprawdzamy odległość pomiędzy wszystkimi statkami (każdy z każdym) i zapisujemy za każdym razem najmniejszą. Złożoność tego algorytmu wynosi O(n²).

3. Metoda dziel i zwyciężaj.

Przykładowy rysunek.

Opis działania algorytmu w programie.

W moim programie algorytm ten realizują głównie dwie procedury: dziel i xxx. Pierwsza z nich wstępnie sortuje tablice X i Y po wartościach z tablic rekordów statki.x i statki.y . Następnie wywoływana jest procedura xxx, która zwraca przez wartość wynik za pomocą zmiennej rozwiązanie. Procedura xxx na samym początku sprawdza czy liczba statków >=3 jeśli tak to wyszukuje najmniejszej odległości metodą wyczerpującą. W przeciwnym razie wyznaczana jest środkowa współrzędna zmienna linia, która dzieli statki "na mapie" na dwie równe części +/- 1 statek. Kolejnym krokiem algorytmu jest podział tablicy Y na podtablice na lewo / prawo od lini z zachowaniem wzajemnego uporządkowania względem X. Następnie procedura xxx zostaje wywołana rekurencyjnie dla lewej i prawej części dzieląc obszar na podobszary tak długo, aż w danym obszarze będą max 3 statki. Procedury wychodząc z rekursji zwracają wartości najlepszych rozwiązań dla lewego i prawego obszaru. Najmniejsza odległość pomiędzy statkami dla obu obszarów jest rozwiązaniem minimalnym, która wyznacza szerokość pasa δ na lewo i prawo od lini dzielącej oba obszary. Wówczas sprawdzane jest czy aby któreś z punktów leżących w obszarze pasa granicznego leżącego w pasie +/- δ od lini granicznej niż minimalne rozwiązanie z obu obszarów. W tym celu algorytm sprawdza każdy punkt z siedmioma kolejnymi punktami z obszaru. Jeżeli, któreś z rozwiązań jest mniejsze od minimalnego to wówczas ono zostaje rozwiązaniem minimalnym. Złożoność tego algorytmu wynosi O(nlogn).

4. Kod programu.

program _statki_;

uses

crt,dos,graph;

const max=200;

sciezka='c:\bp\bgi';

type statek=record

x,y:integer;

end;

odleglosc_r=record

s1,s2:integer; {statki}

d:longint; {odleglosc pomiedzy statkiem s1 a s2}

end;

var

statki :array [1..max] of statek;

x,y,yy:array [1..max] of integer;

pomoc: array [1..max] of integer;

i,n:integer;

min_rozw_w,rozwiazanie:odleglosc_r;

czas_w,czas_d,poczatek,koniec:real;

wybor:char;

Function WlaczTimer :LongInt;

Var Reg :Registers;

Znacznik :Byte;

Begin

Znacznik:=0;

Reg.AH:=$83;

Reg.AL:=0;

Reg.CX:=$7FFF;

Reg.DX:=$FFFF;

Reg.BX:=Ofs(Znacznik);

Reg.ES:=Seg(Znacznik);

Intr($15,Reg);

WlaczTimer:=$7FFFFFFF;

End;

Function WylaczTimer :LongInt;

Var Reg :Registers;

Begin

WylaczTimer:=MemL[$0040:$009C];

Reg.AH:=$83;

Reg.AL:=1;

Intr($15,Reg);

End;

Function CzasWykonania :Real;

Var Czas :Real;

Begin

Czas:=(Poczatek-koniec);

CzasWykonania:=Czas;

End;

procedure losuj_statki;

var i:integer;

begin

for i:=1 to n do

begin

statki[i].x:=random(630);

statki[i].y:=random(350);

end;

end;

procedure wyczerpujace; {wyczerpujace wyszukiwanie kolizji}

var

i,j:integer;

k1,k2,odl:longint;

begin

k1:=statki[1].x-statki[2].x;

k2:=statki[1].y-statki[2].y;

odl:=sqr(k1)+sqr(k2);

min_rozw_w.d:=odl;

min_rozw_w.s1:=1;

min_rozw_w.s2:=2;

for i:=1 to n do

for j:=1 to n do

if i<>j then

begin

k1:=statki[i].x-statki[j].x;

k2:=statki[i].y-statki[j].y;

odl:=k1*k1+k2*k2;

if odl<min_rozw_w.d then

begin

min_rozw_w.d:=odl;

min_rozw_w.s1:=i;

min_rozw_w.s2:=j;

end;

end;

end;

procedure quicksort_y(l,p:word);{dla tablicy y}

var

temp,i,j,srodek:word; {porownuje statki na osi Y

a zmieniam indeksy tab. Y}

begin

srodek:=(l+p) div 2;

i:=l;j:=p;

repeat

while (statki[y[i]].y<=statki[y[srodek]].y) and (i<>srodek) do i:=i+1;

while (statki[y[j]].y>=statki[y[srodek]].y)and (j<>srodek) do j:=j-1;

if i<j then begin temp:=y[i];y[i]:=y[j];y[j]:=temp;end;

if i=srodek then srodek:=j else

if j=srodek then srodek:=i;

until j=i;

if i>l then Quicksort_y(l,i-1);

if j<p then Quicksort_y(i+1,p)

end;

procedure quicksort_x(l,p:word); {dla tablicy X}

var

temp,i,j,srodek:word; {porownuje statki na osi X

a zmieniam indeksy tab. X}

begin

srodek:=(l+p) div 2;

i:=l;j:=p;

repeat

while (statki[x[i]].x<=statki[x[srodek]].x) and (i<>srodek) do i:=i+1;

while (statki[x[j]].x>=statki[x[srodek]].x)and (j<>srodek) do j:=j-1;

if i<j then begin temp:=x[i];x[i]:=x[j];x[j]:=temp;end;

if i=srodek then srodek:=j else

if j=srodek then srodek:=i;

until j=i;

if i>l then Quicksort_x(l,i-1);

if j<p then Quicksort_x(i+1,p)

end;

procedure p(var a,b:odleglosc_r); {w a bedzie mniejsza odleglosc}

var k1,k2:longint; {porownywanie miedzy 2 parami statkow}

begin

k1:=statki[a.s1].x-statki[a.s2].x;

k2:=statki[a.s1].y-statki[a.s2].y;

a.d:=sqr(k1)+sqr(k2);

k1:=statki[b.s1].x-statki[b.s2].x;

k2:=statki[b.s1].y-statki[b.s2].y;

b.d:=sqr(k1)+sqr(k2);

if a.d>b.d then

begin

a.s1:=b.s1;

a.s2:=b.s2;

a.d:=b.d;

end;

end;

procedure xxx(a,b:integer;var min:odleglosc_r);

var

srodek_x:integer;

i,j,k,linia:integer;

l_margines,p_margines,k1,k2,odl:longint;

para:odleglosc_r;

lewe_rozw,prawe_rozw:odleglosc_r;

sqrt_min_odl:real;

begin {uwaga wszystkie odleglosci

to kwadraty odleglosci}

if b-a+1<=3 then

begin

if b-a+1=3 then

begin {trzy statki}

min.s1:=x[a]; {1}

min.s2:=x[a+1]; {2}

para.s1:=x[a+1]; {2}

para.s2:=x[b]; {3}

p(min,para); {1-2,2-3}

para.s1:=x[a];

para.s2:=x[b];

p(min,para); {1-3}

end

else

begin

min.s1:=x[a]; {dwa statki}

min.s2:=x[b];

k1:=statki[x[a]].x-statki[x[b]].x;

k2:=statki[x[a]].y-statki[x[b]].y;

min.d:=k1*k1+k2*k2;

end;

end

else

begin

linia:=(b+a) div 2; {linia dzielaca na pol os X}

srodek_x:=statki[x[linia]].x; {wspolrzedna lini na osi X}

for k:=a to b do pomoc[k]:=y[k];

j:=linia+1;

i:=a;

for k:=a to b do

if statki[pomoc[k]].x<=srodek_x then

begin

y[i]:=pomoc[k];

i:=i+1;

end {podzial Y na podtablice na lewo/prawo od lini}

else {z zachowaniem wzajemnego uporzadkowania wzgledem Y}

begin

y[j]:=pomoc[k];

j:=j+1;

end;

xxx(a,linia,lewe_rozw); {wywolanie rekurencyjne dla lewej}

xxx(linia+1,b,prawe_rozw); {i prawej czesci}

if lewe_rozw.d<prawe_rozw.d then

begin

min.s1:=lewe_rozw.s1;

min.s2:=lewe_rozw.s2;

min.d:=lewe_rozw.d;

end

else

begin

min.s1:=prawe_rozw.s1;

min.s2:=prawe_rozw.s2;

min.d:=prawe_rozw.d;

end;

{min_rozw zawiera najmniejsza odleglosc miedzy punktami liczonymi w

lewym i prawym podzbiorze, trzeba jeszcze uwzglednic punkty lezace

w pasie xsrodkowe +- min_odl}

l_margines:=round(srodek_x-sqrt(min.d));

p_margines:=round(srodek_x+sqrt(min.d)); {pas przygraniczny delta +/- min.d}

j:=0;

for i:=a to b do {yy z punktami z pasa delta}

if (statki[x[i]].x>=l_margines) and (statki[x[i]].x<=p_margines) then

begin

j:=j+1;

yy[j]:=x[i];

end;

{patrzymy, czy jakies punkty z pasa granicznego nie leza blizej od

najblizszych znalezionych wczesniej niezaleznie w lewym i prawym obszarze}

for i:=1 to j do

for k:=i+1 to i+1+7 do {od biezacego pkt i do kolejnych 7 punktow}

begin

if k>j then break;

k1:=statki[yy[i]].x-statki[yy[k]].x;

k2:=statki[yy[i]].y-statki[yy[k]].y;

odl:=k1*k1+k2*k2;

if odl<min.d then

begin

min.d:=odl;

min.s1:=yy[i];

min.s2:=yy[k];

end;

end;

end;

end;

procedure dziel; {dziel i zwyciezaj}

begin

for i:=1 to n do {inicjalizacja tablic x i y}

begin

x[i]:=i;

y[i]:=i;

end;

quicksort_x(1,n); {wywolanie sortowania tab X i Y}

quicksort_y(1,n); {po wartosciach statki.x/.y }

xxx(1,n,rozwiazanie);

end;

procedure pokaz_statki;

var

i,j:integer;

begin

for i:=1 to n do

writeln('statek nr: ',i,' pol. X ', statki[i].x,' Y ',statki[i].y);

end;

procedure rysuj_punkty;

var

n,i:integer;

s:string;

begin

for i:=1 to n do

begin

{ circle(statki[i].x+10,statki[i].y+10,10);}

str(i,s);

outtextxy(statki[i].x+7,statki[i].y+7,s);

end;

end;

procedure pisz_wyniki;

var

s1,s2,s3,text:string;

begin

circle(statki[min_rozw_w.s1].x+12,statki[min_rozw_w.s1].y+10,9);

circle(statki[min_rozw_w.s2].x+12,statki[min_rozw_w.s2].y+10,9);

str(min_rozw_w.s1,s1);

str(min_rozw_w.s2,s2);

str(sqrt(min_rozw_w.d):3:3,s3);

text:='Metoda "dziel i zwyciezaj" - statek: '+s1+' i '+s2+' odleglosc: '+s3;

outtextxy(50,400,text);

str(rozwiazanie.s1,s1);

str(rozwiazanie.s2,s2);

str(sqrt(rozwiazanie.d):3:3,s3);

text:='Metoda wyczerpujaca - statek: '+s1+' i '+s2+' odleglosc: '+s3;

outtextxy(50,420,text);

end;

procedure prezentacja;

var

crd,mode:integer;

begin

n:=20;

mode:=1;

crd:=detect;

InitGraph(crd,mode,'sciezka');

setcolor(15);

losuj_statki;

rysuj_punkty;

wyczerpujace;

dziel;

pisz_wyniki;

repeat until keypressed;

closegraph;

end;

procedure pomiary;

var

a,krok:integer;

f:text;

begin

poczatek:= WlaczTimer;

koniec:=wylaczTimer;

Assign(f,'statki.txt');

rewrite(f);

writeln(' suma czasu 100 pomiarow dla kazdego n statkow');

writeln(' ile | wyczerpujace | dziel i zwyciezaj');

writeln(f,' ile | wyczerpujace | dziel i zwyciezaj');

krok:=5;

n:=5;

while n<max+krok do

begin

czas_w:=0;

czas_d:=0;

for a:=1 to 100 do

begin

losuj_statki;

poczatek:= WlaczTimer;

wyczerpujace;

koniec:=wylaczTimer;

czas_w:=czas_w+czaswykonania;

poczatek:= WlaczTimer;

dziel;

koniec:=wylaczTimer;

czas_d:=czas_d+czaswykonania;

end;

poczatek:= WlaczTimer;

wyczerpujace;

koniec:=wylaczTimer;

czas_w:=czas_w+czaswykonania;

writeln(n:5,(czas_w):18:0,(czas_d):18:0);

writeln(f,n:5,(czas_w):18:0,(czas_d):18:0);

n:=n+krok;

end;

close(f);

writeln(' ********KONIEC********');

writeln;

sound(1000);

delay(100);

nosound;

readln;

end;

{**********************}

begin

randomize;

repeat

repeat

clrscr;

writeln(' Program statki ');

writeln(' autor: Przemyssaw Grygiel ');

writeln;writeln;writeln;writeln;

writeln(' ------------------- ');

writeln(' | |');

writeln(' | prezentacja - 0 |');

writeln(' | |');

writeln(' | testy - 1 |');

writeln(' | |');

writeln(' | koniec - 2 |');

writeln(' | |');

writeln(' ------------------- ');

wybor:=readkey;

until (wybor='1') or (wybor='0') or (wybor='2') ;

case wybor of

'0': prezentacja;

'1': pomiary;

'2': writeln(' Do zobaczenia !!!');

end;

until wybor='2';

end.

5. Tabela pomiarów.

	metody			metody
ilość statków	wyczerpujaca	dziel i zwycieżaj	ilość statków	wyczerpujaca	dziel i zwycieżaj
[-]	[s]	[s]	[-]	[s]	[s]
5	0.003904	0.010736	105	0.753472	0.260592
10	0.009760	0.018544	110	0.828624	0.282064
15	0.020496	0.033184	115	0.905728	0.312320
20	0.035136	0.038064	120	0.985760	0.341600
25	0.053680	0.042944	125	1.066768	0.362096
30	0.064416	0.076128	130	1.145824	0.383568
35	0.085888	0.087840	135	1.243424	0.388448
40	0.114192	0.091744	140	1.337120	0.395280
45	0.143472	0.092720	145	1.441552	0.395280
50	0.177632	0.107360	150	1.536224	0.406016
55	0.212768	0.133712	155	1.642608	0.406992
60	0.245952	0.160064	160	1.748016	0.417728
65	0.296704	0.179584	165	1.851472	0.427488
70	0.337696	0.182512	170	1.966640	0.439200
75	0.386496	0.193248	175	2.086688	0.442128
80	0.445056	0.190320	180	2.206736	0.447984
85	0.501664	0.202032	185	2.338496	0.449936
90	0.558272	0.208864	190	2.451712	0.466528
95	0.620736	0.211792	195	2.583472	0.486048
100	0.687104	0.230336	200	2.724016	0.505568

6. Wykres.

Zależności czasowe od liczby wierzchołków

dla metody wyczerpującej i dziel i zwyciężaj.

7. Wnioski.

Ze względu na niedokładność funkcji obliczających czas wykonywania się algorytmów zastosowałem w swoich pomiarach sumaryczny czas 100 kolejnych wywołań algorytmu dla tej samej ilości statków.

Zacznę od metody wyszukiwania wyczerpującego, tzn. metody, która porównuje każdy z każdym. W metodzie tej zaraz widać że należy wykonać n porównań, gdzie n jest liczbą statków dla każdego statku. Na tej podstawie łatwo zauważyć, że złożoność tej metody wynosi O(n²) co kwalifikuje ja do problemów o złożoności wykładniczej co widać na wykresie.

Reasumując :

Do zalet tej metody można zaliczyć:

- łatwa implementacja i prostota algorytmu

- efektywność lepsza niż metody dziel i zwyciężaj dla małej ilości obiektów

Do wad tej metody można zaliczyć:

- wykładniczy charakter

- mała odporność na dużą liczbę obiektów

Metoda dziel i zwyciężaj jest rekurencyjnym algorytmem, który za pomocą dzielenia problemu na podproblemy podobnie jak w algorytmie sortowania metodą quicksort osiąga bardzo dobrą wydajność. Zastosowana w tym algorytmie rekurencja i wstępne sortowanie tablic X i Y zawierających indeksy statków powoduje, że złożoność wynosi O(nlogn) co klasyfikuje tę metodę jako metodę o charakterystyce logarytmicznej, co łatwo można zauważyć na wykresie. Algorytm ten ogólnie jest bardzo szybki ale przy małej liczbie obiektów nie sprawuje się tak jakby można było się spodziewać. Spowodowane jest to tym, że algorytm ma bardzo złożoną budowę i znalezienie minimalnej odległości przy małej ilości obiektów staje się na tyle skomplikowane, że lepiej z tym radzi sobie metoda wyczerpująca.

Reasumując :

Do zalet tej metody można zaliczyć:

- logarytmiczny charakter metody

- duża szybkość działania

Do wad tej metody można zaliczyć:

- zawiła implementacja algorytmu

- kiepska wydajność dla małej liczby obiektów

Zastosowanie praktyczne obu metod:

Obie metody można wykorzystać tam, gdzie zależy nam na określeniu wzajemnych położeń obiektów na płaszczyźnie z tym, że metoda wyczerpująca nadaje się właściwie wyłącznie dla ich malej ilości a dziel i zwyciężaj do dużej.

1

5

---