最小化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（n ）工作。

在SciPy的，可以发现在scipy.optimize.linear_sum_assignment