Минимизировать общее расстояние между двумя наборами точек в Python

Question

Учитывая два набора точек в n-мерном пространстве, как можно сопоставить точки от одного набора к другому, так что каждая точка используется только один раз, а общее эвклидовое расстояние между пары точек минимизированы?

Например,

import matplotlib.pyplot as plt 
import numpy as np 

# create six points in 2d space; the first three belong to set "A" and the 
# second three belong to set "B" 
x = [1, 2, 3, 1.8, 1.9, 3.4] 
y = [2, 3, 1, 2.6, 3.4, 0.4] 

colors = ['red'] * 3 + ['blue'] * 3 

plt.scatter(x, y, c=colors) 
plt.show() 

Таким образом, в приведенном выше примере, цель будет отображать каждую красную точку на синюю точку, так что каждая синяя точка используется только один раз, а сумма расстояний между точками минимизируется.

я наткнулся this question, который помогает решить первую часть задачи - вычислить расстояние между всеми парами точек через множеств с помощью функции scipy.spatial.distance.cdist().

Оттуда я мог бы, вероятно, проверить каждую перестановку отдельных элементов из каждой строки и найти минимум.

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

Answer 1

Пример присвоения (отображения) элементов одного множества в точках к элементам другого множества точек, таких, что сумма евклидово расстояние минимизируется.

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial.distance import cdist 
from scipy.optimize import linear_sum_assignment 

np.random.seed(100) 

points1 = np.array([(x, y) for x in np.linspace(-1,1,7) for y in np.linspace(-1,1,7)]) 
N = points1.shape[0] 
points2 = 2*np.random.rand(N,2)-1 

C = cdist(points1, points2) 

_, assigment = linear_sum_assignment(C) 

plt.plot(points1[:,0], points1[:,1],'bo', markersize = 10) 
plt.plot(points2[:,0], points2[:,1],'rs', markersize = 7) 
for p in range(N): 
    plt.plot([points1[p,0], points2[assigment[p],0]], [points1[p,1], points2[assigment[p],1]], 'k') 
plt.xlim(-1.1,1.1) 
plt.ylim(-1.1,1.1) 
plt.axes().set_aspect('equal') 

Answer 2

Там в известном алгоритме для этого, The Hungarian Method For Assignment, который работает во время O (п).

В SciPy, вы можете найти реализацию в scipy.optimize.linear_sum_assignment