如何使用 TSP 包从 R 中的旅行商问题中获取路径
How to obtain the path from a traveling salesman problem in R using TSP package
假设我有以下成本矩阵，我想从旅行商问题的角度通过最近插入法从节点 20 开始的路径（和总成本）。
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))
ds.ex
2 13 14 17 20
2 0.0 Inf Inf 1.9 1.7
13 Inf 0.0 7.3 7.4 7.2
14 Inf 7.3 0.0 7.7 7.8
17 1.9 7.4 7.7 0.0 9.2
20 1.7 7.2 7.8 9.2 0.0
我正在使用TSP包来解决：
ds.ex.tsp <- as.TSP(ds.ex)
(a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start=5))
object of class ‘TOUR’
result of method ‘nearest_insertion’ for 5 cities
tour length: 25.8
我可以从以下位置获取路径吗：
`attr(a, "names")
[1] "20" "2" "17" "14" "13"
?
如果这确实是路径，为什么路径 20-2-17-13-14 不是结果？一旦访问了节点 20、2 和 17，成本较小的是 13 而不是 14。
提前致谢！
我们可以使用labels.TSP，即
library(TSP)
ds.ex.tsp <- as.TSP(ds.ex)
a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start = 5)
labels(a)
#[1] "20" "13" "14" "17" "2"
请注意，在最近的插入试探法中，您可以根据城市与路线中已有的所有城市的最小距离将城市添加到路线中。如果有两个城市的距离相同，则随机选择一个城市。因此 solve_TSP 可能 return 复制时的不同最佳路径。你举的例子好像是这样。
示例数据
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))
假设我有以下成本矩阵，我想从旅行商问题的角度通过最近插入法从节点 20 开始的路径（和总成本）。
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))
ds.ex
2 13 14 17 20
2 0.0 Inf Inf 1.9 1.7
13 Inf 0.0 7.3 7.4 7.2
14 Inf 7.3 0.0 7.7 7.8
17 1.9 7.4 7.7 0.0 9.2
20 1.7 7.2 7.8 9.2 0.0
我正在使用TSP包来解决：
ds.ex.tsp <- as.TSP(ds.ex)
(a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start=5))
object of class ‘TOUR’
result of method ‘nearest_insertion’ for 5 cities
tour length: 25.8
我可以从以下位置获取路径吗：
`attr(a, "names")
[1] "20" "2" "17" "14" "13"
?
如果这确实是路径，为什么路径 20-2-17-13-14 不是结果？一旦访问了节点 20、2 和 17，成本较小的是 13 而不是 14。
提前致谢！
我们可以使用labels.TSP，即
library(TSP)
ds.ex.tsp <- as.TSP(ds.ex)
a <- solve_TSP(ds.ex.tsp, method = "nearest_insertion", start = 5)
labels(a)
#[1] "20" "13" "14" "17" "2"
请注意，在最近的插入试探法中，您可以根据城市与路线中已有的所有城市的最小距离将城市添加到路线中。如果有两个城市的距离相同，则随机选择一个城市。因此 solve_TSP 可能 return 复制时的不同最佳路径。你举的例子好像是这样。
示例数据
ds.ex <- structure(c(0, Inf, Inf, 1.9, 1.7, Inf, 0, 7.3, 7.4, 7.2, Inf,
7.3, 0, 7.7, 7.8, 1.9, 7.4, 7.7, 0, 9.2, 1.7, 7.2, 7.8, 9.2,
0), .Dim = c(5L, 5L), .Dimnames = list(c("2", "13", "14", "17",
"20"), c("2", "13", "14", "17", "20")))