algorithm - 中国 postman 问题的变体

Question

为了现在为我的 Spring 学期考试做好充分准备，我正在研究和试验图形问题。

我已经熟悉了像“旅行商”这样的典型问题，但是当我深入研究“中国 postman 问题”及其变体时，我立即觉得这个问题的一个重要方面被遗漏了:拥有的方面容量有限，因此需要在成功发送一定数量的 n 信件后返回办公室(以便获得新信件)。那么如何找到最短路径呢？

我对 CPP 非常感兴趣，因为它与现实生活相关且易于应用，但我认为添加这方面将使它更适用于现实生活。

对于如何在至少访问每条边一次的无向图中找到最短路径(CPP)的任何帮助，我将不胜感激，这是在一定数量后必须返回起点(驿站)的约束信件已送达。

---

编辑(原始 CPP 的描述):“中国 postman 问题或路线检查问题是找到访问(连接的)无向图的每条边的最短闭合路径或电路。当图有欧拉回路(一次覆盖每条边的封闭行走)，该回路是最佳解决方案。如果图不是欧拉图，则它必须包含奇数度的顶点。根据握手引理，这些顶点的数量必须为偶数。为了解决 postman 问题，我们首先找到一个最小的 T 连接。我们通过将 T 连接加倍使图成为欧拉图。原始图中 postman 问题的解决方案是通过为新图寻找欧拉回路获得的。”来源:wikipedia.org

Answer 1

你的变体是 NP-hard 的，例如，3-partition problem其中所有值都严格介于 B/4 和 B/2 之间。它可能会使用一些与 capacitated vehicle routing 相同的方法“解决” .不过，您必须明白，CPP 与其说是一个真正的问题，不如说是研究 T 型连接的借口。