下载文档原格式
关于中国邮递员研究的回顾与发展管梅谷复旦大学管理学院摘要：本文回顾了中国邮递员问题产生的历史背景和过程，指出了该问题名称的来源，综述了求解中国邮递员问题的算法，最后指出了该问题的发展。
关键词：中国邮递员问题，奇偶图上作业法，NP-CompleteThe Origin of Chinese Postman ProblemGuan MeiguSchool of Management, Fudan UniversityAbstract: This paper describes the historical background about Chinese Postman Problem (CPP) which was introduced by Guan Meigu and named by J.Edmonds. The algorithms to solve CPP are also surveyed.Keywords: Chinese Postman Problem, Graphic Programming Using Odd or Even Points, NP-Complete（1）引言在数学史上，以中国命名的问题或定理出现得不多。
有一个“中国余数定理”是广为人知的，就是，如果一个正整数n（≤105）被3、5、7除的余数都已知道，n就可以被唯一的决定了。
这个定理在一千多年前就知道了。
不过，在近代，又出现了一个以中国命名的问题，那就是“中国邮递员问题”（Chinese Postman Problem，以下简称CPP）。
这个问题就是：一个邮递员每次上班，要走遍他负责送信的所有街道，最后回到邮局，问应该怎样走才能使所走的路程为最短。
这个问题之所以被称为“中国邮递员问题”，可以想象是在中国并且是由中国人最早提出的。
事实也正是如此。
CPP最早出现在我写的“奇偶点图上作业法”（见【1】）一文中。
这篇文章中还给出求解这个问题的一个算法，就是奇偶点图上作业法。
中国邮递员问题解法中国邮递员问题是一个著名的组合优化问题，实际上是一个旅行商问题（Traveling Salesman Problem，TSP）的变种。
问题描述：给定一个城市集合和城市之间的距离矩阵，求解一个最短的邮递员路径，使邮递员能够从出发城市出发，经过每个城市恰好一次，最后回到出发城市。
解法：1.暴力搜索暴力搜索是最简单直观的解法。
遍历所有可能的路径，计算每个路径的总距离，最后选择最短的路径。
这种解法的时间复杂度为O(n!)，随着城市数量的增加而急剧增加，效率非常低，只适用于小规模问题。
2.动态规划动态规划是一个更高效的解法。
使用一个二维数组dp[i][j]表示从城市i出发经过城市集合j的最短路径长度，其中j是一个二进制数，表示哪些城市已经访问过。
动态规划的转移方程为：dp[i][j] = min{dp[k][j XOR (1 << k)] + distance[i][k]}，其中k表示已经访问的最后一个城市。
利用这个递推关系，可以逐步计算出dp[0][1<<n-1]，即从城市0出发经过所有城市的最短路径。
最后，将此路径与每个城市的距离相加，得到最终的最短路径长度。
3.贪心算法贪心算法是一种更简单的解法。
首先选择一个起始城市，然后每次选择距离最近且未被访问过的城市，将其加入路径中。
重复此过程，直到访问完所有城市，然后回到起始城市。
这种解法的时间复杂度为O(n^2)，但由于贪心策略的局限性（可能会出现回头或死胡同），所以得到的解并不一定是最优解。
以上是三种常用的解决中国邮递员问题的方法，具体可以根据实际情况选择合适的算法进行求解。
中国邮递员模型研究一、 中国邮递员问题概述著名图论问题之一。
邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。
在此条件下，怎样选择一条最短路线?关于邮递员最优投递路线问题最早是由管梅谷首先提出并进行研究的, 国际上现在统称之为中国邮递员问题。
管梅谷给出了这一问题的奇偶点图上作业法。
Edmonds 等给出了中国邮递员问题的改进算法, 较前者的计算更为有效。
管梅谷对有关中国邮递员问题的研究情况进行了综述。
早期关于中国邮递员问题的讨论总是基于无向图展开的,事实上,由于单行线或上下行路线的坡度等原因, 这一问题有时必须借助于有向图来进行研究和解决。
到目前为止,对中国邮递员问题的研究主要是从图论角度展开的, 给出的多数都是各种启发式算法或递推算法。
本文从数学规划的角度进行研究。
数学规划建模具有借助软件包求解方便、 易于修改和推广等多方面的优点,即使对于大型问题也易于建模分析和解决的优点。
1、 传统中国邮递员问题的建模 一些基本概念:定义 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E 回路；含Euler 回路的图叫做Euler 图。
直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。
定理（i ）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次。
（ii ）G 是Euler 图的充分必要条件是G 连通且 di i C G 1==，i C 是圈，)()()(j i C E C E j i ≠Φ= 。
（iii ）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点。
问题（管梅谷，1960） ：一位邮递员从邮局出发投递邮件，经过他所管辖的每条街道至少一次，然后回到邮局。
请为他选择一条路线，使其所行路程尽可能短。
图论模型：求赋权连通图中含有所有边的权最小的闭途径。
这样的闭途径称为最优回路。
思想：（1）若 G 是 Euler 图，则 G 的 Euler 环游便是最优回路，可用 Fleury 算法求得；（2）若 G 不是 Euler 图，则含有所有边的闭途径必须重复经过一些边，最优回路要求重复经过的边的权之和达到最小。
闭途径重复经过一些边，实质上可看成给图 G 添加了一些重复边（其权与原边的权相等） ，最终消除了奇度顶点形成一个 Euler 图。
因此，在这种情况下求最优回路可分为两步进行：首先给图 G 添加一些重复边得到 Euler 图*G ，使得添加边的权之和()e Fw e ∈∑最小， （其中()()*\F E G E G = ） ；然后用 Fleury 算法求*G 的一条 Euler 环游。
这样便得到 G 的最优回路。
问题是：如何给图 G 添加重复边得到 Euler 图*G ，使得添加边的权之和()e Fw e ∈∑ 最小？方法一（图上作业法）定理1设 C 是一条经过赋权连通图 G 的每条边至少一次的回路，则 C 是 G 的最优回路当且仅当 C 对应的Euler 图*G 满足： （1）G 的每条边在*G 中至多重复出现一次；（2）G 的每个圈上在*G 中重复出现的边的权之和不超过该圈总权的一半。
奇偶点图上作业法：先分奇偶点，奇点对对联；联线不重迭，重迭要改变；圈上联线长，不得过半圈。
基本步骤：1、确定第一个可行方案。
找到图中所有奇顶点（必有偶数点）将它们两两配对。
新图中无奇顶点，得到第一个可行方案。
2、调整可行方案，使重复边总长度下降。
3 检查图中的每个圈，如果每个圈重复边总长度不超过该圈总长度的一半，则已求得最优解。
否则进行调整：将这个圈的重复边去了，而将原来没有重复边的各边加上重复边，其他各圈的边不变，根据 2 再一次调整。
奇偶点图上作业法虽然通俗易懂，但使用时需要检查图的每个圈，对于有很多圈的图，计算量很大，实际当中用得较少。
方法二（Edmonds-Johnson 方法）定理2设 G 是赋权连通图，G 中有2k 个奇度顶点。
设 {}|,e A e e E =∈求最优回路时被添加重复边则[]G A 是以G 的奇度顶点为起点和终点的k 条无公共边的最短路。
基于此定理，Edmonds 和 Johnson 于 1973 年给出了求解邮递员问题的有效算法。
Edmonds-Johnson 算法：对于非Euler 图，1973年，Edmonds 和Johnson 给出下面的解法： 设G 是连通赋权图。
（i ）求)}2(m od 1)(),(|{0=∈=v d G V v v V 。
（ii ）对每对顶点0,V v u ∈，求),(v u d （),(v u d 是u 与v 的距离，可用Floyd 算法求得）。
（iii ）构造完全赋权图||0V K ，以0V 为顶点集，以),(v u d 为边uv 的权。
（iv ）求||0V K 中权之和最小的完美对集M 。
（v ）求M 中边的端点之间的在G 中的最短轨。
（vi ）在（v ）中求得的每条最短轨上每条边添加一条等权的所谓“倍边”（即共端点共权的边）。
（vii ）在（vi ）中得的图'G 上求Euler 回路即为中国邮递员问题的解。
若此连通赋权图是Euler 图，则可用Fleury 算法求Euler 回路，此回路即为所求。
Fleury 算法：（1）任取()()0v V G ∈，令00P v =.（2）设0112...i i i P v e v e e v =已经行遍，按下面方法来从(){}12,,...,i E G e e e -中选取1i e +：（a ）1i e +与i v 相关联；（b ）除非无别的边可供行遍，否则1i e +不应该为{}12,,...,i i G G e e e =-中的桥。
（3）当（2）不能再进行时，算法停止。
2、 利用LINGO 中国邮递员0-1规划求解在中国邮递员问题中，不算出地点，n 个邮局有(n-1)!种排列方法，每一种投递路线是排列中的一种，当n 变大时，计算量呈指数增长，穷举法所费时间是难以承受的。
我们把中国邮递员问题转化为0-1规划，然后用LINGO 来求解。
(1). 判断各边包含在投递路线中引入0-1整数变量i j x (且i ≠j ):i j x =1表示路线从i 到j ，即边i-j 在旅行路线中，而i j x ＝0则表示不走i-j 路线。
目标函数：首先必须满足约束条件：对每个投递点访问一次且仅一次。
从投递点i 出发一次(到其它投递点去),表示为从某个投递点到达j 一次且仅一次，表示为以上建立的模型类似于指派问题的模型，对中国邮递员问题只是必要条件，并不充分。
例如，用图示路线连接六个点，满足以上两个约束条件，但这样的路线出现了两个子回路，两者之间不通，不构成整体巡回路线。
11min nnij iji j z c x ===∑∑11,1,2,,,ni jj xi n j i===≠∑11,1,2,,,ni ji xj n i j===≠∑为此需要考虑增加充分的约束条件以避免产生子巡回增加变量i u ,i=2,3,…,n ，（它的大小可以取整数：例如从起点出发所达到的投递点u=2,依此类推）。
1,1,...,,2,...,,i j i j u u nx n i n j n i j -+≤-==≠附加约束条件：证明：(1)任何含子巡回的路线都必然不满足该约束条件（不管i u 如何取值）； (2)全部不含子巡回的整体巡回路线都可以满足该约束条件（只要i u 取适当值）。
用反证法证明(1),假设存在子巡回，则至少有两个子巡回。
那么（必然）至少有一个子巡回中不含起点1，如上图中的4－5－6－4，则必有4554641,1,1u u n n u u n n u u n n -+≤--+≤--+≤-把这三个不等式加起来得到1n n ≤-，不可能，故假设不能成立。
而对整体巡回，因为附加约束中j ≥2,不包含起点投递点1，故不会发生矛盾。
对于整体巡回路线，只要ui 取适当值，都可以满足该约束条件： (ⅰ)对于总巡回上的边，1i j x =, i u 可取访问投递点i 的顺序数，则必有1i j u u -=-，约束条件1i j i j u u nx n -+≤-变成：-1+n ≤n-1，必然成立。
(ⅱ)对于非总巡回上的边，因为0i j x = ，约束条件1i j i j u u nx n -+≤-变成-1≤n-1，肯定成立。
综上所述，该约束条件只限止子巡回，不影响其它，于是中国邮递员问题转化成了一个混合整数线性规划问题。
中国邮递员问题可以表示为规划：例1 有一个县城，有五个乡邮局，现在又一个邮车从县邮局出发派送物品，如何为这个邮车设计一条最短的派送路线（从驻地出发，经过每个投递点恰好一次，最后返回驻地）？（数据在下表中）11minn nij iji j z c x ===∑∑111,1,2,,,1,1,2,,,1,1,,,2,,,0,1,,1,2,,,0,1,2,,n i j i n i j j i j i j ij i x j n i j x i n j i u u nx n i n j n i j x i j n u i n ==⎧==≠⎪⎪⎪⎪==≠⎨⎪-+≤-==≠⎪⎪==≥=⎪⎩∑∑（单位：千米）Lingo代码：model:sets:country/1,2,3,4,5,6/:u;！定义6个点 link(country,country):dist,！距离矩阵x;！决策变量endsetsn= @size( country);data: ！距离矩阵dist=0 3 4 7 9 53 0 6 22 11 164 6 0 33 21 557 11 33 0 17 109 16 21 17 0 135 22 55 10 13 0;enddata！目标函数min=@sum(link:dist*x);@FOR( country(K):！进入邮局@sum( country( I)| I #ne# K: x(I,K))=1;！离开邮局@sum( country( j)| J #ne# K: x(K,J))=1;);！保证不出现子圈@FOR( country(I) | I #gt# 1:@FOR( country( J)| j #gt# 1:u(I)-u(J)+n*x(I,J)<=n-1););@FOR( country(I) : u(I)<=n-1);@FOR( link:@bin(x));！定义0-1变量END运算结果：Objective value: 53.00000X( 1, 3) 1.000000 4.000000X( 2, 4) 1.000000 11.00000X( 3, 2) 1.000000 6.000000X( 4, 6) 1.000000 10.00000X( 5, 1) 1.000000 9.000000X( 6, 5) 1.000000 13.00000由此可以看出最优解为 53千米路线为：1-3-2-4-6-5-12.对投递点进行排序，找出最优排序在现实中的交通图中，有些投递点之间有直接道路，有些则没有，如果两点之间没有直接的通路，则两点之间的距离取最短路（经过其它点），即用任意两C作为图的距离矩阵，于是该图可以看成是一个完全图（即任点之间的最短路i j意一对顶点都有一条边相连的图），此时形式上的环形巡回路线实际上个别点有可能不止经过一次。
