1

我有两组向量，集合 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 ... 等等，那么迭代这两个集合的最有效方法是什么并做这个配对。

如果需要进一步说明，请告诉我。

4

1 回答 1

1

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

希望这可以帮助。

于 2012-04-11T06:43:54.197 回答