Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Основи проектування систем штучного інтелекту
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет
«Львівська політехніка»
кафедра САПР
Лабораторна робота №2
з курсу “Основи проектування систем штучного інтелекту”
тема: АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI.
Виконав:
cт. гр. КН-3
Львів-2008
1.Мета роботи
Вивчити принципи роботи максимінного алгоритму розпізнавання образів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Максимінний алгоритм розпізнавання образів
Алгоритм використовує евклiдову вiдстань. Алгоритм, у принципi, аналогiчний схемi евристичного алгоритму порогової величини, за виключенням тiєї обставини, що, в першу чергу, вин виявляє найвiддаленiшi кластори. Один з об'єктiв (X1) довiльним чином назначається центром першого кластера. Потiм вiдшукується образ, розмiщений вiд образа X1 найдалi, який призначається центром кластера Z2. На третьому кроцi алгоритму здiйснюється обчислення вiдстаней мiж всiма iншими образами вибiрки i центрами кластерiв Z1 i Z2. В кожнiй парi цих вибірок вибирається мiнiмальне. Пiсля цього видiляється максимальне з цих мiнiмальних вiдстаней. Якщо останнє складає значну частину вiдстанi мiж кластерами Z1 i Z2 (половина цiєї вiдстанi), вiдповiдний образ призначається центром кластера Z3. Iнакше - виконання алгоритму припиняється.
В загальному випадку описана процедура повторюється до тих пiр, поки на якомусь кроцi не буде отримане максимальне значення вiдстанi, для якої умова, що викликає видiлення кластера, не виконується.
1. Z1=X1
2. Обчислити Di1
3. Вибрати Ki(1)=max{Di1} i1 ; L1=Ki(1)
4. Z2=Xi
5. Обчислити Di1, Di2 i1,2
6. Обчислити Ai=min{Di1,Di2} i1,2
7. Обчислити Ki(2)=max{Ai} i1,2 ; L2=Ki(2)
8. Якщо L2>0.5L1, тодi Z3=Xi. Iнакше - STOP.
9. Визначити середню арифметичну величину попереднiх максимальних
вiдстаней:
Lc.a.=(L1+L2)/2
10. Обчислити Di1, Di2, Di3 i1,2,3
11. Обчислити Ai=min{Di1, Di2, Di3}
12. Обчислити Ki(3)=max{Ai} ; L3=Ki(3)
13. Якщо Li>0.5La.c., тодi Z4=Xi. Iнакше - STOP.
14. Обчислити Lc.a.=(L1+L2+L3)/3
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
4.6. Х1(0,4), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(8,8), Х13(12,7), Х14(12,12), Х15(0,3).
Програмна реалізація:
Program Laba_1;
Uses CRT;
const q = 15 ;
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]:= 0 ; y[1]:=4;
x[2]:= 0 ; y[2]:=5;
x[3]:= 0 ; y[3]:=6;
x[4]:= 1 ; y[4]:=4;
x[5]:= 5 ; y[5]:=0;
x[6]:= 6 ; y[6]:=0;
x[7]:= 7 ; y[7]:=0;
x[8]:= 6 ; y[8]:=1;
x[9]:= 5 ; y[9]:=5;
x[10]:=6 ; y[10]:=6;
x[11]:=7 ; y[11]:=7;
x[12]:=8 ; y[12]:=8;
x[13]:=12; y[13]:=9;
x[14]:=12; y[14]:=12;
x[15]:= 0; y[15]:=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(' NEW_centre = 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(' NEW_centre = X(',centre[3],
') d_max = ',dmax_z[2]:2:1); textcolor(15);end
else begin textcolor(4);
writeln('THERE ARE NO MORE ANY CLASTERS !!!');
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];
{For i:=1 to 12 do
write(' ',min[i]:2:1);}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;
{writeln(dmax_z[k]:2:1);}
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(' NEW_centre = X(',centre[k+1],
') d_max = ',dmax_z[k]:2:1); textcolor(15);
k:=k+1; goto next;
end else begin
textcolor(4);
writeln(' THERE ARE NO MORE ANY CLASTERS !!!');
textcolor(15);
goto quit; end;
quit:;
writeln;
readln;
END.
Результат виконання:
Z1(0;4)
x1 (0;4) 0.0
x2 (0;5) 1.0
x3 (0;6) 2.0
x4 (1;4) 1.0
x5 (5;0) 6.4
x6 (6;0) 7.2
x7 (7;0) 8.1
x8 (6;1) 6.7
x9 (5;5) 5.1
x10(6;6) 6.3
x11(7;7) 7.6
x12(8;8) 8.9
x13(12;9) 13.0
x14(12;12) 14.4
x15(0;3) 1.0
NEW_centre = X(14) d_max = 14.4
Z1(0;4) Z2(12;12)
x1 (0;4) 0.0 14.4
x2 (0;5) 1.0 13.9
x3 (0;6) 2.0 13.4
x4 (1;4) 1.0 13.6
x5 (5;0) 6.4 13.9
x6 (6;0) 7.2 13.4
x7 (7;0) 8.1 13.0
x8 (6;1) 6.7 12.5
x9 (5;5) 5.1 9.9
x10(6;6) 6.3 8.5
x11(7;7) 7.6 7.1
x12(8;8) 8.9 5.7
x13(12;9) 13.0 3.0
x14(12;12) 14.4 0.0
x15(0;3) 1.0 15.0
NEW_centre = X(7) d_max = 8.1
min Z3(7;0)
x1 (0;4) 0.0 8.1
x2 (0;5) 1.0 8.6
x3 (0;6) 2.0 9.2
x4 (1;4) 1.0 7.2
x5 (5;0) 6.4 2.0
x6 (6;0) 7.2 1.0
x7 (7;0) 8.1 0.0
x8 (6;1) 6.7 1.4
x9 (5;5) 5.1 5.4
x10(6;6) 6.3 6.1
x11(7;7) 7.1 7.0
x12(8;8) 5.7 8.1
x13(12;9) 3.0 10.3
x14(12;12) 0.0 13.0
x15(0;3) 1.0 7.6
NEW_centre = X(11) d_max = 7.0
min Z4(7;7)
x1 (0;4) 0.0 7.6
x2 (0;5) 1.0 7.3
x3 (0;6) 2.0 7.1
x4 (1;4) 1.0 6.7
x5 (5;0) 2.0 7.3
x6 (6;0) 1.0 7.1
x7 (7;0) 0.0 7.0
x8 (6;1) 1.4 6.1
x9 (5;5) 5.1 2.8
x10(6;6) 6.1 1.4
x11(7;7) 7.0 0.0
x12(8;8) 5.7 1.4
x13(12;9) 3.0 5.4
x14(12;12) 0.0 7.1
x15(0;3) 1.0 8.1
THERE ARE NO MORE ANY CLASTERS !!!
Висновок: У даній лабораторній роботі ми вивчили принципи роботи максимінного алгоритму розпізнавання образів. Написали програму, яка реалізовує цей алгоритм.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора