The Astronaut Salesman Problem

on 22 Oct 2021

% This is a traveling salesman problem

% Use the cities defined by x

n=60;

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

f=@(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:1e6

s=r;

k=sort(randi(n-2,2,1)+1);

m=k(1):k(2);

s(m)=s(flip(m));

u=f(s);

if u<t

r=s;

t=u;

end

plot(x(r),'yp:',MarkerS=9)

axis off

set(gcf,Color="k")

Load full remix tree