МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” іНСТИТУТ КОМП’ютерних НАУК та ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Кафедра “Системи автоматизованого проектування”
ЗВІТ до лабораторної роботи №2 на тему «Алгоритм максимінної відстані» з курсу «Системи штучного інтелекту» Львів-2008 Текст програми: Program Laba_1; Uses CRT; const q = 17 ; type dis = record v:array [1..q] of real; end; var x : array [1..q] of integer; y : array [1..q] of integer; j,i,k:integer; n:array [1..q] of integer; d: array [1..q] of dis; ser:real; t:string; min:array [1..q] of real; dmax_Z:array[1..q] of real; centre: array [1..q] of integer; centrex: array [1..q] of integer; centrey: array [1..q] of integer; xg:real; Label next,quit; BEGIN clrscr; writeln; x[1]:= 1 ; y[1]:=1;x[2]:= 0 ; y[2]:=3; x[3]:= 0 ; y[3]:=4;x[4]:= 4 ; y[4]:=1; x[5]:= 5 ; y[5]:=1;x[6]:= 5 ; y[6]:=2; x[7]:= 5 ; y[7]:=3;x[8]:= 6 ; y[8]:=9; x[9]:= 8 ; y[9]:=6;x[10]:=9 ; y[10]:=2; x[11]:=9 ; y[11]:=5;x[12]:=9 ; y[12]:=6; x[13]:=9 ; y[13]:=7;x[14]:=10; y[14]:=1; x[15]:=10; y[15]:=2;x[16]:=10; y[16]:=3; x[17]:=11; y[17]:=3; t:=' '; textcolor(8); writeln; n[1]:=1; centre[1]:=1; centrex[1]:=x[1]; centrey[1]:=y[1]; textcolor(14); writeln(' Z1(',centrex[1],';',centrey[1],')'); textcolor(15); For i:=1 to q do begin if i<10 then write(' x',i,' (',x[i],';',y[i],')',' ') else if i=12 then write(' x',i,'(',x[i],';',y[i],')',' ') else write(' x',i,'(',x[i],';',y[i],')',' '); d[1].v[i]:=sqrt(sqr((centrex[1]-x[i]))+sqr((centrey[1]-y[i]))); writeln(d[1].v[i]:2:1); end; dmax_z[1]:=d[1].v[1]; centre[2]:=1; For i:=1 to q do if d[1].v[i]>dmax_z[1] then begin dmax_z[1]:=d[1].v[i]; centre[2]:=i; end; textcolor(3); writeln(' NOVYJ CENTR = X(',centre[2],') d_max = ',dmax_z[1]:2:1); textcolor(15); centrex[2]:=x[centre[2]]; centrey[2]:=y[centre[2]]; writeln; textcolor(14); writeln(' Z1(',centrex[1],';',centrey[1],')',' Z2(',centrex[2],';',centrey[2],')'); textcolor(15); For i:=1 to q do begin if i<10 then write(' x',i,' (',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t) else if i=12 then write(' x',i,'(',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t) else write(' x',i,'(',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t); d[2].v[i]:=sqrt(sqr((centrex[2]-x[i]))+sqr((centrey[2]-y[i]))); writeln(d[2].v[i]:2:1); end; For i:=1 to q do begin if d[1].v[i]>d[2].v[i] then min[i]:=d[2].v[i] else min[i]:=d[1].v[i]; end; writeln; dmax_z[2]:=min[1]; For i:=1 to q do if min[i]>dmax_z[2] then begin dmax_z[2]:=min[i]; centre[3]:=i; end; if dmax_z[2] >= 0.5*(dmax_z[1]/1) then begin textcolor(3); writeln(' NOVYJ CENTR = X(',centre[3],') d_max = ',dmax_z[2]:2:1); textcolor(15); end else begin textcolor(4); writeln('***NEMAJE BILSHE KLASTERIV*** !!!'); textcolor(15); goto quit; end; k:=3; NEXT:; readln; centrex[k]:=x[centre[k]]; centrey[k]:=y[centre[k]]; textcolor(14); writeln(' min',' Z',k,'(',centrex[k],';',centrey[k],')'); textcolor(15); For i:=1 to q do begin if i<10 then write(' x',i,' (',x[i],';',y[i],')',t,min[i]:2:1,t) else if i=12 then write(' x',i,'(',x[i],';',y[i],')',' ',min[i]:2:1,t) else write(' x',i,'(',x[i],';',y[i],')',t,min[i]:2:1,t); d[k].v[i]:=sqrt(sqr((centrex[k]-x[i]))+sqr((centrey[k]-y[i]))); writeln(d[k].v[i]:2:1); end; For i:=1 to q do if d[k].v[i]<min[i] then min[i]:=d[k].v[i]; writeln; dmax_z[k]:=min[1]; For i:=1 to q do if min[i]>dmax_z[k] then begin dmax_z[k]:=min[i]; centre[k+1]:=i; end; ser:=0; j:=0; For i:=k-1 downto 1 do begin ser:=ser+dmax_z[i]; j:=j+1; end; ser:=ser/j; ser:=0.5*ser; if dmax_z[k] >= ser then begin textcolor(3); writeln(' NOVYJ CENTR = X(',centre[k+1],') d_max = ',dmax_z[k]:2:1); textcolor(15); k:=k+1; goto next; end else begin textcolor(4); writeln(' ***NEMAJE BILSHE KLASTERIV*** '); textcolor(15); goto quit; end; quit:; writeln; readln; END. Результат виконання програми NOVYJ CENTR = X(17) d_max = 10.2 Z1(1;1) Z2(11;3) x1 (1;1) 0.0 10.2 x2 (0;3) 2.2 11.0 x3 (0;4) 3.2 11.0 x4 (4;1) 3.0 7.3 x5 (5;1) 4.0 6.3 x6 (5;2) 4.1 6.1 x7 (5;3) 4.5 6.0 x8 (6;9) 9.4 7.8 x9 (8;6) 8.6 4.2 x10(9;2) 8.1 2.2 x11(9;5) 8.9 2.8 x12(9;6) 9.4 3.6 x13(9;7) 10.0 4.5 x14(10;1) 9.0 2.2 x15(10;2) 9.1 1.4 x16(10;3) 9.2 1.0 x17(11;3) 10.2 0.0 NOVYJ CENTR = X(8) d_max = 7.8 Висновок На цій лабораторній роботі я вивчив принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів. Написав програму реалізації алгоритму.