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

Question

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

给出一组欧几里德2d空间中的线段，我喜欢找到通过所有线段的最短路径。

这个问题例如出现在绘图机上，该绘图机使用笔在纸上绘图，并且必须最小化绘制事物之间无用的行进时间。

这个问题的名称是什么？有没有简单的近似解决方案？

Answer 1

最小化绘图笔的非绘图行程距离的问题非常接近traveling salesman problem，其中线段端点为顶点并在绘制线段的两端之间分配成本0。

与TSP不同，您的问题允许您在线段中间启动和停止绘制线条。 power icon上的垂直线是您想要以两个线段绘制线条而不是一次绘制线条的时间示例。不过，我猜想，只有当你开始绘画的地方与你停止绘画的地方不同时，才会出现这种情况。如果我的猜测是正确的，那么通过解决旅行销售人员问题可以获得的解决方案与最佳解决方案的区别仅在于图表的宽度。

Answer 2

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

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

您基本上从一组随机解决方案开始。然后，您对每个解决方案进行轻微随机更改，然后测量行进距离。你保持距离最短的那些。重复这个过程直到新一代不提供优化或者你没有时间。