我有两个矩阵都带有 Nx2 元素。任何值都是一个带有 8-10 位小数的浮点数,它们分别代表一个点的“x”和“y”。
对于第一个数组中的任何元素对 (x, y)(x 在第一列中,而 y 在第二列中),我需要在第二个数组中找到最近的点。在任何循环中,一旦找到,我需要从第二个数组中删除该值。
最后,我的主要目标是获得最佳解决方案,以便第一个数组的任何元素与第二个数组的只有一个元素之间存在一对一映射,从而满足最接近的值子句。
我创建了一个 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 的一个元素,我发现这些约束
问题是我不知道如何编写目标函数,所以我确定是否需要添加任何其他与之相关的约束。
你认为这是一条很好的道路吗?最后一个问题似乎不受欢迎,因为我没有公开我已经做过的事情。
所以在这里。
这称为分配问题。
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(线性规划)问题。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句