algorithm - 找到最接近另一组的点集

Question

我有两个集合，A 和 B，N 和M 分别指向R^n。我知道 N <M 总是。

P 和Q 两点之间的距离用d( P,Q )。由于问题是通用的，因此该距离可以是任何函数(例如欧氏距离)。

我想找到 B 最接近 A 的子集。从数学上讲，我想找到 B 的子集 C，大​​小为 N 到 A 的最小全局距离。 A 和 C 之间的全局距离由下式给出

D(A,C) = min([sum(d(P_i,Q_i),i=1,N) with P_i in A and Q_i in C* for C* in Permutations of C]) 

我一直在思考这个问题，我做了一个算法，它获得了局部最优，但不一定是最优的:

第 1 步)找到 A 在 B 中每个点的最近点。如果没有重复的点，我找到最优子集并完成算法。但是，如果有重复的点，则转到步骤2。

Step 2) 比较它们的距离(当然我比较的是点与点之间的距离是同一个最近点)。距离最小的点保留之前找到的点，其他点将它们的所需点更改为尚未为另一个点选择的“下一个”最近点。

步骤 3) 检查所有点是否不同。如果是，请完成。如果不是，返回步骤 2。

有什么想法吗？尝试所有组合并不是一个好的组合(我应该计算 M!/(M-N)! 全局距离)

Answer 1

如果 M = N，则此问题可以表述为二分图中的最小权重完美匹配，或者换句话说，分配问题。解决分配问题的一个著名方法是 Hungarian algorithm .

为了使匈牙利算法适用于 N < M 的情况，您可以使用 (M-N) 个附加元素扩展集合 A(每个元素与 B 的所有元素的距离为零) ).