- /
-
Show Me the Way to Go Home
on 24 Oct 2021
- 2
- 25
- 0
- 0
- 251
% 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
end
plot(x(r),'o-',LineW=2)
title("dist="+L(s),Color="w")
axis square off
set(gcf,Color=[0 0.1 0.3])