了解EUC_2D边缘权重

Question

我正在为旅行推销员问题构建超启发式框架。

我目前从成本矩阵，它看起来像下面的工作（原谅PHP语法）：

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

这是相当不言自明的，从纽约到洛杉矶的2451的距离，纽约到芝加哥713 。

我在尝试构建一个解析器，它将EUC_2D边缘权重解析为上面显示的格式。问题是我无法理解EUC_2D边缘权重的语义。

EUC_2D加权的一个实例如下所示（从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 

谁能解释加权边缘如何EUC_2D作品？

Answer 1

您提到的示例包含地图上的城市列表。 每行描述一个城市使用3个数字。

city_number - coordinate_x - coordinate_y

因此，例如，行

装置，该城市数60位于与坐标（28，43）在地图上。

的距离向城市A和B定义为

之间的X1 Y1
乙X2 Y2

使用舍入到最接近的整数Eulidean距离计算：

DIST（A， B）= round（sqrt（（x1 - x2）^ 2 +（y1 - y2）^ 2））