对点进行排序,使得连续点之间的最小欧几里德距离最大化

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

你可以通过图来建模你的问题，在你的点之间画线，现在你有了一个完整的图，现在你的问题是在这个图中找到最长的路径，这是NP-Hard，请参阅wiki上的最长路径。

事实上，我回答了问题的第二部分，最大化平均值，这意味着最大化从图的每个节点出发的路径，如果你将它们加权为1/距离，这将是一个旅行商问题（最小化路径长度）并且是NP-难的。对于这种情况，查看公制 TSP 近似值可能很有用。