中国邮递员问题小论文

中国邮递员问题摘要：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题本文主要介绍了中国邮递员问题的基本分析、求解中国邮递员问题的方法以及有关欧拉回路的算法实现。关键词：中国邮递员 欧拉图 欧拉回路一、中国邮递员问题的分析中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”。在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即：“一个售货员要到n个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”。这是一个著名的难题.当n较大时，即使使用大型电子计算机，也很难解决 。投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”(这个问题是我国数学家管梅谷先生在20世纪60年代提出来的)用图论的语言来描述就是在一个带权图G中，能否找到一条回路C，使C包含G的每条边至少一次且C的长度最短？如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少一遍，这时用中国邮路问题算法可求出最短路径。此问题求解的关键点分析：(1)若G没有奇度数结点，则G是欧拉图，于是欧拉回路C是惟一的最小长度的投递路线。(2)若G恰有两个奇度数结点Vi和Vj，则G具有欧拉迹，且邮局位于结点Vi，则邮递员走遍所有的街道一次到达结点Vj；从Vj返回Vi可选择其间的一条最短路径。这样，最短邮路问题转化为求Vi到 Vj的欧拉迹和Vj到Vi的最短路径问题。(3)若 G 中奇数度结点的数目多于2，则回路中必须增加更多的重复边( 路径)。这时，怎样使重复边的总长度最小？二、三种情况的具体思路1、若G没有奇度数结点，则G是欧拉图，则欧拉回路是唯一的最小长度投递路线。此时可以利用求欧拉回路的Fleury算法求解。步骤为：任意选取一个顶点V0、使W0=V0。假设迹Wi=V0e1V1eiVi已经确定，那么按照下述方面从E/e1,e2,ei中选取边ei+1。a、 ei+1和Vi相关联b、 除非没有别的边可选择，否则ei+1不是G=G-e1,e2,ei的割边c。当不能再继续时，停止。2、 若G恰有两个奇度数结点若G只有两个奇点Vi,Vj则有从Vi到Vj的欧拉迹，从Vj回到Vi则必须重复一些边，使重复边的总长度最小，转化为求从Vi到Vj的最短路径。算法如下：找出奇点Vi,Vj之间的最短路径P；令G， = G + P；G，为欧拉图，G，的欧拉回路即为最优邮路。3、 G 中奇数度结点的数目多于2 求解中国邮递员问题的传统方法是通过计算奇度数结点之间的最短路径来确定结点配对，添加重复边。但是，从上面定理的结论可以看出，当图中的奇度数结点数目较多时，其计算量将非常大。因此，我们可以考虑，既然核心问题是要解决奇度数结点的配对问题并在奇度数结点之间添加重复边，那么不妨将原始图中的偶度数结点去掉，只考虑奇度数结点，并利用最小生成树的观点来快速地找出奇度数结点的最优配对方案。具体思路如下：去掉原始图中的偶度数结点，即得到的新图中只包含原奇度数结点与它们之间的路径；求新图的最小生成树；由最小生成树确定奇度数结点的配对；在原始图中添加重复边。例 求解如图1 所示的中国邮递员问题。解 如图 1 所示，该中国邮递员问题共有 8 个奇度数结点，即 V2，V4，V5，V6，V7，V8，V10，V12。 图1 去掉图 1 中的偶度数结点，得到新图 2。 图2求图 2 的最小生成树(如图 3 所示)。 图3由图 3 可知 V2与 V6配对，V4与 V8配对，V5与 V1 2配对，V7与 V10配对。根据奇度数结点的配对在原始图1中添加重复边(如图 4 所示)，经检验此方案已是最优。图4 这种方法为求解多奇数度点的情况提供了一种很完整又相对简便的解法。