这是什么
你正在考虑中国邮递员问题，也称为路线检查问题或邮递员旅行。
它能做什么
该问题要求图的最短/最小成本游览，该图访问每个边至少一次。这被称为中国邮递员之旅（CPT）解决此问题可以让您在其他应用程序中：
找到校车或邮件投递的最佳路线，其中必须访问所有街道来接送乘客/投递邮件，并且巴士不限于仅访问街道一次。其他例子包括扫雪机路线、公路部门在街道上画线，或者警车试图按节奏访问每条街道。
描述机器的复杂性和/或优化测试该机器。例如，按下手机上的按钮就像在状态之间选择一条有向边。菜单出现，菜单关闭。如果您知道手机可能处于的所有状态，那么求解 CPP 将为您提供测试所有状态转换的最佳计划。该计划的长度是对机器复杂性的衡量。例如，诺基亚 2110 移动电话有一个包含 88 个菜单项和 273 个操作的菜单子系统。该系统的 CPT 的按钮按下次数为 515 次。 [1]
无向图
这是最初的问题，由关美高1960 年。他的论文于 1962 年被翻译成英文。 [2] 此后不久，研究表明该问题可以简化为匹配问题，因此可以使用线性规划在多项式时间内求解。 [3]格罗切尔等人。简单介绍一下这方面的历史。 [5]
要解决该问题，请注意该图必须是单个图连通分量.
如果图是单个连接组件并且所有节点都有偶数degree，那么该图有一个欧拉路径。该路径可以在O(|E|)时间使用Hierholzer 算法。如果不是所有的节点都有偶数度，那么我们需要一个更强大的算法。
观察到，如果一个图有两个奇数度的节点，添加连接它们的附加边将导致多图其中每个节点的度数为偶数。根据上面的内容，这样的图有一个容易找到的欧拉路径。进一步：无论采取哪条路线，必须遍历多次的边将连接两个奇数度的节点。很容易看出原因：向其中一个奇数度节点添加一条边使其成为偶数度，但使与该边相关的另一个节点具有奇数度。获得仅包含偶数度节点的图的唯一方法是在两个奇数度节点之间建立一条路径。为了最小化多重图上欧拉路径的成本，我们应该沿着两个奇数度节点之间的最小成本路径添加额外的边。这可以通过以下方式找到：迪杰斯特拉算法.
现在，想象一下我们有2n奇数节点。通过对上述内容的一些思考，您可以说服自己，您将需要n连接这些顶点对的不同的、不重叠的路径。知道这一点，解决问题的一种方法是使用Floyd-Warshall 算法计算奇数度节点之间的所有对最短路径O(|V|³)时间。然后可以找到最大加权匹配O(|E|*|V| 日志 |V|)时间。 [4]
迈克尔斯对此有一篇简单的文章以及一些直观的证明。 [6] Laporte 提供了更技术性的描述，将匹配问题转换为线性整数规划。 [7] 艾塞尔特等人。给出另一个技术描述以及对相关问题的相当广泛的审查（见下文）。 [8]
其他一些变体
由于我们总是只需要一个想法就可以使算法问题变得更加困难，因此以下是一些可能令人感兴趣的变体：
完全有向图：只有当图形是时，这里才存在解决方案强关联（有快速测试为了这）。要找到解决方案，请查找O(|E|)计算每个顶点的入度和出度之间的差值。然后解决了一个多有限源网络问题：每个节点根据其输入输出差异来生产或消耗流量。该问题已解决，以求最小权重最大流量O(|V|² |E|)时间。沿着一条边的流量是必须插入到它旁边才能形成欧拉图的平行边的数量。欧拉之旅可以在O(|E|)时间使用Hierholzer 算法。 Harold Thimbleby 提供了一个记录良好的 Java 实现（参见 [1]，还有他的website).
具有有向边和无向边的图：这个问题是NP完全问题。即使图表是这样，它仍然如此planar，节点的总度数最多为 3，所有边的成本等于 1。这就是说，即使在严重受限的情况下，混合图也是一个难题。 [9]
无向树图：树的每条边都会被访问两次。有一些快速方法可以确定图是否是树：请参阅this维基页面。
欧拉游览图：欧拉巡演就是CPT。有一些快速方法可以确定图是否为欧拉图：请参阅this维基页面。
必须根据优先级访问边的图: 这是等级制度菲律宾人民党。它并不总是可以解决的。当它是时，它可以是 NP 完全的。但是，在某些条件下，有一个O(N⁵)算法。 [10]
带时间窗口的图表：在此公式中，每条边都与一个时间范围相关联[le,ue]在此期间必须完成边缘。例如，当街道清扫工正在清洁街道并且某些街道被要求在不同时间禁止车辆时，就会出现这样的问题。该问题是NP-hard问题，可以通过约束规划精确解决。 [11]
你不需要访问所有的边缘: 这被称为农村邮递员问题。对于有向和无向情况，这个问题都是 NP 困难的。具有有向边和无向边的实例（堆垛机问题) 也是 NP 困难的。请参阅[12]进行评论。
边的代价根据遍历方向的不同而不同: 这被称为有风的邮递员问题。这个问题是NP完全问题。 [13]
[1] Thimbleby, H. 2003。定向中国邮递员问题。软件：实践。专家，33：1081-1096。 doi：10.1002/spe.540
[2] 关美高. 1962. 使用奇数点或偶数点的图形编程，中国数学 1，第 273-277 页。
[3] Edmonds, J., Johnson, E.L., 1973。匹配、欧拉之旅和中国邮递员。数学规划 5, 88–124。
[4] Galil, Z.、Micali, S.、Gabow, H. 1986。用于在一般图中查找最大加权匹配的 O(EV log V) 算法。 SIAM J.Comp。 15、120-130。
[5] Grötschel, M., Yuan, Y., 2012。欧拉、关美子、柯尼斯堡和一位中国邮递员。优化故事 43.
[6] Michaels, J.G., 1991。第 20 章：中国邮递员问题，载于：离散数学的应用。麦格劳-希尔高等教育，第 354-364 页。
[7] Laporte, G., 2014。第 3 章：无向中国邮递员问题，见：弧路由。第 53–64 页。
[8] Eiselt, H.A.、Gendreau, M.、Laporte, G., 1995。弧路由问题，第一部分：中国邮递员问题。运筹学 43, 399–414。
[9] Papadimitriou, C.H., 1976。关于边缘遍历的复杂性。 ACM 杂志 (JACM) 23, 544–554。 （如果这个Papadimitriou的名字看起来很熟悉，可能你认出他是《星球大战》中的角色）逻辑混合).
[10] Dror, M.、Stern, H. 和 Trudeau, P. (1987)，Postman 在弧上具有优先关系的图上游览。网络，17：283-294。 doi:10.1002/net.3230170304
[11] U. F. AMINU 和 R. W. EGLESE，针对具有时间窗口的中国邮递员问题的约束规划方法，计算机与运筹研究，33 (2006)，第 3423–3431 页。
[12] Eiselt, H.A.、Gendreau, M.、Laporte, G.，1995。弧路由问题，第二部分：农村邮递员问题。运筹学 43, 399–414。
[13]关美谷(1984)，“关于大风邮差问题”，离散应用数学，9(1)：41-46，doi：10.1016/0166-218X(84)90089-1，MR 754427。
