Page 224 - 数学建模算法与应用
P. 224
Mathematical Modeling Algorithms and Applications
数学建模算法与应用
7. 在（vi）中得的图 G' 上求 Euler 回路即为中国邮递员问题的解。
多邮递员问题：
邮局有 k(k≥2) 位投递员，同时投递信件，全城街道都要投递，完成任务返
回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记
成 kPP。
kPP 的数学模型如下：
G(V，E) 是连通图 求 G 的回路 C1，&L，Ck ，使得
1.
2.
3.
（二）旅行商（TSP）问题
一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设
计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？
这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一
个有最小权的 Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，
目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但
不一定最优）的解。
一个可行的办法是首先求一个 Hamilton 圈 C ，然后适当修改 C 以得
到具有较小权的另一个 Hamilton 圈。修改的方法叫做改良圈算法。设初始
圈
1. 对于 1< i +1< j+n ，构造新的 Hamilton 圈：
它是由 C 中删去边 和 添加边 而得到的。若
，则以 代替 叫做 C 的改良圈。
2. 转 1.，直至无法改进，停止。
用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，
可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。
这个算法的优劣程度有时能用 Kruskal 算法加以说明。假设 C 是 G 中的最优
214
