第六节中国邮递员问题

在现实生活中，有许多问题，比如城市里的洒水车、扫雪车、垃圾清洁车和参观展览馆等最佳行走路线问题都可以归结为中国邮递员问题。中国邮递员问题的广泛应用，引起了人们极大研究兴趣，提出了许多有效算法。

一个邮递员每天投递邮件都要走遍他所负责投递区域内的每条街道，完成投递任务后回到邮局。他应怎样选择路线，才能使他所走的总路线最短？国际上称这个问题为中国邮递员问题，它是由我国数学家管梅谷教授于1960年首先提出并进行研究的。

中国邮递员问题也可以表示为：在一个有奇点的连通图中。要求增加一些重复边，使得新的连通图不含有奇点，并且增加的重复边总权最小。

我们把增加重复边后不含奇点的新的连通图叫做邮递路线，而总权最小的邮递路线叫做最优邮递路线。

下面我们来介绍初始邮递路线的确定，改进，以及一个邮递路线是否是最优路线的判定标准的方法——图上作业法。

【例5.8】某邮递员负责以下街道的邮递业务，求出行走路线，使每天走的路程最短。

图5-21

(1)初始邮递路线的确定方法

由于任何一个图中，奇点的个数为偶数，所以如果一个连通图有奇点，就可以把它们两两配成对，而每对奇点之间必有一条链(图是连通的)，我们把这条链的所有边作为重复边(虚线部分)追加到图中去，这样得到的新连通图必无奇点，这就给出了初始投递路线。

图5-22

(2)改进邮递路线

①一般地，在邮递路线上，如果有两条以上的多重边，从中去掉偶数条，那么可以得到一个总长度较少的邮递路线。

②对所有的圈，计算重复边的总权，大于该圈总权的一半时，作一次改进，在该圈上去掉重复边，另一半加上重复边，这时重复边的总权减小。

如在圈V₁V₂V₅V₄V₁中，重复边长度为4+5=9，大于该圈总权15的一半，所以去掉重复边V₄V₁V₂，在另一半加上重复边V₄V₅V₂。

以此类推，得到该问题的最优解如下图。