2
我的问题是类似这样的：Get largest Subset of Integers with certain minimum distance/difference找到它们之间距离最小的项目的最大子集？
然而，在我的情况，而不是整数，这是嵌入在一个维度之间的距离，我有，让来自远方的元素的任意集合和距离矩阵每个元素与其他元素。距离都是整数，它们满足distance metric的要求。给定指定的最小距离（例如3），目标是识别起始集的最大尺寸子集，使得子集中的每对元素具有至少指定阈值的距离。
根据上面的链接，明显的贪婪算法对于一维情况（整数之间的距离）是最优的。但是，我怀疑这是任意数量的维度的情况。这似乎是一种会减少一些众所周知的计算机科学问题的问题，但如果是这样，我一直无法找到正确的关键字组合来识别它。我只找到了一维情况的参考。
那么，这个问题NP-complete？如果是这样，是否有一个很好的启发式算法？如果没有，是否有一个快速算法来解决它的最佳？
（对于任何人好奇，这个问题在选择尽可能大的组DNA序列条码是彼此充分不同于他们仍然可以即使测序错误区别开的背景下产生的。）
编辑：现在我想到了，我们可以通过用0和1的矩阵替换距离矩阵来简化问题，其中1表示元素接近（距离小于阈值），0表示元素不接近。那么我认为目标是找到邻接矩阵全为0的元素的最大尺寸子集。
我想你可以使用分治策略（见Corman，Algorithms）来找到距离阈值内的所有元素。然后，您可以采取该组的逆来找到您想要的组。 – mba12
我不明白分治策略如何在这里起作用，除非阈值非常低，只有很少的元素比指定的距离更近。这在我的特定数据集中并非如此。即使问题可以分解，也可以分解为较小的问题，但它绝对不是无限可分的，所以仍然需要解决一般问题。 –
根据违规情况的常见情况，在没有更多违规行为发生之前查找必须移除的最少点是有意义的。使用距离矩阵可以很容易地计算可用于获取候选人的每个点的违规数量。 – maraca