最短路线，起点和终点任意

Question

我正在寻找一个算法，将连接大量的地理坐标（100-1000），创造他们之间的最短可能的路线，从任何地方开始，并完成任何其他地方。我在用Python。你知道吗

我已经研究了可用的算法，我的问题类似于旅行推销员，但它需要我定义一个起点，并在结束时回到同一个点。我会把Uber带到任何起点和终点。我想要的是在尽可能少的步行时覆盖所有点。我不在乎它从哪里开始或结束。你知道吗

Prim和Kruskal的算法似乎能找到好的起点和终点，但它们创建了一棵树，而不是像TSP那样优化的行走路线。你知道吗

Prim算法：

克鲁斯卡尔算法：

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

Answer 1

Prim和Kruskal是寻找生成树的算法。您正在尝试解决一个众所周知的TS（旅行推销员问题）变体，在这个变体中，您不会回到您的起点。你知道吗

根据你的定义，你家的位置无关紧要。你定义的问题是用最少的旅行距离访问每一个地方，而不是回到你的起点。这在“文学”中有很好的论述。你知道吗

“快速打击”解决方案是采取任何标准的TS解决方案，并删除最长的部分。这是一个很好的启发，虽然它不能保证最优的解决方案。你知道吗

Answer 2

如果您不需要产品化的解决方案，请编写Python以TSPLIB格式转储距离矩阵，并添加一个到其他城市的距离为零的额外城市（表示您将往返的地方）。然后把它喂给（例如）Concorde或LKH。你知道吗