在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()

在上面的示例中，目标是将每个红点映射到一个蓝点，以使每个蓝点仅使用一次，并且点之间的距离总和最小。

我发现这个问题可以帮助解决问题的第一部分——使用scipy.spatial.distance.cdist()函数计算不同集合中所有点对之间的距离。

从那里开始，我可能会测试每行单个元素的每个排列，并找到最小值。

我考虑的应用涉及三维空间中相当少量的数据点，因此暴力方法可能是可行的，但我想先检查是否有更有效或更优雅的解决方案。

- Keith Hughitt

---

所以这个问题似乎是关于算法的，也就是与语言无关的？ - moooeeeep

这两个集合的大小总是相等的吗？ - moooeeeep

这个问题难道不是线性求和分配问题的一个实例吗？ - Stelios

@moooeeeep 主要关注Python答案，但如果有简单的算法解决方案，我也会感兴趣；至于大小，我对两种情况都很感兴趣 - 一种是集合大小相同，另一种是一个集合比另一个大。任何一个或两个解决方案都将非常有用。 - Keith Hughitt

@Stelios 感谢你向我指出这一点；我之前没有听说过它。看起来它试图解决同样的问题。你觉得你能否发布一个答案，将其应用于两组点的上下文中？ - Keith Hughitt

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')

- Stelios

---

谢谢！我将此标记为解决方案，因为Stelios首先建议使用scipy.optimize.linear_sum_assignment，并提供了详细的代码示例，从开始到结束演示了应用。 - Keith Hughitt

Answer 2

这个问题已经有一个被广泛应用的算法分配问题的匈牙利算法，它的时间复杂度为O(n³)。

在SciPy中，你可以找到一个实现scipy.optimize.linear_sum_assignment的方法。

- Ami Tavory

---

看起来不错！只是为了明确一下——linear_sum_assigment()接受一个_成本_矩阵，这种情况下它将是从scipy.spatial.distance.cdist()输出的结果，而不是原始数据点本身，对吗？ - Keith Hughitt

@KeithHughitt 当然可以。顺便提一下，你可能想看看幻灯片，它们非常易读。 - Ami Tavory