R中的TSP，错误的游览长度

Question

我有简单的距离table(矩阵):

datalist <- data.table(V1=c(0, 28635.76, 16496.41), V2=c(28635.76, 0, 22032.14), V3 = c(16496.41, 22032.14, 0))

当我从 R 包测试 TSP 算法时 "TSP" 我得到的旅行长度结果：98559.14。但是当我添加距离 "by hand" 时，我的结果是 16496.41+22032.14+28635.76 = 67164.31 = tour_length(tour)。我的其余代码：

  tspObj <- ETSP(datalist)
  tour <- solve_TSP(tspObj, start = 1, method = "two_opt")
  #tour length
  tour_length(tour)

有人知道为什么我得到两个不同的结果吗？

Answer 1

ETSP中的E代表"Euclidean"。此函数将 V1、V2、V3 解释为 3 维欧几里德 space 中的 3 个点，而不是距离矩阵的行（您似乎在想） .注意：

> sum(sqrt(sum((V1-V2)^2)) + sqrt(sum((V1-V3)^2)) + sqrt(sum((V2-V3)^2)))
[1] 98559.14

还有另一个构造函数，简称为 TSP。您不能直接向它提供数据 table，但可以执行以下操作：

> tspObj <- TSP(as.dist(datalist))
> tour <- solve_TSP(tspObj, start = 1, method = "two_opt")
> tour
object of class ‘TOUR’ 
result of method ‘two_opt’ for 3 cities
tour length: 67164.31

R中的TSP，错误的游览长度

TSP in R, wrong tour length

r

traveling-salesman