找到最接近的一组向量，每组中一个向量？

Question

我有k组向量。这些向量的长度均相同m。这些集合的长度并不相同，但假设每个集合的平均长度为n 个向量。我需要找到彼此之间距离最小（L2 范数）的向量组（每组一个）。这类似于“最接近的对”问题，但这只是 2 组，而我有k组。

\n

na\xc3\xafve 方法是交叉连接所有值并搜索所有O(n^k)距离。有更好的方法/算法吗？

\n

Example  \nSet A [[0.1, 0.2], [0.3, 0.4], [0.5, 0.6]]  \nSet B [[0.5, 0.9], [0.1, 0.3], [0.9, 0.1]]  \nSet C [[0.2, 0.2], [0.8, 0.4], [0.5, 0.1]]  \nResult - A [0.1, 0.2], B [0.1, 0.3], C [0.2, 0.2] with L2 distance 0.14  \n\n

\n

Answer 1

我想我对此有一个有趣的启发。

将每个O(n k)向量的第一个元素放入数组中v[1]。

将每个O(n k)向量的第二个元素放入一个数组中v[2]。

...

将m每个O(n k)向量的第 - 个元素放入一个数组中v[m]。

此步骤的总时间复杂度：O(m n k)。

将 的所有元素对放入v[1]一个数组中p[1]，并按 中元素对的平方差对其进行排序O((n k)^2 log(n k))。启动一个计数器cnt: = 0。迭代p[1]并查看每对的第二个元素。x每当您在位置看到一个新元素时i，保存一个映射map[1][x]: = i，将其放入数组中men[1]，递增cnt并放入1数组cnt的第一个位置women[x]。最后，men[1]应该有k要素。

将 的所有元素对放入v[2]一个数组中p[2]，并按 中元素对的平方差对其进行排序O((n k)^2 log(n k))。启动一个计数器cnt: = 0。迭代p[2]并查看每对的第二个元素。每当你在位置 i 看到一个新元素 x 时，保存一个映射map[2][x]: = i，将其放入数组中men[2]，递增cnt并放入2数组cnt的第 - 个位置women[x]。最后，men[2]应该有k要素。

...

将 的所有元素对放入v[m]一个数组中p[m]，并按 中元素对的平方差对其进行排序O((n k)^2 log(n k))。启动一个计数器cnt: = 0。迭代p[m]并查看每对的第二个元素。x每当您在位置看到一个新元素时i，保存一个映射map[m][x]: = i，将其放入数组中men[m]，递增cnt并放入m数组cnt的第一个位置women[x]。最后，men[m]应该有k要素。

此步骤的总时间复杂度：O(m (n k)^2 log(n k) )。

m考虑一个男性和女性的稳定婚姻问题k，其中男性的偏好i由先前计算的数组描述men[i]，女性的偏好j由先前计算的数组描述women[j]。使用 Gale-Shapley 算法求解该问题，并使用map之前计算的结果来查找数组中与每个匹配项关联的对p。将每一对放入一个数组中match。

您可以使用match它在线性时间内根据其大小获得良好的矢量选择。

此步骤的总时间复杂度：O(m k)。

最终时间复杂度：O(m (n k)^2 log(n k) )