algorithm - 找到彼此最远的k个点的子集

Question

我有一组 N 个点(特别是这个点是二进制字符串)并且对于它们中的每一个我都有一个离散度量(汉明距离)使得给定两个点 i 和 j，Dij 是第 i 个和第 j 个点。我想找到 k 个元素的子集(当然 k < N)，使得这 k 个点之间的距离尽可能大。换句话说，我想要的是找到一种覆盖点空间最大面积的“边界点”。如果 k = 2 答案是微不足道的，因为我可以尝试搜索距离矩阵中最远的两个元素，这些是两个点，但是当 k>2 时我如何概括这个问题？有什么建议吗？这是一个NP难问题？谢谢解答

Answer 1

一个概括是“找到 k 个点，使得这 k 个点中任意两个点之间的最小距离尽可能大”。

不幸的是，我认为这很难，因为我认为如果你能有效地做到这一点，你就能有效地找到派系。假设有人给你一个距离矩阵并要求你找到一个 k-clique。创建另一个矩阵，其中原始矩阵具有无穷大的条目 1 和原始矩阵具有任何有限距离的条目 1000000。现在，新矩阵中的一组 k 个点(其中该组中任意两点之间的最小距离为 1000000)对应于原始矩阵中的一组 k 个点，它们都相互连接 - 一个团。

这个构造没有考虑到点对应于位向量并且它们之间的距离是汉明距离，但我认为可以扩展它来应对这一点。为了证明能够解决原始问题的程序可以用来寻找派系，我需要证明，给定一个邻接矩阵，我可以为每个点构造一个位向量，以便在图中连接点对，等等邻接矩阵中的 1 彼此之间的距离大致为 A，图中未连接的点对彼此之间的距离为 B，其中 A > B。请注意，A 可能非常接近 B。事实上, 三角不等式将强制出现这种情况。一旦我展示了这一点，k 个点彼此之间的距离为 A(因此最小距离为 A，并且距离之和为 k(k-1)A/2)将对应于一个集团，因此找到这样的程序点会找到派系。

为此，我将使用长度为 kn(n-1)/2 的位向量，其中 k 将随 n 增长，因此位向量的长度可能与 O(n^3) 一样多。我可以摆脱这个，因为这仍然只是 n 的多项式。我将每个位向量分成 n(n-1)/2 个字段，每个字段的长度为 k，其中每个字段负责表示两点之间的连接或缺乏连接。我声称存在一组长度为 k 的位向量，因此这些 k 长位向量之间的所有距离大致相同，只是其中两个比其他位向量靠得更近。我还声称存在一组长度为 k 的位向量，因此它们之间的所有距离大致相同，除了其中两个比其他的更远。通过在这两个不同的集合之间进行选择，并将较近或较远的一对分配给拥有位向量内 n(n-1)/2 个字段的当前位字段的两个点，我可以创建一组位-具有所需距离模式的向量。

我认为这些是存在的，因为我认为有一种结构可以高概率地创建这种模式。创建 n 个长度为 k 的随机位向量。任何两个这样的位向量具有 k/2 的预期汉明距离和 k/4 的方差，因此标准偏差为 sqrt(k)/2。对于大 k，我们期望不同的距离相当相似。要在此集合中创建两个非常靠近的点，请将其中一个复制为另一个。要创建相距很远的两个点，请使一个点不是另一个点(一个点为 0，另一个点为 1，反之亦然)。

给定任意两个点，它们之间的预期距离将为 (n(n-1)/2 - 1)k/2 + k(如果它们应该相距很远)和 (n(n-1)/2 -1)k/2(如果它们应该靠得很近)并且我在没有证据的情况下声称通过使 k 足够大，预期的差异将战胜随机变化，我将得到几乎是 A 和漂亮的距离我需要多少 B。