基于两个坐标之间的最近距离，对矩阵进行排序

Question

如何根据两个坐标之间的最近距离对矩阵进行排序？

例如，我有这个矩阵：

> x
      [,1] [,2]
[1,]    1    1
[2,]    3    9
[3,]    2    6
[4,]    2    8

我希望矩阵的第一行可以作为一个初始坐标。在手动计算两个坐标之间的距离后，我发现x [1，]与x [3，]之间的距离最近。然后，x [3，]与x [4，]之间的距离最近。x [4，]与x [2，]之间的距离最近。因此，排序后的矩阵如下：

    [,1] [,2]
[1,]    1    1
[2,]    2    6
[3,]    2    8
[4,]    3    9

我尝试编写以下的 R 代码，但它没有起作用。

closest.pair <- c(NA,NA)                  
closest.distance <- Inf                    
for (i in 1:(n-1))                         
  for (j in (i+1):n) {
    dist <- sum((houses[i,]-houses[j,])^2) 
    if (dist<closest.distance) {           
      closest.pair <- c(i,j)               
    }
    print(houses[closest.pair,])
  }

- Edelws

---

如果例如 x 改为 matrix(c(1,1,2,2,1,2,6,8),ncol=2)，结果会在第一行和第二行之间来回移动，还是我们把最接近第二行但不是第一行的一对放在第三行？ - Lamia

我认为你应该看一下旅行商问题。 - KarlP

Answer 1

你可以使用如下的for循环：

D=`diag<-`(as.matrix(dist(x)),NA)# Create the distance matrix, and give the diagonals NA values.

然后运行一个for循环

x[c(i<-1,sapply(1:(nrow(x)-1),function(j)i<<-which.min(D[i,]))),]

     [,1] [,2]
[1,]    1    1
[2,]    2    6
[3,]    2    8
[4,]    3    9

这个for循环可能看起来有点奇怪！看一下：

m=c()
i=1
for(j in 1:(nrow(x)-1)){
i= which.min(D[i,])
m=c(m,i)
}
x[c(1,m),]
     [,1] [,2]
[1,]    1    1
[2,]    2    6
[3,]    2    8
[4,]    3    9

你也可以使用Reduce

x[Reduce(function(i,j)which.min(D[,i]),1:(nrow(x)-1),1,,T),]
     [,1] [,2]
[1,]    1    1
[2,]    2    6
[3,]    2    8
[4,]    3    9

- Onyambu

Answer 2

这里是使用循环的可能解决方案：

## We determine the minimum distance between the coordinates at the current index cur 
## and those at the remaining indexes ind
cur = 1;    
ind = c(2:nrow(x));
## We put our resulting sorted indexes in sorted
sorted = 1;
while(length(ind)>=2){
    pos = ind[which.min(rowSums((x[cur,]-x[ind,])^2))];
    ## At each iteration we remove the newly identified pos from the indexes in ind
    ## and consider it as the new current position to look at
    ind = setdiff(ind,pos);
    cur = pos;
    sorted = c(sorted,pos)}
sorted = c(sorted,ind)

res = x[sorted,];

     [,1] [,2]
[1,]    1    1
[2,]    2    6
[3,]    2    8
[4,]    3    9

- Lamia