我的问题与此类似:Get largest Subset of Integers with certain minimum distance/difference
然而，就我而言，我有一组任意元素和一个距离矩阵，而不是可在一维中嵌入的整数之间的距离，该距离矩阵给出了每个元素到另一个元素的距离。距离都是整数并且满足 distance metric 的要求。给定指定的最小距离(例如 3)，目标是识别起始集合的最大大小子集，使得子集中的每对元素的距离至少为指定阈值。根据上面的链接，明显的贪婪算法对于一维情况(整数之间的距离)是最优的。然而，我怀疑任意数量的维度是否都是这种情况。这似乎是一种可以简化为某些众所周知的计算机科学问题的问题，但如果是这样，我还无法找到正确的关键字组合来识别它。我只找到了一维情况的引用。
那么，这个问题是NP完全问题吗？如果是这样，是否有好的启发式算法？如果没有，是否有快速算法可以最佳地解决它？
(对于任何好奇的人来说，这个问题是在选择最大可能的一组 DNA 测序条形码的背景下出现的，这些条形码彼此之间有足够的差异，即使存在测序错误，它们仍然可以区分。)
编辑:现在我想起来了，我们可以通过将距离矩阵替换为 0 和 1 的矩阵来简化问题，其中 1 表示元素靠近(距离小于阈值)，0 表示元素靠近不熟。那么我想目标是找到邻接矩阵全为 0 的元素的最大子集。
最佳答案
我认为你需要的问题是https://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 ，这是 NP 完全的。如果你能解决最小允许距离2的问题，那么你可以通过构造一个距离矩阵来解决最大独立集，其中独立集图中相邻顶点之间的距离为1，这样它们就不允许在一起。
关于algorithm - 找到项目之间距离最小的最大子集？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43218391/