Show Me the Way to Go Home

on 24 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);

% Circuit length calculation function

% I realized I could just throw out the distance matrix altogether.

% The result is economical in code space, but obviously expensive in

% computation, since it constantly recomputes the same distances over and

% over, but oh well.

L=@(r)sum(abs(diff(x(r))));

% Improve my algorithm to find a shorter route r

r=1:n;

t=inf;

for i=1:1e5

s=r;

% Pick two cities, and see if it's faster to flip the route between

% them. Here I'm trying to preserve the starting and finishing cities.

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

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

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

u=L(s);

if u<t

r=s;

t=u;

end

plot(x(r),'o-',LineW=2)

title("dist="+L(s),Color="w")

axis square off

set(gcf,Color=[0 0.1 0.3])