如何计算距离矩阵中找到的唯一方式的总和

Question

我在 space 中有一个由 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 包获取点的距离矩阵（以米为单位，我将其转换为公里）：

> 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 多个本地人一起工作并且这个问题具有阶乘复杂性，我该如何自动执行此任务？

Answer 1

我写了一个名为 trotter 的包，它将整数映射到不同的排列类型（排列、组合等）。对于这个问题，您似乎对位置的排列感兴趣。包中的对象之一是使用函数 ppv.

创建的 排列伪向量

首次安装"trotter":

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

请记住，正如您所说，您正在处理阶乘复杂性，您最终可能会等待一段时间运行这种暴力搜索具有多个位置...

如何计算距离矩阵中找到的唯一方式的总和

How to calculate sum of unique ways found in a distance matrx

r

geospatial