从X,Y坐标找到最短路径(起始≠end)

Question

我有一个数据框,其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分..谢谢

Answer 1

正如评论所示,您的问题与旅行商问题有关.它实际上是哈密尔顿路径的一个例子(一个路径,它访问每个节点一次,但不会在它开始的地方结束).正如您所料,在R中已有一个包装:TSP.看到这个和这个.

TSP问题是极为困难的解决恰好(在合理的时间量),所以大部分的算法是近似的和迭代:它们使用的算法即"可能",以产生短的路径的随机起点探索各种路径,但不一定是绝对最短的.

在您的示例中,只有10个节点,可以执行详尽(强力)搜索.这很有用,因为我们可以将近似TSP解决方案与精确解决方案进行比较.但请注意,即使只有10个节点,强力方法也需要检查约360万个路径,大约需要2分钟.对于20个节点,路径数量为~2.5×10 ¹⁸.

# 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解决方案确定完全相同的路径,但顺序相反.这是因为,当然,两条路径的长度相同.