algorithm - 对点进行排序，使连续点之间的最小欧氏距离最大化

Question

给定 3D 笛卡尔空间中的一组点，我正在寻找一种算法来对这些点进行排序，以使两个连续点之间的最小欧氏距离最大化。

如果该算法倾向于最大化连续点之间的平均欧几里得距离，这也将是有益的。

编辑:

我已经在 https://cstheory.stackexchange.com/ 上交叉发布了并得到了一个很好的答案。参见 https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin .

Answer 1

这是解决方案成本的下限，它可以作为分支限界或更不可靠的不完整搜索算法的构建 block :

对点之间的距离进行排序，并以非递增的顺序考虑它们。使用 http://en.wikipedia.org/wiki/Disjoint-set_data_structure跟踪点集，在通过两点之间的链接连接时合并两组。将所有点合并为一组时遇到的最短距离的长度是完美解中最小距离的上限，因为完美解也将所有点合并为一个。然而，您的上限可能比完美解决方案的最小距离长，因为您加入的链接可能会形成一棵树，而不是一条路径。