我一直在四处寻找，但似乎每个人最喜欢的问题的情况略有不同：TSP、哈密顿量、欧拉等。我有一个图，由 V（顶点）和 E（边）表示，其中每条边是无向的，并且有一定的遍历成本。我想以最低的成本遍历每一条边，并可能重复。
直观地说，这个问题感觉是 NP-hard，因为它与其他 NP-hard 问题非常相关。但是，我意识到由于路径可以重复边缘，因此可能更容易。
我的第一个想法是将边转换为顶点，将顶点转换为节点，并尝试像哈密顿量一样对其进行分析。但是，这具有只能访问每个节点一次的限制，并且我找不到任何关于放宽可以多次访问节点的问题的信息。
有谁知道我是否只是不擅长搜索并且这实际上是一个已知和研究的问题？
这是什么
您正在考虑中国邮递员问题，也称为路线检查问题或邮递员之旅。
它能做什么
该问题要求至少访问每个边一次的图的最短/最小成本之旅。这称为中国邮递员之旅 (CPT)解决此问题允许您在其他应用程序中：
找到校车或邮件递送的最佳路线，其中必须访问所有街道以接送乘客/投递邮件，并且公共汽车不限于仅访问街道一次。其他示例包括扫雪机路线、高速公路部门在街道上画线，或者警车试图在节拍中访问每条街道。
表征机器的复杂性和/或优化测试该机器。例如，按下电话上的按钮就像在状态之间采取有向边。菜单出现，菜单关闭。如果您知道手机可能处于的所有状态，那么求解 CPP 将为您提供测试所有状态转换的最佳计划。该计划的长度是机器复杂性的度量。例如，诺基亚 2110 手机的菜单子系统包含 88 个菜单项和 273 个操作。该系统的 CPT 有 515 次按键长度。[1]
无向图
这是最初的问题，由Mei-Ko Kwan在 1960 年提出。他的论文在 1962 年被翻译成英文。 [2] 此后不久，表明该问题可以简化为匹配，因此可以在多项式时间内使用线性规划。[3] Grötschel 等人。给出一个很好的小历史。[5]
要解决此问题，请注意该图必须是单个连通分量。
如果图是单个连接组件并且所有节点的度数相等，则图具有欧拉路径。可以使用Hierholzer 算法在O(|E|)时间内找到该路径。如果不是所有的节点都具有相同的度数，那么我们需要一个更强大的算法。
观察如果一个图有两个奇数度的节点，添加连接它们的额外边将导致一个多重图，其中每个节点都有偶数度。根据上述，这样的图具有易于找到的欧拉路径。进一步：无论采取哪条路线，必须经过多次的边将连接奇数度的两个节点。原因很容易理解：向其中一个奇数度节点添加一条边使其成为偶数度，但使入射在该边上的另一个节点具有奇数度。获得只有偶度节点的图的唯一方法是在两个奇度节点之间建立一条路径。为了最小化多重图上欧拉路径的成本，我们应该在两个奇数度节点之间沿着最小成本路径添加额外的边。这可以通过，比如说，Dijkstra 算法。
现在，假设我们有2n奇数节点。通过对上述内容的一些思考，您可以说服自己，您将需要n连接这些顶点对的不同的、不重叠的路径。知道了这一点，解决问题的一种方法是使用Floyd-Warshall 算法在O(|V|³)时间内计算奇数度节点之间的所有对最短路径。然后可以在 O(|E|*|V| log |V|)时间内找到最大加权匹配。[4]
Michaels 对此有一个简单的文章以及一些直观的证明。[6] Laporte 提供了更技术性的描述，将匹配问题转换为线性整数程序。[7] 艾瑟尔特等人。给出另一个技术描述以及对相关问题的相当广泛的审查（见下文）。[8]
其他一些变体
由于我们总是只需要一个想法就可以使算法问题变得更难，这里有一些可能会引起兴趣的变体：
完全有向图：只有当图是强连接时才存在解决方案（对此有快速测试）。要找到解决方案，请在O(|E|)时间内计算每个顶点的入度和出度之间的差异。然后解决了一个多有限源网络问题：每个节点根据其输入输出差异产生或消耗流量。在O(|V|² |E|)时间内解决了最小权重最大流的问题。沿边的流动量是平行边的数量，必须在边上插入这些平行边以形成欧拉图。然后可以使用Hierholzer 算法在O(|E|)时间内找到欧拉之旅. Harold Thimbleby 提供了一个文档齐全的 Java 实现（参见 [1]，还有他的网站）。
具有有向和无向边的图：这个问题是 NP-Complete。即使图是平面图，节点的总度数最多为 3，并且所有边的成本等于 1，它仍然如此。也就是说，即使在严重受限的情况下，混合图也是一个难题。[9]
无向树图：树的每条边被访问两次。有一些快速方法可以确定图表是否为树：请参阅此wiki 页面。
带有欧拉环的图：欧拉环是 CPT。有一些快速方法可以确定图是否为欧拉图：请参阅此wiki 页面。
必须根据优先级访问边的图：这是分层CPP。它并不总是可以解决的。如果是，它可以是 NP 完全的。但是，在某些条件下，存在O(N⁵)算法。[10]
带时间窗的图：在这个公式中，每条边都与[le,ue]必须完成边的时间范围相关联。例如，当清道夫正在清扫街道并且要求某些街道在不同时间禁止车辆通行时，就会出现这样的问题。这个问题是 NP 难的，可以通过约束规划精确地解决。[11]
你不需要访问所有的边缘：这被称为农村邮递员问题。对于有向和无向情况，这个问题都是 NP-hard。具有有向和无向边的实例（堆垛机问题）也是 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, EL, 1973. Matching、Euler tours 和中国邮递员。数学编程 5, 88–124。
[4] Galil, Z., Micali, S., Gabow, H. 1986。在一般图中寻找最大加权匹配的 O(EV log V) 算法。暹罗学家比较。15、120-130。
[5] Grötschel, M., Yuan, Y., 2012. Euler, Mei-ko Kwan, Königsberg, and a Chinese Postman。优化故事 43.
[6] Michaels, JG, 1991. 第 20 章：中国邮递员问题，载于：离散数学的应用。麦格劳-希尔高等教育，第 354-364 页。
[7] Laporte, G.，2014 年。第 3 章：无向中国邮递员问题，载于：弧形路由。第 53-64 页。
[8] Eiselt, HA, Gendreau, M., Laporte, G., 1995。弧路由问题，第一部分：中国邮递员问题。运筹学 43, 399–414。
[9] Papadimitriou, CH, 1976。关于边缘遍历的复杂性。ACM 杂志 (JACM) 23, 544–554。（如果这个 Papadimitriou 的名字看起来很眼熟，那可能是你认出他是Logicomix中的一个角色）。
[10] Dror, M.、Stern, H. 和 Trudeau, P. (1987)，Postman tour on a graph with priority relationship on a arcs。网络，17：283-294。doi:10.1002/net.3230170304
[11] UF AMINU AND RW EGLESE, A constraint programming approach to the Chinese postman problem with time windows, Computers & Operations Research, 33 (2006), pp. 3423–3431.
[12] Eiselt, HA, Gendreau, M., Laporte, G., 1995。弧形路由问题，第二部分：农村邮递员问题。运筹学 43, 399–414。
[13] 关美谷（1984），《论有风的邮递员问题》，离散应用数学，9（1）：41-46，doi：10.1016/0166-218X（84）90089-1，MR 754427。