最短的路线，任何地点的起点和终点

Question

我正在寻找一种能够连接大量地理坐标（100-1000）的算法，在它们之间创建最短的路径，从任何地方开始并在其他任何地方完成。我正在使用Python。

我已经研究了可用的算法，我的问题类似于旅行推销员，但它需要我定义一个起点，并在最后回到同一点。我将把优步带到任何起点，从任何其他终点回到主场。我想要的是尽可能少地走路时覆盖所有点。我不在乎它的开始或结束。

Prim和Kruskal的算法似乎找到了很好的起点和终点，但它们创造了一棵树，而不是像TSP那样优化的步行路线。

Prim的算法：

Kruskal的算法：

基于Prim / Kruskal的期望结果，但使用TSP逻辑（手动绘制的示例，未优化）：

Answer 1

如果您不需要生产的解决方案，请编写Python以TSPLIB格式转储您的距离矩阵，其中包含一个额外的城市（代表您将与Uber相处的地方），其距离为零。然后将其喂给（例如）Concorde或LKH。

Answer 2

Prim和Kruskal是查找生成树的算法。您正试图解决一个众所周知的TS变体（旅行商问题），在这种情况下，您不会回到起点。

根据您的定义，您家的位置并不重要。您定义的问题是访问距离最短的每个位置，而不返回起点。这在“文献”中有很好的说明。

“快速打击”解决方案是采用任何标准TS解决方案并删除最长的段。这是一个很好的启发式方法，虽然它不能保证最佳解决方案。