查找元素之间具有最大距离的对象子数组 [英] Find sub-array of objects with maximum distance between elements

问题描述

让对象[a，b，c，d，...]组成一个数组，并给出一个函数distance(x，y)，该函数给出一个数值，显示对象x和y的不同"程度.

我正在寻找一种算法，以找到长度为n的数组的子集，以最大程度地提高该子集元素之间的最小差异.

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

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

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

PS:这是一个示例，矩阵显示了每个元素之间的距离" ...

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

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

解决方案

此问题是 NP-hard，所以没人知道一种有效的算法(多项式时间).

通过 CLIQUE ，这里有一个简短的草图，说明它是NP困难的.>

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

Let be an array of objects [a, b, c, d, ...] and a function distance(x, y) that gives a numeric value showing how 'different' are objects x and y.

I'm looking for an algorithm to find the subset of the array of length n that maximizes the minimum difference between that subset element.

Of course, I can't simply sort the array by the minimum of the differences with other elements and take the n highest entries, since removing an element can very well change the distances. For instance, if a=b, then removing a means the minimum distance of b with another element will change dramatically.

So far, the only solution I could find was wether to iteratively remove the element with the lowest minimum distance and re-calculate the distance at each iteration, until only n elements are left, or, vice-versa, to iteratively pick new elements, recalculate the distances, add the new pick or replace an existing one based on the distance minimums.

Does anybody know how I could get the same results without those iterations?

PS: here is an example, the matrix shows the 'distance' between each element...

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

If we'd keep only 2 elements, that would be c and d; if we'd keep 3, that would be a or b, c and d.

解决方案

This problem is NP-hard, so no-one knows an efficient (polynomial time) algorithm for solving it.

Here's a quick sketch that it is NP-hard, by reduction from CLIQUE.

Suppose we have an instance of CLIQUE in the form of a graph G and a number n and we want to know whether there is a clique of size n in G. Construct a distance matrix d such that d(i, j) = 1 if vertices i and j are connected in G, or 0 if they are not. Then find a subset of the vertices of G of size n that maximizes the minimum distance between elements (your problem). If the minimum distance between vertices in this subset is 1, then G has a clique of size n; otherwise it does not.

这篇关于查找元素之间具有最大距离的对象子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！