Python

Question

我有 2 个矩阵，都包含 Nx2 个元素。任何值都是一个带有 8-10 位小数的浮点数，它们分别代表一个点的 'x' 和 'y'。

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

最后，我的主要 objective 将获得最佳解决方案，以便第一个数组的任何元素与第二个数组的一个元素之间存在一对一的映射，以便满足最接近的价值条款。

我创建了一个 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;

下一步是将起点和终点耦合起来，并且不能有任何交集，这是一对一的映射。

我想通过整数编程来实现（使用 this）。所以如果 m[i][j] 是矩阵 NxN 的一个元素，我发现那些约束

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

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

原来如此。

Answer 1

好的，我想这就是你要问的。以下代码将遍历 p1 中的每个坐标并计算与 p2 中每个坐标的距离（closest_node 函数来自 here）然后 return最接近 nearest 数组的坐标 & 从 p2

中删除相应的元素

p1 和 nearest 之间会有一对一的对应关系，即 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)

Answer 2

这称为分配问题。

   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（线性规划）问题。

Scipy 有一个简单的赋值求解器 (link). This is not a very fast implementation however: a good LP solver is faster (link)。

Python - 最接近的最小值

Python - Closest Minimum

scipy

integer-programming