中国邮差的变化问题_

为了做好春季季度考试的准备，我正在学习和尝试图形问题。中国邮差的变化问题_

我已经熟悉了像“旅行推销员”这样的典型问题，但是当我深入研究“中国邮递员问题”及其变化时，我立即觉得这个问题的一个重要方面缺失了：容量有限，因此需要在一定数量的n信件成功发送（为了获得新信件）后返回办公室。那么寻找最短路径呢？

我对CPP非常感兴趣，因为它与现实生活中的相关性和易用性有关，但我认为增加这个方面会使它更适合现实生活。

对于如何在无向图中找到最短路径的任何帮助感谢，该路径至少访问一次边（CPP）必须返回到起点（后站）的限制字母数量被传送。

EDIT（originial CPP的说明）： “中国邮递员问题或邮递员问题是要找到访问一个（连接）无向图的每条边的最短闭合路径或电路。当图具有。一个欧拉电路（一个封闭的步行覆盖每个边缘一次），该电路是一个最佳解决方案如果图形不是欧拉，它必须包含奇数度的顶点通过握手引理，必须有一个偶数为了解决postman问题，我们首先找到一个最小的T-连接，我们通过T连接的两倍来生成欧拉图，原始图中邮递员问题的解决方案是通过找到新的欧拉电路来获得图“。 Src：wikipedia.org

来源

2012-04-11 Chicago1971

[这些词语过滤器必须去...]（http://meta.stackexchange.com/questions/107989/using-the-word-problem-in-titles） – Mysticial 2012-04-11 21:22:36

请提供问题的描述或链接到一个很好的描述... – RBarryYoung 2012-04-11 21:24:27

*“我想听听你对这个问题的想法。”*不是一个正确的问题。如果你没有问一个适当的编程问题，你会被社区关闭。 StackExchange论坛是Q + A论坛。他们不是讨论论坛，他们绝对不是为它设立的。 – RBarryYoung 2012-04-11 21:38:56

您的变体通过从所有值严格在B/4和B/2之间的例如3-partition problem减少为NP-hard。它可能使用与capacitated vehicle routing相同的方法“解决”。不过，你必须明白，CPP不是一个真正的问题，而不是研究T-join的借口。

来源

2012-04-11 22:19:59 oldboy

一个应用程序正在测试中，其中节点是状态，并且您想要执行每个状态转换。虽然http://www.ams.jhu.edu/~castello/251/Handouts/ChinesePostman.doc声称，它真的对检查或维修现实生活中的道路有用上。 – mcdowella 2012-04-12 04:12:26

感谢您的回答，老人。尽管如此，我仍然没有发现任何类似于上面在浏览容量不同的车辆路径问题时发布的问题。 – Chicago1971 2012-04-12 13:24:00

如果您想尽量减少总距离，多辆车和多辆车之间没有差别。 CVRP将为有限容量的车辆提供所有客户端*顶点*（而不是边缘）。从您的问题到CVRP的一个可能的减少是将客户端放在每个边缘的中间。 – oldboy 2012-04-12 13:31:42

中国邮差的变化问题_

回答

相关问题