3

我有一个数据框，其中点的 X 和 Y 坐标如下：

structure(list(X = c(666L, 779L, 176L, 272L, 232L, 74L, 928L, 
667L, 1126L, 919L), Y = c(807, 518, 724, 221, 182, 807, 604, 
384, 142, 728)), .Names = c("X", "Y"), row.names = c(NA, 10L), class = "data.frame")

我只想找出连接所有这些点的最短路径，并返回它的总距离。没有其他条件：每个点都可以连接到任何其他点，没有特定的开始或结束点，没有权重等......我发现了很多关于 igraph 包的主题，但我不知道如何提供我的数据进去。也发现了这个，但不是在 R 语言中。也许一个“蛮力”脚本会很好，因为我得到的分数不超过 20 分。谢谢

4

1 回答 1

9

正如评论所暗示的，您的问题与旅行推销员问题有关。它实际上是哈密顿路径的一个例子（一条访问每个节点一次的路径，但不会在它开始的地方结束）。如您所料，在 R 中已经有一个包：TSP. 看到这个和这个。

旅行商问题非常难以准确解决（在合理的时间内），因此大多数算法都是近似的和迭代的：它们使用“可能”产生短路径的算法从随机起点探索各种路径，但不一定是绝对最短的。

在您的示例中，只有 10 个节点，可以执行穷举（蛮力）搜索。这很有用，因为我们可以将近似 TSP 解决方案与精确解决方案进行比较。但是请注意，即使只有 10 个节点，蛮力方法也需要检查约 360 万条路径，大约需要 2 分钟。对于 20 个节点，路径数约为 2.5 × 10 18。

# Hamiltonian Path via traveling salesman problem
library(TSP)
tsp <- TSP(dist(df))
tsp <- insert_dummy(tsp, label = "cut")
tour <- solve_TSP(tsp, method="2-opt", control=list(rep=10))
path.tsp <- unname(cut_tour(tour, "cut"))
path.tsp
#  [1]  6  3  5  4  8  2  1 10  7  9

# Hamiltonian Path via brute force
library(combinat)
M  <- as.matrix(dist(df))     # distance matrix
paths   <- permn(nrow(M))     # all possible paths (~ 3.6e6 !!!)
lengths <- sapply(paths,function(p)sum(M[cbind(p[-nrow(M)],p[-1])]))
path.bf <- paths[[which.min(lengths)]]
path.bf
#  [1]  9  7 10  1  2  8  4  5  3  6

# plot the results
par(mfrow=c(1,2))
plot(Y~X,df[s.path.tsp,],type="b",asp=1)
plot(Y~X,df[s.path.bf,],type="b",asp=1)

要将 TSP 问题转换为哈密顿路径问题，我们必须添加一个“虚拟顶点”，它与每个其他节点的距离为 0（参见上面引用的小插图）。然后，哈密顿路径是从虚拟节点之后的节点开始到虚拟节点之前的节点结束的 TSP 路径。

请注意，蛮力和 TSP 解决方案标识完全相同的路径，但顺序相反。这是因为，当然，两条路径具有相同的长度。

于 2014-12-09T18:53:03.180 回答