第六节 中国邮递员问题       (1) (2) (3)
    6.2 中国邮递员问题
    邮递员每次要走遍他所负责街区的每一条道路，投递完毕后仍须回到邮局，他应走什么路线才能使总路程最短。这个问题是由我国山东师范学院管梅谷教授在1962年首次提出的，所以国际上通称为中国邮递员问题。
    中国邮递员问题可以抽象为一个连通图，每个边都有一个非负权数，试求一个圈，过每边至少一次，并使圈的总权数最小。
    解此问题的基本思路是：若街区路无奇点，显然按欧拉图定理可以不重复地走遍所有街道回到出发位置。如果图中有奇点，每边只走一次又回到出发点是不可能的。如果要回到原地就得走些重复路，也就是在原来的街区图上添加一些边，使有奇点的图转换成无奇点的图。由于我们要求总权数最小，所以必须寻找使新增加的边的总权数最小的方案。我们称增加重复边使图中无奇点的方案为可行方案，称总权数最小的方案为最优方案。
    一般先确定一个可行方案，然后不断改善可行方案就能求出最优方案。具体作法如下：
    1.确定可行方案
    一个连通图中，若有奇点，则奇点个数必为偶数。把奇点配对后，沿连接每对奇点的链增加重复边，则新图中没有奇点，这样，带有重复边的新图就是可行方案。
    2.调整可行方案
    可以证明最优方案具有下述两条性质，并可以按这两条性质不断调整可行方案，直至获得最优方案。