正如标题所说:我想计算相邻时间点之间的距离，并找到所有时间点的 n 最短路径。
我在下面发布了一个例子。在这个例子中，有 2 个清晰的区域(在 3D 空间中)，其中的点被定位。在每个区域内，我们有多个时间点。我想在执行时间点排序的同时计算 T1 --> T2 --> ... --> T8 之间的距离。我最终将其视为某种树，我们最初从 T1 的第一个点分支到 T2 的 2 个(或更多)点，然后从每个 T2 到每个 T3，等等。一旦构建了树，我们就可以计算每条路径从开始到结束的距离，并返回距离最小的顶部 n 路径。简而言之，这里的目标是将每个 T1 节点与其各自的最短路径连接起来。也许有更有效或更好的方法来做到这一点。
示例数据:
> example
Timepoint Centre.int.X Centre.int.Y Centre.int.Z
FOV4.Beads.T1.C2 T1 5.102 28.529 0.789
FOV4.Beads.T1.C2.1 T1 37.904 50.845 0.837
FOV4.Beads.T2.C2 T2 37.905 50.843 1.022
FOV4.Beads.T2.C2.1 T2 5.083 28.491 0.972
FOV4.Beads.T4.C2 T4 37.925 50.851 0.858
FOV4.Beads.T4.C2.1 T4 5.074 28.479 0.785
FOV4.Beads.T5.C2 T5 37.908 50.847 0.977
FOV4.Beads.T5.C2.1 T5 5.102 28.475 0.942
FOV4.Beads.T6.C2 T6 5.114 28.515 0.643
FOV4.Beads.T6.C2.1 T6 37.927 50.869 0.653
FOV4.Beads.T7.C2 T7 37.930 50.875 0.614
FOV4.Beads.T7.C2.1 T7 5.132 28.525 0.579
FOV4.Beads.T8.C2 T8 4.933 28.674 0.800
FOV4.Beads.T8.C2.1 T8 37.918 50.816 0.800
此 data.frame 生成一个 3D 散点图，如下所示:
生成上述图的基线代码发布如下:
require(scatterplot3d)
with(example, {
s3d <- scatterplot3d(Centre.int.X, Centre.int.Y, Centre.int.Z,
pch=19,
cex.symbols=2,
col.axis="grey", col.grid="lightblue",
angle=45,
xlab="X",
ylab="Y",
zlab="Z")
})
这是一个相对干净的例子，但我的一些数据非常困惑，这就是为什么我试图避免聚类方法(例如 k-means、dbscan 等)。任何帮助，将不胜感激!
编辑:添加结构细节。
structure(list(Timepoint = structure(c(1L, 1L, 2L, 2L, 4L, 4L,
5L, 5L, 6L, 6L, 7L, 7L, 8L, 8L), .Label = c("T1", "T2", "T3",
"T4", "T5", "T6", "T7", "T8"), class = "factor"), Centre.int.X = c(5.102,
37.904, 37.905, 5.083, 37.925, 5.074, 37.908, 5.102, 5.114, 37.927,
37.93, 5.132, 4.933, 37.918), Centre.int.Y = c(28.529, 50.845,
50.843, 28.491, 50.851, 28.479, 50.847, 28.475, 28.515, 50.869,
50.875, 28.525, 28.674, 50.816), Centre.int.Z = c(0.789, 0.837,
1.022, 0.972, 0.858, 0.785, 0.977, 0.942, 0.643, 0.653, 0.614,
0.579, 0.8, 0.8)), .Names = c("Timepoint", "Centre.int.X", "Centre.int.Y",
"Centre.int.Z"), class = "data.frame", row.names = c("FOV4.Beads.T1.C2",
"FOV4.Beads.T1.C2.1", "FOV4.Beads.T2.C2", "FOV4.Beads.T2.C2.1",
"FOV4.Beads.T4.C2", "FOV4.Beads.T4.C2.1", "FOV4.Beads.T5.C2",
"FOV4.Beads.T5.C2.1", "FOV4.Beads.T6.C2", "FOV4.Beads.T6.C2.1",
"FOV4.Beads.T7.C2", "FOV4.Beads.T7.C2.1", "FOV4.Beads.T8.C2",
"FOV4.Beads.T8.C2.1"))
最佳答案
不是很优雅，但它可以找到最短路径。
distance.matrix <- as.matrix(dist(example[,2:4], upper = TRUE, diag = TRUE))
t1s <- grep("T1", rownames(distance.matrix))
paths <- lapply(t1s, function (t) {
path <- rownames(distance.matrix)[t]
distance <- NULL
for (i in c(2,4:8))
{
next.nodes <- grep(paste0("T", i), rownames(distance.matrix))
next.t <- names(which.min(distance.matrix[t,next.nodes]))
path <- c(path, next.t)
distance <- sum(distance, distance.matrix[t,next.t])
t <- next.t
}
output <- list(path, distance)
names(output) <- c("Path", "Total Distance")
return(output)
})
编辑:切断一些不需要的行。
关于r - 计算相邻时间点的点之间的距离并找到所有时间点的 `n` 最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45807362/