algorithm - 找到项目之间距离最小的最大项目子集？

Question

我的问题与此类似:Get largest Subset of Integers with certain minimum distance/difference

但是，在我的例子中，我没有在一维中嵌入整数之间的距离，而是有一组任意元素和一个距离矩阵，它给出了每个元素到其他元素的距离。距离均为整数，满足distance metric的要求。 .给定指定的最小距离(例如 3)，目标是识别起始集合的最大大小的子集，使得子集中的每对元素的距离至少为指定的阈值。

根据上面的链接，显然贪心算法对于一维情况(整数之间的距离)是最优的。但是，我怀疑任意数量的维度都是这种情况。这似乎是那种可以归结为一些众所周知的计算机科学问题的问题，但如果是的话，我还没能找到正确的关键字组合来识别它。我只找到了对一维情况的引用。

那么，这个问题是NP完全的吗？如果是这样，是否有一个好的启发式算法？如果不是，是否有快速算法可以最优地解决它？

(对于任何好奇的人来说，这个问题出现在选择尽可能多的 DNA 测序条形码集的背景下，这些条形码彼此之间差异很大，即使在测序错误的情况下仍然可以区分它们。)

编辑:现在想想，我们可以通过将距离矩阵替换为0和1s的矩阵来简化问题，其中1表示元素接近(距离小于阈值)，0表示元素是不熟。那么我假设目标是找到邻接矩阵全为 0 的元素的最大大小子集。

Answer 1

我想你需要的问题是https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 ，这是 NP 完全的。如果您可以解决最小允许距离 2 的问题，那么您可以解决最大独立集问题，方法是构造一个距离矩阵，其中独立集图中相邻顶点之间的距离为 1，因此它们不允许在一起。