匹配点集的算法

Question

我有两组点 A 和 B，而这些点可以是 2D 或 3D。两组都具有相同的大小 n，这是相当低的 (5 - 20)。

我想知道这些集合的一致性如何。也就是说，理想情况下，我会找到点之间的配对，使得所有欧几里德对距离的总和 d(A,B) 最小。所以

d(A,B) =\sum_{i=1}^n ||A_i - B_i||_2

最终结果用于与其他点集进行比较。所以，例如:

• A = (1,1), (1,2), (1,3)
• B = (1,1), (2,2), (1,3)

会给我 d(A,B) = 1。

• C = (1,1), (2,1), (3,1)
• D = (2,1), (2,2), (3,1)

会给我 d(C,D) = 1.414。

有什么好主意吗？

Answer 1

例如，您可以将问题建模为分配问题 ( Wikipedia link )，您可以在其中定义将点 A_i(来自集合 A)分配给点 B_j(来自集合 B)的成本 C_ij等于它们之间的距离。然后可以使用匈牙利算法 (Wikipedia link) 解决此分配问题。