问从相同的地理点画出相等的路径

EN

你有一个很好的起点，从一开始就按距离排序。现在把10,000点看作1000个同心圆环，每个环10点。我们所要做的就是把每一个戒指上的一个点分配给一个销售员，如下所示：

• 按当前点的路径长度给销售人员下订单
• 从拥有最长路径的推销员开始：
  • 让推销员取最近的点(当前环中的10点)。
  • 继续寻找下一位推销员(目前仍有9点)
  • 其他8名销售人员等等

​

如果你从外到内迭代环，路径长度的差异就会变小(而不是从小环变大)。

你可以从最外面的圆环上给每一个销售员播种每一个点。

对于“最近”的步骤，您只需将最后一个添加点连接到正在考虑添加的当前点。对于每个销售员的点集，路径不会是最短的，但是每个路径都会有相同的无效率，而且总体上路径长度差异将收敛到零。

如果你想改进每个销售员的路径，当你考虑添加一个点时，你可以在候选人的“in set”中找到两个最近的点，然后在它们之间插入，或者如果这个距离小于两个最近点的距离之和，就把它附加到‘结束’点之一。