下载文档原格式
§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。
1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。
2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。
城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。
3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。
伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。
对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。
我们将这些重复的边组成的集合称可行集，即找最小的可行集。
命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。
中国邮递员问题第一篇：中国邮递员问题运筹学第六组运筹学个人心得之中国邮递员问题我们第六组做的第二次案例就是中国邮递员问题，这个问题是运筹学中的经典命题。
这个案例讲的是：在中国的六个县城，每个县城都有一个县局，县局下面设立若干个邮政所，每天邮递员的任务就是从县局出发，依次到每一个邮政所送邮件，要求每个邮政所都必须去，而且只能去一次。
这就涉及到一个路线的规划问题，怎么走才能使得邮递员走的路最少，而且能够完成任务。
在做题之前考虑了很久，真不知道从何着手，国为以前确实没有接触过这个类型的题，没有一个能够行得通的办法。
后来，我们选定了一个代表性的区域，来尝试求解，国为第六个区域的变量最多，所以就选择这个区域作为突破口。
只要第六个区域求解成功，其它五个区域便迎刃而解了。
首先，我们画了一个由第六区域的十七个点所组成的17*17矩阵，一一对应设定变量，在去除对角线的17个变量之后，我们得到272个变量。
这是一个非常庞大的变量群体，若按传统的线性规划方法求解，求解过程将会变得异常艰辛，而且以前的模板，求解工具都不能求解这么多变量。
所以我们一度陷入混乱，求解工作停滞不前。
后来老师在对这价目案例作初步的讲解的时候，提出了用运输模型来对这个问题进行求解，此话一出，真是如醍醐灌顶，酣畅极了，眼前简直豁然一亮，真想“拍案而起”。
若用运输模型求解，这个问题将会变得非常简单。
一方面由于每行的出发点只能有一个，而每列的终点也只能有一个，这样看来，邮运筹学第六组递员总是变成了一个产销平衡的运输问题，产量和销量都有是1。
这样我们就完成了求解工作，在第一次求解得出结论后，我们画了一个路线图，发现有几个两点循环，没有形成一条大通路，于是我们重新加入了两点循环约束，进行二次求解；在第二次求解完成后，我们又重新画了路线图，结果发现有四点循环于是我们又加入四点循环约束，进行第三次求解，在得到第三次求解的结果后，我们又画出了路线图，这次刚好形成了一个完整的通路，保证了邮递员每点都走到且行走的路线最合理。
§4.中国邮递员问题（Chinese Postman Problem）1．问题的提出例5. 一个邮递员从邮局出发投递信件, 然后再返回邮局, 如果他必须至少一次地走过他负责投递范围内的每条街道, 街道路线如下图所示, 问选择怎样的路线才能使所走的路为最短?5 6 78问题的图论表述：在赋权G=[V, E]上找一条经每条边至少一次的权最小的圈。
1960年山东师范学院管梅谷教授首先提出此问题，并设计了一个“奇偶点表上作业法”，后来发现此法不是多项式算法，1973年，Edmonds和Johnson给出一个多项式算法。
2．哥尼斯堡七桥问题18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥，将河中的两个岛和河岸连结，如下图所示。
城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。
3．Euler圈Euler圈：经图G的每条边的简单圈Euler图：具有Euler圈的图Euler图非Euler图下面讨论的图G允许有重边，且重边被认为是有区别的边。
伪Euler 圈：经图G 的每条边至少一次的圈点v 的次：与点V 关联的边的数目奇(偶)点：该点的次为奇(偶)数命题1：G 的奇点个数为偶数命题2：G 中有伪Euler 圈 ⇔ G 无奇点中国邮递员问题可表述为：在图G 中找一条权最小的伪Euler 圈。
对于邮递员来说，有些街道可能会重复走，原问题便转化为尽可能少走重复的 街道。
我们将这些重复的边组成的集合称可行集，即找最小的可行集。
命题3：E *是最小可行集 ⇔ωωμμμ()()()()*()*()e e e E E E e E E ≤∑∑∀μ∈∩∈∩\初等圈重复的边 非重复的边4．算法思路由命题1，简单图G 的奇点个数为偶数，可设为v 1 , v 2 , …, v 2k , 对每个1≤ i ≤k, 找v 2i − 1 至v 2i 的链p i ，将p i 的边重复一次。
中国邮递员问题摘要：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局．如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程．这个问题是由我国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的，因此在国际上称之为中国邮递员问题本文主要介绍了中国邮递员问题的基本分析、求解中国邮递员问题的方法以及有关欧拉回路的算法实现。
关键词：中国邮递员欧拉图欧拉回路一、中国邮递员问题的分析中国投递员问题是1960年我们从生产实际中提出的一个数学问题，它是从下述实际问题中抽象出来的：“一个投递员应该怎么选择一条线路，才能既把所有由他负责的信件都送到，而所走的路程又最短”。
在我们开始研究中国投递员问题以前，国外有人研究过所谓旅行售货员的问题，即：“一个售货员要到n个城市去售货，问他应该选择怎样的一条线路，才能既走遍所有城市，并且走的路程最短”。
这是一个著名的难题.当n较大时，即使使用大型电子计算机，也很难解决。
投递员面临的问题显然可以归纳为旅行售货员问题，事实上，只要把投递员必须送的每一个地点看成是一个城市就行了.但是一般来说，投递员每次要到约二、三百个地点送信，如果归纳为旅行售货员问题来解决，将是一个规模很大的问题，是无法解决的.但是，在仔细分析了投递员面临的问题后，我们发现这个问题具有一定的特点，即需要送信的地点一般都是比较密集的排列在街道上的，因此，实际上，我们称这个问题为“最短投递线路问题”，1965年后国外称之为“中国投递员问题”(这个问题是我国数学家管梅谷先生在20世纪60年代提出来的)用图论的语言来描述就是在一个带权图G中，能否找到一条回路C，使C包含G的每条边至少一次且C的长度最短？如若他所管辖的街道构成一欧拉回路，则这欧拉回路便是所求路径。
如若不然，即存在度数为奇数的顶点，必然有些街道需要多走至少一遍，这时用中国邮路问题算法可求出最短路径。
中国邮递员数学问题
中国邮递员数学问题是一个著名的数学问题，也称为"中国邮递员问题"。
这个问题源于邮递员在担任邮递员工作时，需要沿着不同的街道进行投递。
邮递员必须走遍每一条街道至少一次，然后回到出发地点。
问题的目标是寻找一条最短的路径，使得邮递员能够满足投递的要求。
具体问题描述如下：给定一个城市的街道网络图，每条街道上都有一个正整数表示街道的长度。
邮递员需要从一个特定地点出发，沿着街道网络进行投递，然后回到出发地点。
要求邮递员经过的路径总长度最短。
这个问题属于旅行商问题的变种，是一个NP-完全问题。
因为问题规模较大，难以找到一个最优解。
因此，通常采用近似算法进行求解，如TSP（Traveling Salesman Problem）等。
邮递员问题在实际中有很多应用，比如快递员的路线规划、物流配送等。
解决这个问题可以提高物流效率，减少成本。
