Python -最近的最小值

Question

我有两个矩阵，都有Nx2元素。任何值都是带有8-10小数的浮点数，它们分别表示点的'x‘和'y’。

对于第一个数组中的任何元素偶(x，y) (x在第一列，而y在第二列)，我需要在第二列中找到最近的点。在任何循环中，一旦找到，我需要从第二个数组中删除该值。

最后，我的主要目标是获得最优解，以便在第一个数组的任何元素与第二个数组的一个元素之间进行一对一的映射，从而满足最近的value子句。

我创建了一个NxN矩阵，其中计算了从第一个数组的任意点到第二个数组的任意点的距离，通过

scipy.spatial.distance.cdist

代码：

def find_nearest(X_start, X_end):
    mat = scipy.spatial.distance.cdist(X_start, X_end, metric='euclidean')
    new_df = pd.DataFrame(mat)
    return new_df;

​

​

下一步是将起点与终点结合起来，不应该有任何交集，即一对一的映射。

我想通过Integer编程(使用这)来实现它。因此，如果mi是矩阵NxN的一个元素，我发现了这些约束。

​

​

问题是，我不知道如何编写目标函数，所以我确定是否需要添加与其相关的任何其他约束。

你认为这是一条好的道路吗？最后一个问题似乎不被欣赏，因为我没有揭露我已经做过的事情。

所以就是这样了。

Answer 1

这被称为赋值问题。

   min sum((i,j), dist[i,j]*x[i,j])
   subject to
       sum(i, x[i,j]) = 1 for all j
       sum(j, x[i,j]) = 1 for all i
       x[i,j] in {0,1}

哪里

 i = 1..n is an element of the first matrix
 j = 1..n is an element of the second matrix
 dist[i,j] is a distance matrix

这些问题可以用专门的求解者来解决，也可以用线性规划问题来表示。

席比有一个简单的任务求解器(链接)。然而，这不是一个非常快速的实现:一个好的LP解决程序更快(链接)。

Answer 2

好吧，我想这就是你要问的。下面的代码将遍历p1中的每个坐标&计算p2中每个坐标的距离( closest_node函数来自这里)，然后将最接近的坐标返回到nearest数组，相应的元素从p2中删除

p1和nearest之间将有1到1的通信，例如，p1[0]映射到nearest[0]等。

import numpy as np

def closest_node(node, nodes):
    dist_2 = np.sum((nodes - node)**2, axis=1)
    return np.argmin(dist_2)

p1 = np.random.rand(10, 2)
p2 = np.random.rand(10, 2)
nearest = []

for coord in p1:
    near = closest_node(coord, p2)
    nearest.append(p2[near])
    p2 = np.delete(p2, near, 0)

nearest = np.array(nearest)