Решение задачи коммивояжера методом ветвей и границ в MatLAB
code the TSP MatLAB
xx(1)=2520;yy(1)=60;
xx(2)=3405;yy(2)=2580;
xx(3)=5955;yy(3)=2625;
xx(4)=3810;yy(4)=4110;
xx(5)=4215;yy(5)=5910;
xx(6)=2820;yy(6)=4770;
xx(7)=1065;yy(7)=5940;
xx(8)=1650;yy(8)=3840;
xx(9)=30;yy(9)=2550;
xx(10)=2055;yy(10)=2580;
xx(11)=2790;yy(11)=3495;
figure(1);
plot(xx,yy,'b+');text(87,7,'\rightarrow1');
xx1=xx;xx1(31)=xx(1);
yy1=yy;yy1(31)=yy(1);
figure(2);
plot(xx1,yy1);
for i=1:N
for j=1:N
if i==j
continue;
end
d(i,j)=sqrt((xx(i)-xx(j)).^2+(yy(i)-yy(j)).^2);
end
end
gen=1;
time1=datestr(now)
while gen =10
[f,T]=trp(a,d,t0,tf);
opf(gen)=f;
path(gen,:)=T;
gen=gen+1;
end
time2=datestr(now)
disp('ЧоРЎВ·ѕ¶єН')
min(opf)
disp('ЧоУЕВ·ПЯ')
T
for i=1:N
xx2(i)=xx(T(i));
yy2(i)=yy(T(i));
end
xx2(31)=xx(1);yy2(31)=yy(1);
figure(3);plot(xx2,yy2);
function [f,T]=trp(a,d,t0,tf)
[m,n]=size(d);
L=1000*n;
t=t0;
pi0=1:n;
min_f=0;
for k=1:(n-1)
min_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
while t tf
for k=1:L
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f 0
pi0=pi_1;
elseif exp(-d_f/t) r_r
pi0=pi_1;
else
pi0=pi0;
end
end
f_temp=0;
for k=1:(n-1)
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f f_temp
min_f=f_temp;
p_min=pi0;
end
t=a*t;
end
f=min_f;
T=p_min;
.