optimization - 最大限度地减少笔式绘图仪或类似设备中的笔升力

Question

我正在寻找对在机械笔绘图仪上绘图的算法的引用。

具体来说，我有一个直线向量列表，每个向量代表要绘制的一条线。首先我想删除重复的向量，所以每条线只绘制一次。这很容易。

其次，有许多向量相交，有时在端点处，但并非总是如此。它们可以按任何顺序绘制，但我想找到一个可以减少必须提起笔的次数的顺序，最好是最小化，尽管我知道这可能需要很长时间来计算，如果它是可计算的。如果有帮助，可以将相交的向量分解为更小的向量。但一般来说，如果笔沿直线移动，最好尽可能长时间地保持直线移动。因此，两个首尾相连的平行向量可以组合成一个向量，等等。

这听起来像是各种各样的图论问题，但我对此知之甚少。任何人都可以指出我需要研究的引用资料或算法吗？或者可能是示例代码？

谢谢，

尼尔

Answer 1

问题是 Chinese postman problem 的一个例子这是一个NP完全问题。最著名的 NP 完全问题是 Travelling Salesman .所有 NP 完全问题的共同点是它们都可以相互转化。没有已知的算法可以在与输入中节点数量多项式相关的时间内解决其中任何一个，它们是非多项式 (NP)。

对于您的情况，我会建议一些简单的启发式方法。不要过头，只要选择任何非常简单的东西，比如尽可能长的直线，然后将笔举到最近的可用起点，然后从那里继续。