中国邮递员问题

数学术语

中国邮递员问题是邮递员在某一地区的信件投递路程问题。邮递员每天从邮局出发，走遍该地区所有街道再返回邮局，问题是他应如何安排送信的路线可以使所走的总路程最短。这个问题由中国学者管梅谷在1960年首先提出，并给出了解法——“奇偶点图上作业法”，被国际上统称为“中国邮递员问题”。用图论的语言描述，给定一个连通图G，每边e有非负权)，要求一条回路经过每条边至少一次，且满足总权最小。

定义

一个邮递员从邮局出发，要走完他所管辖范围内的每一条街道，至少一次再返回邮局，如何选择一条尽可能短的路线？这就是中国邮递员问题（CPP），其命名是因为中国数学家管梅谷在1962年首先提出了这个问题。如果用顶点表示交叉路口，用边表示街道，那么邮递员所管辖的范围可用一个赋权图来表示，其中边的权重表示对应街道的长度。

图论语言

中国邮递员问题可用图论语言叙述为：在一个具有非负权的赋权连通图G中，找出一条权最小的环游。这种环游称为最优环游。若G是欧拉图，则G的任意欧拉环游都是最优环游，从而可利用弗勒里算法求解。若G不是欧拉图，则G的任意一个环游必定通过某些边不止一次。将边e的两个端点再用一条权为w(e)的新边连接时，称边e为重复的。此时CPP与下述问题等价，若G是给定的有非赋权的赋权连通图，

（1）用添加重复边的方法求G的一个欧拉赋权母图，使得尽可能小；

（2）求的欧拉环游。

此图论中和中国邮递员问题类似的是旅行商问题，区别于中国邮递员问题，旅行商问题是说在边赋权的完全图中找一个权和最小的哈密尔顿圈。

埃德蒙兹（J.Edmonds）和约翰逊（E.L.Johnson)在1973年给出了求解（1）的多项式时间算法。

如果邮递员所通过的街道都是单向道，则对应的图应为有向图。1973年，埃德蒙兹和约翰逊证明此时CPP也有多项式时间算法。帕帕季米特里屋（C.H.Papadimitrious）在1976年证明，如果既有双向道，又有单向道，则CPP是NP困难的。

TSP问题

Traveling Salesman Problem，即旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题。

TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。

全国各地天气预报查询

上海市

市辖区