尝试寻找在图中浏览一组边的最快方法

Question

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

现实世界中的问题是，我有一个需要从CNC图案中切割出来的边缘列表。我试图减少CNC机器切割此图案所需的时间。我知道我总是想从原点开始，但我不在乎图案在哪里结束，只要图案中的所有小块都被切割出来即可。我知道每个零件的每条边需要多长时间来切割，而且机器足够精确，可以抬起头并转到任何位置以从该位置开始。我的图形不是很大，通常最多有100个节点。

这与旅行商不同，因为我不必从同一个地方开始和结束，并且允许（并且需要）多次击中一个节点。

Djikstra算法不起作用，因为我需要遍历所有节点才能得到所有被切割的边缘... 我不仅仅是试图找到从点A到点B的最快方式。

额外奖励，我需要用C#实现这个算法，但即使我只知道是哪种算法，我也可以编程。

这是一个我需要切割的样式图案示例。请注意，我忘记为其中一个对角线和一条弧分配权重，可以将其分别设置为50和75：

- bunggo

---

每个形状都有起点和终点？不确定图表是否是最佳方法.. 这些形状已经布置在纸张上了，还是这也是优化问题的一部分？ - gjvdkamp

啊，等等，你已经计算出每个起点和终点之间的距离了吗？这些就是边权重？ - gjvdkamp

正确的...边缘是加权的，这实际上是从节点A到节点B（或任何节点）所需的时间量。形状大多是矩形，但偶尔在矩形内有一个弧线。 - bunggo

这些形状是否共享边缘？也许一个例子可以帮助澄清这个问题。 - user3386109

是的，它们可以共享一条边，因此只需要切割一次。我会提供一个被切出来的东西的图片，我只需要把它组合起来。 - bunggo

@user3386109，我添加了一个样本图案的图片，需要将其剪切出来。 - bunggo

Answer 1

我认为这可以被视为路线巡视问题的一个案例。

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

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

- ekke

---

这个解决方案在我看来是正确的。在这种情况下，问题变成了如何连接顶点以完成循环，使其保持全偶数或者只有起点和另一个奇数。这可以被视为稳定室友问题的一个例子，该问题也有多项式解法。https://en.wikipedia.org/wiki/Stable_roommates_problem - btilly

我认为这个问题本质上归结为中国邮递员问题，其中我有无向边，并且可能有一个顶点只有一条路径。最后，我可以摆脱追踪的时间，直接去下一个点。仍在努力想出C#解决方案，这绝对不是简单的。 - bunggo

最终...我最终找到了所有的奇顶点，然后在最短的奇顶点之间绘制了一条人工边，然后使用Fleury算法来跟踪路径。它非常有效并且速度很快。 - bunggo

Answer 2

我认为这仍然会归结为旅行商问题。删除返回原点规则或允许多次访问并不会使TSP变得更容易。

因此，没有多项式解决方案，你最好的选择可能是近似解。

- JonasH