Нужна помощь в этом представлении проблемы коммивояжера

Question

Я наткнулся на решение для коммивояжера, которое использует скрипт Matlab, и в его коде я обнаружил, что оно использует представление с названием Городские координаты, которое выглядит следующим образом:

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

для 5 городов.*

На данный момент я действительно не знаю, как автор получил это представление, поскольку из того, что я видел до сих пор, имеющейся информацией должна быть симметричная матрица 5 * 5, представляющая расстояние между любыми двумя из этих пятигорода.

Поэтому я был бы признателен, если бы кто-нибудь мог дать мне представление о том, как работает это представление на основе координат.Заранее спасибо.

Answer 1

CityCoord (я думаю, что здесь не хватает буквы) - это массив 2 на 5.Я предполагаю, что это означает, что CityCoord содержит две координаты (x, y) для каждого города.

Чтобы создать матрицу расстояний 5 на 5, вы можете позвонить

squareform(pdist(CityCoord'))

Answer 2

Если у вас нет набора инструментов статистики, форма, эквивалентная решению, предоставленному @ Jonas для вычисления евклидова расстояния:

%# 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) );

В противном случае мы можем использоватьтот факт, что ||u-v||^2 = ||u||^2 + ||v||^2 - 2*u.v для реализации еще более быстрого векторизованного кода:

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