为了现在为我的 Spring 学期考试做好充分准备,我正在研究和试验图形问题。
我已经熟悉了像“旅行商”这样的典型问题,但是当我深入研究“中国 postman 问题”及其变体时,我立即觉得这个问题的一个重要方面被遗漏了:拥有的方面容量有限,因此需要在成功发送一定数量的 n 信件后返回办公室(以便获得新信件)。那么如何找到最短路径呢?
我对 CPP 非常感兴趣,因为它与现实生活相关且易于应用,但我认为添加这方面将使它更适用于现实生活。
对于如何在至少访问每条边一次的无向图中找到最短路径(CPP)的任何帮助,我将不胜感激,这是在一定数量后必须返回起点(驿站)的约束信件已送达。
编辑(原始 CPP 的描述): “中国 postman 问题或路线检查问题是找到访问(连接的)无向图的每条边的最短闭合路径或电路。当图有 欧拉回路(一次覆盖每条边的封闭行走),该回路是最佳解决方案。 如果图不是欧拉图,则它必须包含奇数度的顶点。根据握手引理,这些顶点的数量必须为偶数。为了解决 postman 问题,我们首先找到一个最小的 T 连接。我们通过将 T 连接加倍使图成为欧拉图。原始图中 postman 问题的解决方案是通过为新图寻找欧拉回路获得的。” 来源:wikipedia.org
最佳答案
你的变体是 NP-hard 的,例如,3-partition problem其中所有值都严格介于 B/4 和 B/2 之间。它可能会使用一些与 capacitated vehicle routing 相同的方法“解决” .不过,您必须明白,CPP 与其说是一个真正的问题,不如说是研究 T 型连接的借口。
关于algorithm - 中国 postman 问题的变体,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10114157/