algorithm - 查找元素之间距离最大的对象子数组

Question

设是一个对象数组 [a, b, c, d, ...] 和一个函数 distance(x, y)，它给出一个数值，显示对象 x 和 y 的“不同”程度。

我正在寻找一种算法来找到长度为 n 的数组的子集，该子集最大化该子集元素之间的最小差异。

当然，我不能简单地根据与其他元素的差异的最小值对数组进行排序，然后取 n 个最高的条目，因为删除一个元素可以很好地改变距离。例如，如果 a=b，则删除 a 意味着 b 与另一个元素的最小距离将发生显着变化。

到目前为止，我能找到的唯一解决方案是迭代删除具有最低最小距离的元素并在每次迭代时重新计算距离，直到只剩下 n 个元素，或者，反之亦然，迭代选择新元素，重新计算距离，添加新选择或根据距离最小值替换现有选择。

有人知道我如何在没有这些迭代的情况下获得相同的结果吗？

PS:这里有一个例子，矩阵显示了每个元素之间的“距离”......

   a   b   c   da  -   1   3   2b  1   -   4   2c  3   4   -   5d  2   2   5   -

如果我们只保留 2 个元素，那就是 c 和 d；如果我们保留 3，那就是 a 或 b、c 和 d。

Answer 1

这个问题是NP-hard ，所以没有人知道解决它的有效(多项式时间)算法。

这是 NP-hard 的快速草图，由 CLIQUE 归约而成.

假设我们有一个 CLIQUE 的实例，其形式为图 G 和一个数 n，我们想知道 G 中是否存在大小为 n 的团. 构造一个距离矩阵 d 使得 d(i, j) = 1 如果顶点 i 和 j 在 G 中相连，否则为 0。然后找到 G 的顶点子集，其大小为 n ，可最大化元素之间的最小距离(您的问题)。如果该子集中顶点之间的最小距离为 1，则 G 有一个大小为 n 的团；否则它不会。