在一个三维笛卡尔空间中给定一组点，我正在寻找一种算法来对这些点进行排序，使得相邻两点之间的欧几里得距离最小化，同时希望该算法倾向于最大化相邻两点之间的平均欧几里得距离。
编辑：
我在https://cstheory.stackexchange.com/上发表了交叉贴，并得到了一个好答案。请参见https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin。
对点进行排序，使得相邻点之间的最小欧几里得距离最大化。
6
- Lior Kogan
5
这听起来非常像它将成为NP完全问题。 - David Heffernan
如果您根据它们的Z曲线索引进行排序，这样就足够好了吗？ - harold
@哈罗德：我不明白它如何有所帮助。 - Lior Kogan
@LiorKogan 你说得对，如果你反过来的话就可以了。 - harold
基于问题：https://dev59.com/t1vUa4cB1Zd3GeqPyOuE - Peter O.
2个回答
3
这是解决方案成本的下限，可以作为分支定界或不完全搜索算法的基础模块。首先按距离排序点之间的距离，按非递增顺序考虑它们。使用不相交集合数据结构来跟踪点的集合，当两个点之间有链接时，合并两个集合。在将所有点合并为一个集合之前遇到的最短距离的长度是完美解中最小距离的上限，因为完美解也将所有点合并为一个集合。但是你的上限可能比完美解中的最小距离更长，因为你连接的链接可能形成一棵树，而不是一条路径。
- mcdowella
1
您可以通过图形建模来解决问题，在点之间绘制线条，现在您拥有一个完整的图形，现在您的问题是在此图形中查找最长路径，这是NP-Hard问题，请参见维基百科longest path。
实际上，我回答了问题的第二部分，即最大化平均值，这意味着最大化从图中每个节点出发的路径，如果您把它们的权重设置为1/距离，那么它将成为旅行商问题（最小化路径长度），并且是NP-Hard问题。对于这种情况，可能可以看一下Metric TSP approximation。
实际上，我回答了问题的第二部分，即最大化平均值，这意味着最大化从图中每个节点出发的路径，如果您把它们的权重设置为1/距离，那么它将成为旅行商问题（最小化路径长度），并且是NP-Hard问题。对于这种情况，可能可以看一下Metric TSP approximation。
- Saeed Amiri
1
我没有点踩。感谢您发布答案。我正在寻找第一个问题的解决方案。更高平均水平的趋势将是一个“奖励”。 - Lior Kogan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接