问题标签 [chinese-postman]

我有很多循环的有向图，可能是强连接的，我需要从中得到一个最小的循环。我的意思是我需要得到循环，这是图中最短的循环，并且每条边至少被覆盖一次。

我一直在寻找一些算法或一些理论背景，但我发现的只有中国邮递员算法。但是这个解决方案不适用于有向图。

有谁能够帮我？谢谢

编辑>>该图的所有边具有相同的成本 - 例如 1

我正在编写一个涉及解决中国邮递员问题的课程。我们的任务只需要我们编写一个程序来解决硬编码图的问题，但我正在尝试自己解决一般情况。

给我带来麻烦的部分是为奇数顶点生成配对分区。

例如，如果我在图中有以下标记的奇数顶点：

我需要找到我可以用这些顶点进行的所有可能的配对/分区。

我发现我会i给出分区：

因此，鉴于上面的 6 个奇数顶点，我们将知道我们需要生成i = 15分区。

这 15 个部分看起来像：

然后，对于每个分区，我取每一对并找到它们之间的最短距离，然后为该分区求和。选择其对之间总距离最小的分区，然后我将奇数顶点之间的最短路径之间的所有边加倍（在所选分区中找到）。

这些代表邮递员必须走两次的边缘。

起初我以为我已经制定了一个合适的算法来生成这些分区：

1. 从所有奇数顶点开始按升序排序

   12 34 56

2. 选择当前具有最大顶点的对后面的对

   12 [34] 56

3. 将这对中的第二个数字加 1。将所选对左侧的所有内容保持不变，并将所选对右侧的所有内容设为集合中的剩余数字，按升序排序。

   12 35 46

4. 重复

然而，这是有缺陷的。例如，我意识到当我到达终点并且选择对位于最左边的位置（即）时：

[16] .. ..

在这种情况下，我制定的算法将停止，并且不会生成开始 [16] 的其余对，因为它的左侧没有要更改的对。

所以，它又回到了绘图板上。

以前研究过这个问题的人有没有任何提示可以帮助我指出生成这些分区的正确方向？

旅行商问题(TSP) 和中国邮差问题(CPP)有什么区别？

对我来说，两者都想去一个目的地，然后再回来。

我正在寻找一种在双向图中找到中国邮递员电路的算法。这里的双向图不是对称有向图，而是 Edmonds & Johnson 在 1970 年引入的图。

根据 Harold N Gabow 在 983 年发表的一篇论文，我发现很少有解决类似问题的论文，但没有正式的算法；他们刚刚提到这个问题可以减少/与完美的 b 匹配、双向网络流......等等有关，到目前为止我还无法理解。

如果有人知道这个概念和算法，请给我一些建议。

我有一个图，其中包含必须访问的边，以及可选的边。边缘具有不同的重量，可以在任一方向上移动，并且可以根据需要多次移动。我正在尝试确定最小化总重量的路线。

据我了解，中国邮递员问题处理的图必须至少访问一次图的每条边。谁能告诉我上面描述的变体是否有一个“名称”或指出我可能处理解决这种类型图的算法的方向？

我正在尝试用 Python 编写一个解决方案，所以任何使用它的解决方案都会很棒，否则我相信我将能够完成一个解决方案。

好吧，我现在手头的一项小工作遇到了问题……

主要目标是，有一个给定的图（没有权重和有向图），我必须发现总长度最小的一组路径（如果可能，只有一条路径，但它们可以更多），覆盖所有边。其他“约束”是图形是 DFA，因此路径应该以初始状态开始，并以接受状态结束（它们被标记）。

最初我发现这和中国邮递员问题很像，事实上也确实如此。但在我的情况下，图形是有向的（我相信这会改变一些事情），并且不止一次处理边没有任何问题，因为结果路径仍然是最短的。

我读过一些关于欧拉路径和 T-Joins 的东西，这可能是我的问题的解决方案。如果我理解正确，我应该做的是在我的图中找到一条欧拉路径，如果没有，让它存在，复制 T-Joins，或者类似的东西......我遇到了很多麻烦理解这一点，我什至不知道这是否是我问题的答案......（我在这里找到的最短和最容易理解的文本：http ://en.wikipedia.org/wiki/Route_inspection_problem ）

仅举一个简短的例子，给定这张图（1 是初始值，5 是接受度）：

1 -> 2; 2 -> 3; 2 -> 4; 4 -> 5;

我的问题的答案应该是：1 -> 2 -> 4 -> 5 和 1 -> 2 -> 3。（在这种情况下，我还必须处理 3 不是接受状态的事实，但是边缘必须被覆盖。但我可以通过将所有没有边缘的状态标记为其他节点作为接受状态来轻松解决这个问题）。

希望我解释得很好。

提前致谢！

所以下面是我用于查找图在有向图中是否具有欧拉循环的代码。该代码适用于几种情况（我的主要方法中的注释行有效）。但它确实适用于 g1 图（我的主要方法中未注释的代码）。它说图形（g1）不是欧拉电路，应该是。请帮我找出错误，谢谢

输出为假。请帮忙

我知道我的问题更多是关于图表而不是编程，但是，我喜欢这里非常活跃的社区，你们可能会使用图表。

所以在这里我想知道一个无向图的欧拉循环的集合是否可以包含多个。

谢谢

所以，我想用图表来找点乐子，现在它让我发疯了。

首先，我生成一个具有给定边数的连通图。这是容易的部分，这成了我的诅咒。基本上，它按预期工作，但我得到的结果非常奇怪（好吧，也许他们不是，我是这里的问题）。生成图的算法相当简单。

我有两个数组，其中一个填充了0to的数字n - 1，另一个是空的。

一开始，我将第一个元素打乱，将其最后一个元素移动到空元素。

然后，在一个循环中，我在第一个数组的最后一个元素和第二个数组的随机元素之间创建一条边，然后我再次将最后一个元素从第一个数组移动到另一个数组。

完成该部分后，我必须在顶点之间创建随机边，直到获得所需数量为止。同样，这非常容易。我只是在从0to范围内随机两个数字n - 1，如果这些顶点之间没有边，我创建一个。

这是代码：

现在，如果我把它打印出来，这是一个很好的图表。然后我想找到一个汉密尔顿循环。这部分有效。然后我遇到了我的祸根——欧拉循环。有什么问题？

好吧，首先我检查所有顶点是否都是偶数。他们不是。总是。每一次，除非我选择生成一个完整的图表。

我现在感觉被我自己的代码摧毁了。有什么问题吗？或者它应该是这样的？我知道欧拉回路会很罕见，但并不那么罕见。请帮忙。

我是图论的初学者。自 5 天以来，我一直在尝试使用 Python 将 Hierholzer 的算法实现到代码中。到目前为止，我的图论经验也是 5 天。我的代码如下：

D2图是连通的，每个节点的度数是偶数。当 ran_k 选择 6 作为起始节点且欧拉回路为 [6, 5, 4, 2, 1, 0, 3, 2, 6, 8, 7, 9, 6] 时，我的代码（循环函数）工作正常。任何起始节点都有欧拉回路，因为 D2 图是强连通的，所有节点的度数都是偶数。

当ran_k选择0作为起始节点时，我的循环函数返回如下：剩余图：{2：[6]，4：[2]，5：[4]，6：[5,8]，7：[9]， 8: [7], 9: [6]} 和临时堆栈为：[0, 3, 2, 1, 0]。这也没关系，因为我知道我必须在循环函数的这些输出上运行 cycle2 和 stack 函数。我可以在我的论文上解决这个问题，但我不知道如何使用 while 循环检查 D2 的长度为零或 tmp_stk 的长度为 0 来使用这些函数。我很高兴看到你的建议。