在python中，如何高效地从一组不同的点到另一组点的每个点找到最近的点

Question

我有这个密码

import random as rand


W = 2
H = 2
n_riders = 10
n_drivers = 20
riders_coords = []
drivers_coords = []
for n in range(n_riders):
    x = rand.uniform(-1,1)*W
    y = rand.uniform(-1,1)*H
    riders_coords.append((x, y))
for n in range(n_drivers):
    x = rand.uniform(-1,1)*W
    y = rand.uniform(-1,1)*H
    drivers_coords.append((x, y))
print(riders_coords)
print(drivers_coords)

我想找到一种方法，将每个车手与最近的车手配对（欧几里得距离），考虑到单个车手只能分配给单个车手。目标是找到使总距离最小的配对。如果n_骑手<；=n_司机。 有谁知道一个简单的方法来实现这一点，还是我必须从头开始绘制voronoi多边形

Answer 1

您的问题称为欧几里德赋值问题，或者欧几里德二部匹配问题。这个问题已经在学术上进行了研究，有一些已知的算法，但除了在学术论文中，我没有找到任何关于它们的信息：

• Vaidya (1989)描述了一种在O(n^2.5 log n)时间内运行的算法
• Agarwal, Efrat & Sharir (1999)描述了在O(n^(2 + ε))时间内为任意小的ε运行的一个
• Agarwal & Varadarajan (2004)描述了一种启发式算法，该算法在O(n^(1 + ε))时间内运行，并在真实最小值的常数因子内找到与期望权重匹配的结果

通过搜索文献，您可能会找到更多已发布的算法或启发法