引用R.. GitHub STOP HELPING ICE关于问题的评论：

很确定它是 NP 完全的（相当于旅行商问题），不是吗？——

这是对的; 这是最纯粹的路线优化，绝不是一个新问题。您希望在本质上是完全互连的图形的所有顶点之间移动最短的总距离；从任何地方到任何地方都没有固有的限制。TSP 是此问题的一般情况陈述，您的问题仅通过预先定义最终路径中所需的某些沿边缘的移动来稍微专门化（但这些边缘可以以任何方向和任何顺序遍历。

从表面上看，之所以如此复杂，是因为像 Held-Karp 这样的 TSP 的详尽解决方案必须评估大量的可能性。对于在哪些点之间旅行，您没有真正的限制；你可以从任何地方去到任何地方。只有相对少量的边（您的挤出线）是已知的必要条件，理论上可以按任何顺序跟踪这些边。

如果我正确阅读你的图表，你从顶部中心附近开始，然后到左上角，然后到 S 曲线，然后你跳到主要形状并开始从“右臂”开始遍历它，向下转动通过“身体”和“左脚”的中央形状，然后到“右臀部”，通过那条腿到脚，然后回到“左肩”，通过那个“手臂”等。

如果我有那个权利，那么您肯定有“端点检测”，您可以在其中识别图形中仅属于一个线段的点（因此需要旅行移动才能到达或离开它们），并且正在计划旅行往返于这些点。很聪明。我很想知道你如何选择下一个去旅行。显然，未绘制线的最近端点是一个自然的选择，但您的算法似乎并没有这样做。它从一开始就选择一个相对较远的点进行挤出，然后返回到形状的其余部分。这实际上似乎是整个图表中最有效的举措，因为如果您不及早采取行动，您很可能会采取重大举措稍后再做决定，但以非详尽的方式做出该决定并不会“

无论如何，您的算法在路径选择方面做得很好，直到它完成绘制“右腿”。从那里开始最有效的移动是转到主要图形右侧的“Y”形底部并跟踪它。完成后，最近的未绘制线段将回到主图的左肩，这将引导您到达小点，并且您将以相对较小的行程移动到该区域结束。总的来说，我认为“最接近的剩余端点”策略在每一轮都接近最佳；当您到达绘制线的末端时，寻找离您当前位置最近的端点。它将做出您现有算法所做的大部分决定，以及一些更好的决定。这并不总是 最好的选择（例如，左上角的点，它永远不会最接近任何其他移动的结尾，因此在它是最后一个移动之前将被忽略），但通常是这样。

我的程序员精明说你也有一些递归交叉点跟踪（“树行走”）；该算法发现从一个点绘制多条路径，记住该点，然后选择一条路径。当它到达一连串拉伸线的末端时，它会返回到最近遇到的交叉点，重新评估可用路径，并选择下一条，直到绘制出该交叉点的所有路径。然后您跳回前一个交叉点，以递归 LIFO 方式依此类推。

虽然这通常也是接近它的一种聪明方式，但它会导致一些明显低效的移动，例如从主要人物的“右脚”回到“肩膀”（这是最近访问过但未被完全绘制的交叉点）那一点）。更有效的移动只是最近的剩余端点，即主图右侧看起来不稳定的 Y 的底部。

您如何选择交叉路径进行优先排序也很关键。一般来说，选择将您带到最近的交叉路口或终点的路线将减少您可能需要进行的回溯。然而，您的算法似乎更喜欢从叉子（或沿着它的叉子最多的路径）的最长路径，结果证明在这个特定的图中这并不是一个糟糕的方法。

现在，已经绘制了主要人物的“左臂”，我完全无法理解为什么您的算法选择交叉图形来绘制不稳定的 Y，然后再交叉回到左侧。这是迄今为止效率最低的举措，而且您可能指的是自己。给定要画的东西，从主图左臂末端的最有效路径是直线最近的端点，在左侧填充点和线，然后在图形上移动到不稳定的 Y。最近的端点实际上已经填充了前面提到的 Y，并且您将在点和小线的左侧区域结束图形遍历。根据最近点的计算，您可能会在图形左侧的该区域的角之间进行一次或两次相对低效的移动，但与整个图表的移动相比，这些都是微不足道的。如果您的算法正在为该图生成确定性结果，我会对其进行调试并逐步执行到该点，并找出为什么它认为该序列更可取。优化该决策很可能是近乎最优的整体图行走策略的关键。

如果您可以将绘图保存为 dxf，则可以使用 Repetrel 生成带有我们的“查找最近邻”优化的 gcode。你可以从这里下载http://hyrel3d.net -完整安装说明在开始http://hyrel3d.net/wiki/index.php/Installation_Overview

请参阅此视频中的过程：

免责声明：我为 Hyrel 3D 工作。仅在实际打印机上需要许可，软件安装不需要。

注意：这将生成 gcode 路径，但每次打印移动的 E 值为 1，因此适用于激光或喷墨，或使用 Hyrel 原生 E 计算运行，但可能不适用于其他 3d 打印机。