2

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

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

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

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

有谁知道没有这些迭代我怎么能得到相同的结果？

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

   A B C D
一 - 1 3 2
b 1 - 4 2
c 3 4 - 5
d 2 2 5 -

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

4

2 回答 2

3

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

这是一个简单的草图，它是 NP-hard，通过从CLIQUE减少。

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

于 2013-01-16T00:41:44.317 回答
1

正如 Gareth 所说，这是一个 NP-hard 问题，但是已经有很多研究来解决这类问题，因此已经找到了比蛮力更好的方法。不幸的是，这是一个很大的领域，您可能会永远花时间研究解决方案的可能实现。

但是，如果您对解决此问题的启发式方法感兴趣，我建议您研究 Ant Colony Optimization ( ACO )，它已被证明在寻找图中的最佳路径方面相当有效。

于 2013-01-16T19:52:17.607 回答