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

Question

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

给定欧氏二维空间中的一组线段，我想找到通过所有线段的最短路径。

例如，绘图机会出现此问题，它使用笔在纸上绘图，并且必须尽量减少绘制对象之间无用的移动时间。

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

Answer 1

最小化绘图笔非绘图行进距离的问题非常接近traveling salesman problem以线段端点为顶点，在一条直线绘制的线段两端之间赋值为0。

不同于TSP ，您的问题允许您在线段中间开始和停止绘制线条。 power icon 上的垂直线是您想要分两段而不是一次绘制一条线的时间示例。但是，我猜想只有当您开始绘制的位置与您停止绘制的位置不同时才会出现这种情况。如果我的猜测是正确的，您通过解决旅行推销员问题得到的解与最优解最多只相差图的宽度。