r - 从 2 个向量中找到最佳匹配的成对点

Question

我有 2 个列表，其中包含点的 X、Y 坐标。
列表 1 比列表 2 包含更多的点。

任务是以最小化整体欧几里德距离的方式找到点对。

我有一个工作代码，但我不知道这是否是最好的方法，我想得到提示我可以改进结果(找到最小值的更好算法)或速度，因为每个列表大约有 2000 个元素.

实现样本向量中的轮次也是为了获得具有相同距离的点。
使用“rdist”函数，所有距离都在“距离”中生成。比矩阵中的最小值用于链接 2 个点(“dist_min”)。这 2 个点的所有距离现在都被 NA 替换，循环继续搜索下一个最小值，直到列表 2 的所有点都有一个来自列表 1 的点。
最后，我添加了一个可视化图。

require(fields)

set.seed(1)
x1y1.data <- matrix(round(runif(200*2),2), ncol = 2)   # generate 1st set of points 
x2y2.data <- matrix(round(runif(100*2),2), ncol = 2)   # generate 2nd set of points

distances <- rdist(x1y1.data, x2y2.data)
dist_min <- matrix(data=NA,nrow=ncol(distances),ncol=7)   # prepare resulting vector with 7 columns

for(i in 1:ncol(distances)) 
{
    inds <- which(distances == min(distances,na.rm = TRUE), arr.ind=TRUE)

    dist_min[i,1] <- inds[1,1]              # row of point(use 1st element of inds if points have same distance)
    dist_min[i,2] <- inds[1,2]              # column of point (use 1st element of inds if points have same distance)
    dist_min[i,3] <- distances[inds[1,1],inds[1,2]] # distance of point
    dist_min[i,4] <- x1y1.data[inds[1,1],1]     # X1 ccordinate of 1st point
    dist_min[i,5] <- x1y1.data[inds[1,1],2]     # Y1 coordinate of 1st point
    dist_min[i,6] <- x2y2.data[inds[1,2],1]     # X2 coordinate of 2nd point
    dist_min[i,7] <- x2y2.data[inds[1,2],2]     # Y2 coordinate of 2nd point

    distances[inds[1,1],] <- NA # remove row (fill with NA), where minimum was found
    distances[,inds[1,2]] <- NA # remove column (fill with NA), where minimum was found
}

# plot 1st set of points
# print mean distance as measure for optimization
plot(x1y1.data,col="blue",main="mean of min_distances",sub=mean(dist_min[,3],na.rm=TRUE))       
points(x2y2.data,col="red")                         # plot 2nd set of points
segments(dist_min[,4],dist_min[,5],dist_min[,6],dist_min[,7])   # connect pairwise according found minimal distance

Answer 1

这是组合优化中的一个基本问题，称为 assignment problem .解决分配问题的一种方法是 Hungarian algorithm这是在 R 包线索中实现的:

require(clue)
sol <- solve_LSAP(t(distances))

我们可以验证它优于简单的解决方案:

mean(dist_min[,3])
# [1] 0.05696033
mean(sqrt(
  (x2y2.data[,1] - x1y1.data[sol, 1])^2 +  
    (x2y2.data[,2] - x1y1.data[sol, 2])^2))
#[1] 0.05194625

我们可以构建一个与您的问题类似的图:

plot(x1y1.data,col="blue")       
points(x2y2.data,col="red")
segments(x2y2.data[,1], x2y2.data[,2], x1y1.data[sol, 1], x1y1.data[sol, 2])