如何计算距离矩阵中唯一方法的总和

iatowks 发表于 Dev

Iatowks

我有一个由3个点的经度和纬度表示的空间数据框：

myData <- structure(list(lng = c(-37.06852042, -37.07473406, -37.07683313
), lat = c(-11.01471746, -11.02468103, -11.02806217)), .Names = c("lng", 
                                                                  "lat"), row.names = c(NA, 3L), class = "data.frame")

接下来，我使用geosphere软件包获取点的距离矩阵（以米为单位，将其转换为km）：

> m <- round(distm(myData)/1000,2)
> rownames(m) <- c("A", "B", "C")
> colnames(m) <- c("A", "B", "C")
> m
     A    B    C
A 0.00 1.30 1.74
B 1.30 0.00 0.44
C 1.74 0.44 0.00

鉴于这是一个距离矩阵，我有6种前往A，B和C的方法（例如A-> B-> C，C-> A> -B等），我想从中提取一些信息就像最小距离，中值距离和最大距离一样。

为了说明这一点，我手动计算了示例的所有可能方式：

ways <- c(abc <- 1.3 + 0.44,
             acb <- 1.74 + 0.44,
             bac <- 1.3 + 1.74,
             bca <- 0.44 + 1.74,
             cab <- 1.74 + 1.3,
             cba <- 0.44 + 1.3)
> min(ways)
[1] 1.74
> median(ways)
[1] 2.18
> max(ways)
[1] 3.04

考虑到我将要与10个以上的本地人一起工作并且此问题具有阶乘复杂性，我如何自动执行此任务？

理查德·安伯勒

我编写了一个名为trotter的程序包，该程序包将整数映射到不同的排列类型（排列，组合和其他）。对于此问题，您似乎对位置的排列感兴趣。包中的对象之一是使用函数创建的置换伪向量ppv。

首先安装“猪蹄”：

install.packages("trotter")

然后，您的任务的自动化版本可能类似于：

library(geosphere)
myData <- data.frame(
  lng = c(-37.06852042, -37.07473406, -37.07683313), 
  lat = c(-11.01471746, -11.02468103, -11.02806217)
)

m <- round(distm(myData) / 1000, 2)

locations <- c("A", "B", "C")
rownames(m) <- colnames(m) <- locations

library(trotter)

perms <- ppv(k = length(locations), items = locations)
ways <- c()

for (i in 1:length(perms)) {
  perm <- perms[i]
  route <- paste(perm, collapse = "")
  ways[[route]] <- sum(
    sapply(
      1:(length(perm) - 1),
      function(i) m[perm[i], perm[i + 1]]
    )
  )
}

回到R控制台：

> ways
 ABC  ACB  CAB  CBA  BCA  BAC 
1.74 2.18 3.04 1.74 2.18 3.04 
> # What is the minimum route length?
> min(ways)
[1] 1.74
> # Which route (index) is this?
> which.min((ways))
ABC 
  1

请记住，就像您说的那样，您正在处理阶乘复杂性，最终可能会在多个位置运行此蛮力搜索而最终等待一段时间...

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。