中国邮递员问题

中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此问题为在一个连通的无向图中找到一最短的封闭路径，且此路径需通过所有边至少一次。现实意义中，中国邮递员问题就是在一个已知的地区，邮差要设法找到一条最短路径，走过此地区所有的街道，且最后要回到出发点。

此问题是图遍历问题的一种。无向图的中国邮递员问题是容易解决的，是P问题；而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出，而美国国家标准和技术研究院（NIST）的 Alan Goldman 首先将此问题命名为中国邮递员问题。^[1]

无向图上中国邮递员问题的解法

若图中有欧拉回路，因为欧拉回路通过所有的边，因此任何一个欧拉回路即为此问题的解。

若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。因此有些边需要再重复一次，使奇数边的端点变为偶数边的端点。

用图来模拟一个镇的街道，标示红色的路口有奇数条路通过。

假设有一个镇有14条路及9个路口（路口分别编号为 1,2, …,9），其路和路口对应的图（右边第 1 图，边上的数字是各边的 cost）中有4个端点（编号 1, 3, 6 及9）有奇数个边通过，因此这个图不存在欧拉回路。后续要作的在图中使几个边重复，使图中所有的端点均有偶数边通过。例如若图中 {1,3} 及 {6.9} 边重复，所有的端点均有偶数边通过。不过增加的长度不一定最少。

所有奇数边端点组成的${\displaystyle K_{4}}$完全图。

为了要确定重复哪个边可以使原图的端点都有偶数边通过，且增加长度最少。先画出所有奇数边的端点的完全图 ${\displaystyle K_{4}}$ （右边第 2 图），边上的数字是从一端点到另一端点（可以经过其他完全图 ${\displaystyle K_{4}}$ 中省略的点）的最短长度。若选择边 {1,6} 及 {3,9}，所有端点都经过一次，而总长度 ${\displaystyle 4+2=6}$最短。

最后的解，红色部分是新增的边及其对应的长度。

因此原来的图中，连接端点 1 和 6, 端点 3 和 9 的边再重复一次，所有端点均有偶数个边通过（右边第 3 图）。因此任一个欧拉路径即为此问题的解答，如以下的端点顺序 (1,2,3,4,9,3,1,8,7,3,9,7,6,9,5,6,7,8,1) 即为一解。图中红色的部分即为重复的边。

参考文献

1. "Chinese Postman Problem". [2009-02-19]. （原始内容存档于2008-10-17）.

参见

• 一笔画问题
• 汉弥尔顿路径问题
• 旅行推销员问题

外部链接

• Chinese Postman Problem （页面存档备份，存于互联网档案馆）