试图找到在图中导航一组边的最快方法
Trying to find the fastest way to navigate a set of edges in a graph
我不确定应该使用哪种算法来完成此任务。我有一个节点图。一些节点与需要遍历的加权线连接。但是，每个节点都与加权 bi-directional 线相连。只有一些线路必须经过，而其他线路仅用于导航。我需要找到一条路径来遍历所有这些必需的行 (bi-directional)，但只遍历一次。我知道我必须从哪个节点开始。
real-world 问题是我有一个需要从 CNC 模型中切割的边缘列表。我正在尝试减少 CNC 机器切割此图案所花费的时间。我知道我总是想从原点开始，但我不在乎图案在哪里结束，只要图案中的所有小块都被切掉即可。我知道切出每条边需要多长时间，而且机器足够精确，可以抬起头并转到任何一点，从那个位置开始。我的图表并不大，一般情况下最多可能有 100 个节点。
这与 travelling-salesman 不同，因为我不必在同一个地方开始和结束，而且我可以（并且需要）多次点击一个节点。
Djikstras 算法不起作用，因为我需要遍历所有节点以切割所有边...我不只是想找到从 A 点到 B 点的最快方法。
奖金，我需要用 C# 实现这个，但即使我只知道什么算法，我也可能会把它编程出来。
这是我需要裁剪的图案样例图片。请注意，有一条对角线和一条弧线我忘了分配权重，对角线可以是 50，弧线可以是 75：
我认为这仍然可以简化为旅行商问题。 TSP does not get any easier by removing the return-to-origin rule or allowing multiple visits.
因此不会有多项式解，您最好的选择可能是 approximate solution.
我相信这可以作为路由检查问题的案例来解决。
https://en.wikipedia.org/wiki/Route_inspection_problem
您需要确保图形存在欧拉回路，这可以通过运气或将奇数顶点连接在一起来实现。
我不确定应该使用哪种算法来完成此任务。我有一个节点图。一些节点与需要遍历的加权线连接。但是，每个节点都与加权 bi-directional 线相连。只有一些线路必须经过，而其他线路仅用于导航。我需要找到一条路径来遍历所有这些必需的行 (bi-directional)，但只遍历一次。我知道我必须从哪个节点开始。
real-world 问题是我有一个需要从 CNC 模型中切割的边缘列表。我正在尝试减少 CNC 机器切割此图案所花费的时间。我知道我总是想从原点开始，但我不在乎图案在哪里结束，只要图案中的所有小块都被切掉即可。我知道切出每条边需要多长时间，而且机器足够精确，可以抬起头并转到任何一点，从那个位置开始。我的图表并不大，一般情况下最多可能有 100 个节点。
这与 travelling-salesman 不同，因为我不必在同一个地方开始和结束，而且我可以（并且需要）多次点击一个节点。
Djikstras 算法不起作用，因为我需要遍历所有节点以切割所有边...我不只是想找到从 A 点到 B 点的最快方法。
奖金，我需要用 C# 实现这个，但即使我只知道什么算法，我也可能会把它编程出来。
这是我需要裁剪的图案样例图片。请注意，有一条对角线和一条弧线我忘了分配权重，对角线可以是 50，弧线可以是 75：
我认为这仍然可以简化为旅行商问题。 TSP does not get any easier by removing the return-to-origin rule or allowing multiple visits.
因此不会有多项式解，您最好的选择可能是 approximate solution.
我相信这可以作为路由检查问题的案例来解决。
https://en.wikipedia.org/wiki/Route_inspection_problem
您需要确保图形存在欧拉回路，这可以通过运气或将奇数顶点连接在一起来实现。