r - 以优化的方式将现有二维点移动到新生成的二维点

Question

我正在尝试解决一个问题，我有一些现有的点 (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 作为语言。

谢谢

Answer 1

首先，您最好使用 dist 函数来生成 summationMatrix(名称 summationMatrix 恕我直言，太可怕了，我会给它起个名字像 dist.matrix 或 dist.mat)。

其次，你需要的叫Hungarian algorithm .