最大化阵列中成对距离的总和 [英] Maximise sum of pairwise distances in array
问题描述
想象一个列表[e1, e2, ..., en]和一个函数f(e1, e2) -> number，该函数在恒定时间内返回任意两个元素之间的距离.
Imagine a list [e1, e2, ..., en] and a function f(e1, e2) -> number that returns the distance between any two elements in constant time.
f(e, e) = 0
e1 != e2 => f(e1, e2) > 0
f(e1, e2) <= f(e1, e3) + f(e3, e2)
目标是排列列表，以使元素的成对距离之和最大.
The goal is to permute the list so that the sum of pairwise distances of the elements is maximal.
我想出了一个O(n^2)贪婪算法，该算法似乎正在执行此操作:
I came up with a O(n^2) greedy algorithm that seems to be doing this:
- 进行所有成对距离的表格(或三角形矩阵)
- 寻找最大距离，选择该对作为起点(可以在步骤1中完成)
- 通过添加最大增加总和的自由元素来增加列表(也许使用链接的哈希集来跟踪到目前为止所选择的元素并允许快速检查)
请告诉我它是否不正确. 您能提出/建议一种更快的算法还是实质性的(非复杂性)加速?而解决这个问题的最小复杂性是什么?
Please tell me if its incorrect. Can you come up with/suggest a faster algorithm or substantial (non-complexity) speedups? And what is the minimal complexity for solving this problem?
此问题类似于在严格正加权的完整图中找到最长路径，除了您知道距离函数的特征外，它还与最小跨度有些相似一棵树(也许比我现在意识到的还要多?).
This problem is similar to finding the longest path in a strictly positively weighted complete graph, except for the fact that you know the characteristics of the distance function, it also bears some resemblance to the minimum spanning tree (Maybe there's more to this resemblance than I currently realise?).
(这个问题可能等同于一些已知问题，我很想知道是哪个问题)
(Probably this problem is equivalent to some known problem, I'd be interested to know which one)
推荐答案
您的最佳排列会产生一条路径，其中每个节点都连接到排列列表中的下一个节点.因此，您正在寻找最长的简单路径，即使对于您所描述的度量空间，该路径也是NP难的. (有关最长路径问题，请参见Wikipedia).贪婪的解决方案存在以下问题:如果选择相距最远的两个元素，则如果有两个相同的额外元素投影到连接两个原始选定元素的线段的中点，则最优解决方案这四个点实际上是在创建从第一个端点到一个中心点再到另一个端点到另一个中心点的链，而不是最初连接最远的顶点(这将导致然后再连接到一个中心点，并且然后在距离0处连接到另一个中心点，通过三角形不等式创建一条较短的路径.
Your optimal permutation gives rise to a path where each node is connected to the next node in your permuted list. Thus you are looking for a longest simple path, which even for a metric space like you describe is NP-hard. (see wikipedia on longest path problem). Your greedy solution has the problem that if you choose two elements that are the farthest distance apart, then if there are two extra elements that are identical that project onto the midpoint of the line segment connecting the two original selected elements, then the optimal solution for these 4 points is actually to create a chain from the first endpoint to one of the center points to the other endpoint to the other center point, rather than connecting the farthest apart vertices originally (which would lead to then connecting to a center point, and then connecting to the other center point at distance 0, creating a shorter path by the triangle inequality).
这篇关于最大化阵列中成对距离的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
