我正在尝试解决一个问题，我有一些现有的点 (P) 需要移动到由某种方法生成的新位置，比如 (P`)。我想知道是否有一种优化算法可以找到最佳的点映射。
我尝试通过使用点之间的最小距离在循环中选择最佳点来绘制 map ，但最后一个点以最差的方式结束。我们如何确定最佳映射？
我们没有尝试最佳时间或空间复杂度，因为我们只有少数几个点可以使用。以下是我们目前所拥有的。
getMapping <- function(originalX, originalY, newX, newY)
{
#Maps original index to new index
dimemsion <- length(originalX)
#this matrix will hold distance of each original point from each of the new points
dist.matrix <- matrix(nrow = dimemsion, ncol= dimemsion)
#this is a brute force method
for(i in 1:dimemsion) # i traverses over original data points
{
for(j in 1:dimemsion) # j traverses over new data points
{
distance <- sqrt((originalY[i] - newY[j])^2 + (originalX[i] - newX[j])^2)
dist.matrix[i,j] = distance
}
}
#Best way to find mapping ?????
..... Not sure how to do it right now
return(dist.matrix)
}
#Use Case 1
originalX = c( 1, 2, 3, 4, 5, 6)
originalY = c( 1, 2, 3, 4, 5, 6)
newX = c( 1, 1, 3, 4, 5, 6)
newY = c( 1, 1, 4, 3, 2, 1)
print(getMapping(originalX, originalY, newX , newY))
如何从求和矩阵中找到最佳组合？或者解决此问题的任何算法/想法将不胜感激。我们在这里使用 R 作为语言。
谢谢
最佳答案
首先，您最好使用 dist 函数来生成 summationMatrix(名称 summationMatrix 恕我直言，太可怕了，我会给它起个名字像 dist.matrix 或 dist.mat)。
其次，你需要的叫Hungarian algorithm .
关于r - 以优化的方式将现有二维点移动到新生成的二维点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38108509/