问题标签 [chinese-postman]

我想在不存在欧拉循环的图中解决中国邮递员问题。所以基本上我在图中寻找一条路径，它恰好访问每条边一次，并在同一个节点开始和结束。当且仅当每个节点都有相同数量的边进入和退出图时，图才会具有欧拉环。显然我的图表没有。

我发现欧拉化（制作欧拉图）可以解决我的问题LINK。任何人都可以建议一个脚本来向图中添加重复的边，以便生成的图没有奇数度的顶点（因此确实有一个欧拉电路）？

这是我的例子：

这是我之前提出的一些问题的延续，如何为庭院灯和圣诞灯路线效率 (CS)规划最有效的路线，关于我尝试尽可能有效地用庭院灯覆盖屏蔽结构。

这是规则：

• 尽量减少光重叠
• 每串灯长 234 英寸（这很重要，因为除非它位于另一个分支的末端，否则我无法启动新的灯分支）。

• 把这些想象成圣诞灯饰，你有男性和女性的一面：

  start (male) end (female) =[}~~~o~~~o~~~o~~~o~~~o~~~o~~~o~~~{=] <- to outlet to other lights ->

  因此，只要有一个雌性供雄性插入，多股就可以菊花链，如下所示：

  

• 一个母插头必须通过一个公插头为下一个灯串供电，一个公插头不能给另一个公插头供电。

• 这是我的结构图：

  

• 粉红色圆圈 = 挂灯的地方（不，在 10、11 和 12 的交叉点没有挂灯的地方 -这不是错误）。

• “开始” = 唯一可用的电源插座。
• 黄点 = 我想要让灯光沿着结构运行的部分。

基于我之前的问题，我开始研究“路由效率问题”算法。我使用这篇文章，用 eulerization 解决中国邮递员算法来开始，它引导我找到这段代码（感谢 @DamianoFantini 在我之前的文章中帮助我正确设置图表）：

这是代码的结果：

我认为这可以转化为这一点（但我是一个图形/算法菜鸟，如果我错了，请纠正我）：

显然，这里有一些问题：

1. 我不知道每束灯的结束/开始应该在哪里（我认为算法也不知道）
2. 节点 1 独立供电。这在现实中是行不通的。所有电源必须来自“开始”位置。
3. 距离和结构似乎没有被考虑在内。

有没有办法将这些约束添加到算法中？我可以使用另一种算法来使这更容易吗？

从时间复杂度的角度来看，旅行商问题和中国邮递员问题有什么区别？我的意思是 TSP 和 CPP 之间哪个时间复杂度更高？

在尝试解决中国邮递员问题时，您将必须找到图中所有奇数顶点的所有可能配对的最小成本并添加找到的边（配对），我的问题几乎就是这样。

如何实现一个返回所有可能配对的算法？ 或如何修复我的。

我有一个起点，但无法走得更远或想得更远。

我尝试查看以下主题，但不幸的是它们并没有帮助我。 我应该如何为中国邮递员问题生成分区/对？或找到使权重总和最小化的配对？

输出与

应该：

但是：

我无法完全解决插入向量的方式。查看输出时，您可以看到它几乎是正确的（忽略格式）。第一行12 34 45是正确的。其次35 46，当它必须时12 35 36，似乎只有第一对丢失了，你会注意到它适用于每个配对。

更新：所以我想出了另一种似乎很有希望的算法，但是我没有丢失一些配对，而是得到了重复。高度赞赏解决方案。如果我自己找到一个，我会发布它。

输出：