algorithm - 通过断开的线段的最短路径

Question

我有一个非常常见的问题，但找不到解决它的名称或算法。

给定欧几里得二维空间中的一组线段，我喜欢找到通过所有线段的最短路径。

例如，绘图机会出现此问题，该绘图机使用笔在纸上绘图，并且必须最大限度地减少绘图对象之间无用的旅行时间。

这个问题的名称是什么？是否有已知的简单近似解？

Answer 1

最小化绘图笔的非绘图行程距离的问题非常接近于以线段端点为顶点并在绘制的线段的两端之间分配成本为 0 的旅行商问题。

与TSP不同，您的问题允许您开始和停止在线段中间绘制线条。电源图标上的垂直线 是您想要在两段中绘制一条线的示例，而不是一次绘制一条线。但是，我猜这种情况只会在您开始绘制的位置与您停止绘制的位置不同时出现。如果我的猜测是正确的，那么您通过解决旅行商问题得到的解决方案与最优解决方案的差异最多只有图的宽度。

Answer 2

您必须为此调整 tsp 的解决方案。

你可以通过遗传算法来做到这一点。它不能保证你会得到最好的解决方案，但你通常可以在很短的时间内非常接近它。

您基本上从一组随机解决方案开始。然后，您对每个解决方案进行轻微的随机更改，然后测量行进距离。您保留距离最短的那些。只需重复此过程，直到新一代不提供优化或您的时间用完为止。