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

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

如果算法倾向于最大化average连续点之间的欧氏距离。

Edit:

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

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

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