瞭解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））