试图找到在图形中导航一组边的最快方法

Question

我不确定应该使用哪种算法来完成此任务。我有一个节点图。某些节点与需要遍历的加权线连接。但是，每个节点都连接有一条加权的双向线路。仅需遍历其中一些行，而其他仅用于导航。我需要找到一条路径来遍历所有这些必需的线（双向），但是只遍历这些线一次。我知道我必须从哪个节点开始。

实际问题是，我有需要从CNC图案切割的边列表。我正在尝试减少CNC机床花费在切出该图案上的时间。我知道我一直想从原点开始，但是我不在乎图案在哪里结束，只要将图案中的所有小片段都切掉即可。我知道切块的每个边缘要花多长时间，并且机器足够精确，可以抬起头并从该位置开始到任意点。我的图不是很大，一般情况下可能最多100个节点。

这与旅行推销员不同，因为我不必在同一地点开始和结束，而且我被允许（并且被要求多次击中一个节点。

Djikstras算法不起作用，因为我需要遍历所有节点才能切掉所有边缘...我不仅仅是在寻找从A点到B点的最快方法。

奖金，我需要用C＃实现，但是即使我只知道什么算法，也可能可以对其进行编程。

这里是我需要裁剪的图案的示例图片。注意，有一个对角线和一个我忘记分配权重的弧线，对角线可以为50，弧线可以为75：

Answer 1

我相信这可以解决路由检查问题。

https://en.wikipedia.org/wiki/Route_inspection_problem

您将需要确保图中有欧拉回路，这可以通过运气或将奇数顶点连接在一起来实现。

Answer 2

我认为这仍然可以解决旅行商问题。 TSP does not get any easier by removing the return-to-origin rule or allowing multiple visits。

因此，不会有多项式解，您最好的选择可能是approximate solution。