A Slightly Shorter Trip

on 22 Oct 2021

% 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

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

plot(x(r),'o-')

title("dist = "+len(r))

axis square

Load full remix tree