performance - 最大化数组中成对距离的总和

Question

想象一个列表 [e1, e2, ..., en] 和一个函数 f(e1, e2) -> number 返回任意两个之间的距离恒定时间的元素。

f(e, e) = 0
e1 != e2 => f(e1, e2) > 0
f(e1, e2) <= f(e1, e3) + f(e3, e2)

目标是排列列表，使元素的成对距离之和最大。

我想出了一个 O(n^2) 贪婪算法，它似乎是这样做的:

1. 制作所有成对距离的表格(或三角矩阵)
2. 寻找最大的距离，选择那对作为起点(可以在第 1 步中完成)
3. 通过添加使总和增加最多的自由元素来扩展列表(可能使用链接哈希集来跟踪到目前为止选择的元素并允许快速检查)

如果不正确请告诉我。 您能想出/建议更快的算法或实质性(非复杂性)加速吗？解决这个问题的最小复杂度是多少？

这个问题类似于在严格正加权的完全图中寻找最长路径，除了你知道距离函数的特性外，它还与最小跨度有一些相似之处树(也许这种相似之处比我目前意识到的更多？)。

(这个问题可能等同于某个已知问题，我很想知道是哪一个)

Answer 1

您的最佳排列会产生一条路径，其中每个节点都连接到排列列表中的下一个节点。因此，您正在寻找最长的简单路径，即使对于您描述的度量空间也是 NP-hard。 (请参阅有关最长路径问题的维基百科)。你的贪婪解决方案有一个问题，如果你选择两个距离最远的元素，那么如果有两个相同的额外元素投影到连接两个原始选定元素的线段的中点，那么最佳解决方案是这 4 个点实际上是创建一个从第一个端点到一个中心点到另一个端点到另一个中心点的链，而不是最初连接最远的顶点(这将导致然后连接到一个中心点，并且然后连接到距离为 0 的另一个中心点，通过三角形不等式创建一条更短的路径)。