我正在尝试按照路径顺序对一组三维坐标进行排序。一个示例:
points = np.array([[ 0.81127451, 0.22794118, 0.52009804],
[ 0.62986425, 0.4546003 , 0.12971342],
[ 0.50666667, 0.41137255, 0.65215686],
[ 0.79526144, 0.58186275, 0.04738562],
[ 0.55163399, 0.49803922, 0.24117647],
[ 0.47385621, 0.64084967, 0.10653595]])
这些点是随机排列的，但总会有一条路径穿过它们。我正在使用LKH求解器（Helsgaun 2009）寻找适应性旅行商问题（TSP）的路线。它包括两个修改：
- 在原点附近添加一个点。这在我处理的每个实例中都能找到最佳起点。这是我的想法，我没有其他依据。
- 在每个点上添加一个距离为零的点。这使得求解器能够找到路径的另一端。这个想法来自于这个 SO 问题。
请注意，TSP不涉及位置，只涉及节点之间的距离。因此，求解器并不知道（或在意）我正在使用三维空间。我只需像这样制作距离矩阵：
import numpy as np
from scipy.spatial.distance import pdist, squareform
# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, 'euclidean'))
# Normalize to int16s because the solver likes it.
d = 32767 * dists / np.sqrt(3)
d = d.astype(np.int16)
# Add a point that is zero units from every other point.
row, col = d.shape
d = np.insert(d, row, 0, axis=0)
d = np.insert(d, col, 0, axis=1)
我将这个问题提交给我的pytsp分支，然后将其传递给LKH求解器。一切都很好......除了路径交叉的情况。TSP解决方案不能有闭合环，所以我总是得到右边显示的开放环路：
请注意，这是我情况的类似2D版本。还要注意，这些点没有完全对齐，即使沿着“直线”部分也是如此。
因此，我的问题是：如何帮助求解器尽可能地保留路径的方向？我有两个不成熟的想法，但迄今为止未能实现任何东西：
- 使用另一种度量而不是L2。但我认为这行不通，因为在给定的交点处，'错误'点本质上并没有什么不同。它的错误取决于前一个点。而我们还不知道哪个是前一个点（这就是我们试图弄清楚的）。所以我认为这不好。
- 评估每组三个点的局部共线性（例如使用每个三元组的行列式）。通过此共线性系数调节本地“三维坡度”（不确定我的意思是什么）。为每个点提供另一个表示此本地对齐的维度。现在，范数将反映局部对齐，（希望）大致共线的事物将连接起来。
我已经将这些文件放在Dropbox上：
谢谢您的阅读；任何想法都会受到赞赏。
参考文献
K. Helsgaun, Lin-Kernighan TSP启发式算法的通用k-opt子移动。Mathematical Programming Computation, 2009, doi: 10.1007/s12532-009-0004-6.