Python最接近最小值

2021-08-02 15:57:30 发布

您现在位置:Python中文网/ 问答频道 /正文

我有两个矩阵都有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;

enter image description here

下一步是把一个起点和一个终点连接起来,不应该有任何交点,也就是一对一的映射。你知道吗

我想通过整数编程(使用this)来实现。 如果m[i][j]是矩阵NxN的一个元素,我发现了这些约束

enter image description here

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

你认为这是一条好的道路吗? 最后一个问题似乎没有得到重视,因为我没有揭露我已经做了什么。你知道吗

就是这样。你知道吗

2条回答
网友
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

这些问题可以用专门的解算器来解决,也可以用线性规划来表示。你知道吗

Scipy有一个简单的赋值解算器(link)。然而,这并不是一个很快的实现:一个好的LP解算器更快(link)。你知道吗

网友
2楼 ·

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

p1&;nearestp1[0]映射到nearest[0]等之间将有1对1的对应关系。。你知道吗

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)

相关问题