Need some help on this representation of Traveling Salesman Problem

Question

I came across a traveling salesman solution which uses Matlab script, and in its code, I found that it uses a representation called City Coordinates, which looks like:

CityCood = [0.4000,0.2439,0.1707,0.2239,0.5171;0.4439,0.1463,0.2293,0.7610,0.9414]

for 5 cities.

At this point, I am really clueless about how did the author get this representation, since from what I have seen so far, the information at hand should be a 5*5 symmetric matrix representing distance between any two of these five cities.

So I would be grateful if anyone could give me an idea on how that coordinate-based representation works. Thanks in advance.

Answer 1

CityCoord (I think there's a letter missing) is a 2-by-5 array. I assume this means thatCityCoord contains two coordinates (x,y) for every single city.

To create a 5-by-5 distance matrix, you can call

squareform(pdist(CityCoord'))

Answer 2

If you don't have the Statistics Toolbox, an equivalent form to the solution provided by @Jonas to compute the Euclidean distance is:

%# dist(u,v) = norm(u-v) = sqrt(sum((u-v).^2))
D = cell2mat( arrayfun( ...
    @(i) sqrt( sum( bsxfun(@minus, CityCoord, CityCoord(:,i)).^2 ) ), ...
    (1:size(CityCood,2))', ...
    'UniformOutput',false) );

Otherwise, we can use the fact that ||u-v||^2 = ||u||^2 + ||v||^2 - 2*u.v to implement an even faster vectorized code:

X = sum(CityCoord.^2);
D = real( sqrt(bsxfun(@plus,X,X')-2*(CityCoord'*CityCoord)) );