跳转到内容

中国邮递员问题

维基百科,自由的百科全书

中国邮递员问题(也称路线检查问题,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} 边重复,所有的端点均有偶数边通过。不过增加的长度不一定最少。

所有奇数边端点组成的完全图。

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

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

因此原来的图中,连接端点 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). 

参见

[编辑]

外部链接

[编辑]