在两个集合之间映射元素的算法

Question

我有两组向量，A 组和 B 组。假设 A 组包含 100 个向量，B 组包含 50 个向量。我有自己的方法来测量任意两个向量之间的距离。目标是将集合 A 中的向量映射到集合 B 中的向量，其距离在特定阈值内。现在，如果两个向量之间的距离不在特定阈值内，那么它们就不会配对。映射是一对一的，即集合 A 中的一个向量只能映射到集合 B 中的一个向量，反之亦然。

因此，最终可能会发生这样的情况，即集合 A 中的 40 个向量映射到集合 B 中的 40 个向量。因此，集合 A 中的 60 个向量未与集合 B 中的任何向量配对。因此，集合 B 中的 10 个向量是也未配对。

现在，如果我将集合 A 中的向量标记为 A1、A2、A3 ... A100 并将集合 B 中的向量标记为 B1、B2、B3 ... 等等，那么最有效的迭代方式是什么两组并进行配对。

如果需要额外说明，请告诉我。

Answer 1

您需要做的是首先查看 A 中的哪些向量可以与 B 中的哪些向量配对。这是用 O(n^2) 复杂度完成的，并将创建一个二部图 - 您有两个顶点分区 - A 中的向量和 B 中的向量，当且仅当 A 中的向量可以与 B 中的向量配对时，你才有一条边。构建图形后，您需要找到最大二分匹配，这通常使用流来完成。看看here例如。我个人使用Dinitz流的算法。

希望这对您有所帮助。