Python - ближайший минимум

Question

У меня есть 2 матрицы с 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;

Следующий шаг - связать начальную точку с конечной точкой, и пересечения НЕ должно быть, то есть сопоставление один к одному.

Я думал сделать это с помощью целочисленного программирования (используя это ).Поэтому, если m [i] [j] является элементом матрицы 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 (линейное программирование).

У Сципи простой решатель назначений ( ссылка ).Однако это не очень быстрая реализация: хороший решатель LP быстрее ( link ).

Answer 2

ОК, я думаю, это то, что вы спрашиваете. Следующий код будет проходить через каждую координату в p1 и вычислять расстояния с каждой координатой в p2 (функция closest_node была от здесь ), а затем возвращать ближайшую координату в массив nearest & соответствующий элемент удален из p2

Будет соответствие 1: 1 между 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)