Route Inspection (Chinese Postman Problem) | 路径检查（中国邮递员问题）

2026-08-21 14:02 · 本文部分内容由AI辅助创作

📚 Route Inspection (Chinese Postman Problem) | 路径检查（中国邮递员问题）

Route inspection, often called the Chinese Postman Problem, is a fundamental topic in Decision Mathematics. It asks how to traverse every edge of a connected network at least once while returning to the start, covering the shortest possible total distance.

路径检查（常称为中国邮递员问题）是决策数学中的基础主题。它研究如何在连通网络中至少遍历每条边一次并返回起点，同时使总路程最短。

1. What is Route Inspection? | 什么是路径检查？

In a connected graph, a route that travels along each edge at least once and returns to the start is called a route inspection or postman route. The aim is to minimise the total weight of the route when edges have lengths or costs.

在连通图中，沿着每条边至少走一次并回到起点的路线称为路径检查路线或邮递员路线。当边有长度或成本时，目标是使路线的总权值最小。

The problem appears in real situations such as refuse collection, gritting roads, street sweeping, and mail delivery.

该问题出现在实际场景中，如垃圾清运、道路撒沙、街道清扫和邮件投递。

2. Key Terms: Eulerian and Semi-Eulerian Graphs | 关键术语：欧拉图与半欧拉图

A graph is Eulerian if every vertex has even degree. An Eulerian circuit exists: a closed trail that uses every edge exactly once with no repeats.

如果图中每个顶点的度数都是偶数，则该图是欧拉图。欧拉回路存在：一条闭合路径恰好使用每条边一次且不重复。

A graph is semi-Eulerian if exactly two vertices have odd degree. An Eulerian trail exists that starts at one odd vertex and ends at the other, using every edge exactly once.

如果图中恰好有两个奇度顶点，则该图是半欧拉图。存在欧拉路径，从一个奇度顶点出发到另一个奇度顶点结束，恰好使用每条边一次。

The degree of a vertex is the number of edges incident to it. A loop, if present, contributes 2 to the degree.

顶点的度数是与它相连的边数。如果存在环，则环对度数的贡献为 2。

In any graph, the number of odd-degree vertices is always even.

在任何图中，奇度顶点的数量总是偶数。

3. The Chinese Postman Problem | 中国邮递员问题

The Chinese Postman Problem was studied by the Chinese mathematician Kwan Mei-Ko in 1960. It asks for the shortest closed walk that covers every edge at least once.

中国邮递员问题由数学家管梅谷于1960年研究。它要求寻找覆盖每条边至少一次的最短闭合行走路线。

If the network is already Eulerian, the shortest route is simply the total weight of all edges, because every edge can be traversed exactly once.

如果网络已经是欧拉图，最短路线就是所有边的总权值，因为每条边可以恰好被走一次。

If the network has odd vertices, some edges must be repeated to make all vertex degrees even. The challenge is to choose repeats with minimum total weight.

如果网络存在奇度顶点，则必须重复某些边以使所有顶点度数变为偶数。难点在于选择总权值最小的重复方案。

广告 / Sponsored

京东精选

4. Step-by-Step Algorithm | 路径检查算法步骤

Step 1: List all vertices with odd degree in the original connected network.

步骤1：列出原连通网络中所有奇度顶点。

Step 2: Find the shortest path distances between every pair of odd vertices, using Dijkstra's algorithm or inspection on small networks.

步骤2：使用 Dijkstra 算法或在小网络上直接观察，找出每对奇度顶点之间的最短路径距离。

Step 3: Consider all perfect pairings of the odd vertices. Each pairing pairs up two odd vertices, and the cost is the shortest distance between them.

步骤3：考虑奇度顶点的所有完美配对。每个配对将两个奇度顶点配成一对，其成本是它们之间的最短距离。

Step 4: Choose the pairing with the smallest total cost. The repeated edges are exactly the edges on the shortest paths in that pairing.

步骤4：选择总成本最小的配对。重复的边正是该配对中最短路径上的边。

Step 5: Add the repeated edges to the network. Every vertex now has even degree, so an Eulerian circuit can be found.

步骤5：将重复的边添加到网络中。现在每个顶点都具有偶数度数，因此可以找到欧拉回路。

Step 6: The optimal route length equals the sum of all original edge weights plus the total weight of the repeated edges.

步骤6：最优路线长度等于所有原边权之和加上重复边的总权值。

Total route length = sum of all original edge weights + minimum pairing cost

总路线长度 = 所有原边权之和 + 最小配对成本

5. Pairing Odd Vertices | 奇度顶点的配对

Because the number of odd vertices is even, they can always be paired. If there are 2k odd vertices, the number of possible pairings is (2k−1)(2k−3)···1.

由于奇度顶点数量为偶数，它们总可以配对。如果有 2k 个奇度顶点，可能的配对数为 (2k−1)(2k−3)···1。

For four odd vertices A, B, C, D, the three pairings are (A,B)+(C,D), (A,C)+(B,D), and (A,D)+(B,C).

对于四个奇度顶点 A、B、C、D，三种配对为 (A,B)+(C,D)、(A,C)+(B,D) 和 (A,D)+(B,C)。

You must use the shortest distances between vertices, not just direct edge weights, because the repeated route may pass through intermediate even vertices.

必须使用顶点之间的最短距离，而不仅仅是直接边的权重，因为重复路线可能经过中间偶数度顶点。

If two shortest paths share an edge, that edge may be repeated twice, which is equivalent to adding two copies. This is allowed in the augmented graph.

如果两条最短路径共享一条边，该边可能被重复两次，相当于添加两条副本。这在增强图中是允许的。