- /
-
A Slightly Shorter Trip
on 22 Oct 2021
- 1
- 34
- 4
- 0
- 268
% This is a traveling salesman problem
% Use the cities defined by x
rng(0)
n=30;
x=rand(n,1)+1i*rand(n,1);
% Generate distance matrix d
d=[];
for i=1:n
for j=1:i
d(i,j)=abs(x(i)-x(j));
end
end
d=d+d';
% Circuit length calculation function
len=@(r)sum(d(sub2ind([n,n],r,circshift(r,1))));
% Improve my algorithm to find a shorter route r
r=1:n;
t=inf;
for i=1:5e6
rn=r;
ix=randi(n-1);
rn=randperm(n);
tn=len(rn);
if tn<t
r=rn;
t=tn;
end
end
plot(x(r),'o-')
title("dist = "+len(r))
axis square
