从X，Y坐标中找到最短路径(开始≠结束) [英] Find shortest path from X,Y coordinates (with start ≠ end)

问题描述

我有一个数据点，其点的X和Y坐标是这样的:

I have a dataframe with X and Y coordinates of points like this:

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分. 谢谢

I just want to find out the shortest path connecting all these points, and also return its total distance. There are no other conditions: every point can be connected to any other, no specific point to start or end, no weights, etc... I found lots of topics about igraph package but i can't figure out how to feed my data into it. Found also this but not in R language. maybe a "brute force" script would be fine since i've got no more than 20 points.. Thanks

推荐答案

正如评论所建议的，您的问题与旅行推销员问题" 相关.实际上，这是哈密顿路径的示例(该路径仅访问每个节点一次，但在开始时未结束).如您所料，R中已经有一个软件包:TSP.参见此和

As the comments suggest, your question is related to the Traveling Salesman Problem. It is in fact an example of a Hamiltonian path (a path which visits each node once, but does not end where it started). As you might expect, in R there's already a package for that: TSP. See this and this.

旅行推销员问题"很难(在合理的时间内)精确解决，因此大多数算法都是近似和迭代的:它们使用可能"产生的算法从随机起点探索各种路径.路径短，但不一定绝对最短.

The Traveling Salesman Problem is extremely difficult to solve exactly (in a reasonable amount of time), so most of the algorithms are approximate and iterative: they explore various paths from a random starting point using algorithms which are "likely" to produce short paths, but not necessarily the absolute shortest.

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

In your example, with only 10 nodes, it is possible to execute an exhaustive (brute force) search. This is useful because we can compare the approximate TSP solution with the exact solution. Note however that even with only 10 nodes, the brute force approach requires examination of ~3.6 million paths, and takes about 2 minutes. With 20 nodes the number of paths is ~ 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路径.

To convert a TSP problem into a Hamiltonian Path problem we have to add a "dummy vertex" which is a distance 0 from every other node (see the vignette referenced above). Then, the Hamiltonian Path is the TSP path starting from the node right after the dummy and ending at the node right before the dummy.

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

Notice that the brute force and the TSP solution identify the exact same path, but in the reverse order. This is because, of course, both paths have the same length.

这篇关于从X，Y坐标中找到最短路径(开始≠结束)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！