Comprendre la pondération des arêtes EUC_2D

Question

Je suis en train de construire un cadre hyper-heuristique pour le problème du voyageur de commerce.

Je travaille actuellement à partir d'une matrice de coût qui ressemble à la suivante (excusez la syntaxe PHP):

("New York") => array(0, 2451, 713), 
("Los Angeles") => array(2451, 0, 1745), 
("Chicago") => array(713, 1745, 0), 

Ceci est assez explicite, la distance de New York à Los Angeles 2451, État de New York à Chicago 713

Je tente de construire un analyseur qui analyse la pondération de bord EUC_2D au format que j'ai montré ci-dessus. Le problème est que je ne peux pas comprendre la sémantique de la pondération des arêtes EUC_2D.

Un exemple de pondération EUC_2D est indiquée ci-dessous (tirée de here):

1 0 13 
2 0 26 
3 0 27 
4 0 39 
5 2 0 
6 5 13 
7 5 19 
8 5 25 
9 5 31 
10 5 37 

Quelqu'un peut-il expliquer comment fonctionne la pondération bord EUC_2D?

Answer 1

L'exemple que vous avez mentionné contient la liste des villes sur une carte. Chaque rangée décrit une ville en utilisant 3 nombres.

city_number - coordinate_x - coordinate_y

Ainsi, par exemple ligne

moyens, ce numéro de ville 60 se trouve sur la carte avec des coordonnées (28, 43).

La distance entre les villes A et B définis comme

A x1 y1
B x2 y2

est calculée en utilisant la distance Eulidean arrondi au nombre entier le plus proche:

dist (A, B) = rond (sqrt ((x1 - x2)^2 + (y1 - y2)^2))