Besoin d'aide sur cette représentation de Traveling Salesman problème

Question

je suis tombé sur une solution de voyageur de commerce qui utilise le script Matlab, et dans son code, je trouve qu'il utilise une représentation appelée ville Coordonnées, qui ressemble à:

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

pour 5 villes. À ce stade, je ne sais vraiment pas comment l'auteur a obtenu cette représentation, puisque d'après ce que j'ai vu jusqu'ici, l'information à portée de main devrait être une matrice symétrique 5 * 5 représentant la distance entre deux de ces cinq villes.

Donc, je serais reconnaissant si quelqu'un pouvait me donner une idée sur comment fonctionne cette représentation basée sur les coordonnées. Merci d'avance.

Answer 1

CityCoord (Je pense qu'il manque une lettre) est un tableau de 2 par 5. Je suppose que cela signifie que CityCoord contient deux coordonnées (x, y) pour chaque ville.

Pour créer une matrice 5 par 5 la distance, vous pouvez appeler

squareform(pdist(CityCoord')) 

Answer 2

Si vous ne disposez pas de statistiques Boîte à outils, une forme équivalente à la solution fournie par @Jonas pour calculer la distance euclidienne est :

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

Sinon, nous pouvons utiliser le fait que ||u-v||^2 = ||u||^2 + ||v||^2 - 2*u.v pour mettre en œuvre un code encore plus rapide vectorisé:

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