8

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

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

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

实施样本向量中的轮次以获得具有相同距离的点。使用“rdist”功能，所有距离都以“距离”生成。比矩阵中的最小值用于链接 2 点（“dist_min”）。这两个点的所有距离现在都被 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

最小距离输出

4

1 回答 1

11

这是组合优化中的一个基本问题，称为分配问题。解决分配问题的一种方法是在 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])

在此处输入图像描述

于 2012-12-20T00:47:31.833 回答