python - 找到最小距离为 `n` 的 `d` 个不同向量的子集

Question

我有一组向量 V (比如像 [1,2,...64] 这样的 64 维向量)。来自矢量集 V , 我想找到 n 的子集( n 是任意数 > 0)个不同的向量，V1 ， 在哪里

子集中的任意两个向量 V1最小距离为 d并且;

对于任何元素 w在向量集中V ，存在一个元素 w'在子集中 V1可以达到w距离小于 d .

确定 n 的一个子集的有效算法是什么？不同的向量，其中 n 的值是最低限度？
距离可以是欧几里得距离或余弦相似度(当然两者不能混合)。

Answer 1

让我们这样思考您的问题:您在 64 维空间中有一组球，每个球的半径为 d，代表每个输入向量周围的空间。 (注意，我假设“距离”是指 Euclidean distance )。
现在，您想要找到将覆盖每个原始点的最小球子集，这意味着您需要每个点至少位于子集中的一个球内，并且附加限制是覆盖中的球必须具有中心距离 d。
如果没有这个额外的限制，你就有一个很难但经过充分研究的实例，名为 Geometric set cover ，这又是更著名的 Set cover problem 的特例。 .从直觉上看，附加限制使问题变得更加困难，但我没有证据证明这一点。
坏消息是，(几何)集合覆盖问题是 NP-hard 问题，这意味着如果原始集合中可能有很多点，您将无法快速找到确切的最小值。
好消息是，有一些很好的算法可以找到近似解，这会给你一个不一定尽可能小的集合，但它接近于尽可能小的集合。
这是一个简单的贪心算法的 Python 代码，它并不总是能找到一个最小大小的覆盖，但总是会返回一个有效的覆盖:

def greedy(V, d):
    cover = set()
    uncovered = set(V)
    # invariant: all(distance(x,y) > d for x in cover for y in uncovered)
    while uncovered:
        x = uncovered.pop()
        cover.add(x)
        uncovered = {y for y in uncovered if distance(x,y) > d}

请注意，您可以通过替换 uncovered.pop() 使这个贪婪的解决方案更好一点。调用更明智的选择，例如选择一个可以“覆盖”最多剩余点数的向量。