.344 智能系统学报 第5卷 2收缩方法 (xm,yim）、(xmy)和(xmn,yme）.这4个边角有 可能与原来城市坐标重叠，也可能不重叠（如图3 与扩张方法思路相反的方法是收缩，首先确定 中“0”).然后找出分别与上面4个边角点最近的4 4个边角点，方法如下：分别比较出所有城市的x轴 个边角城市（如图中的“+”），这4个边角城市作为 的最小值x和最大值xa,y轴的最小值yan和最 初始路径 大值ymr,这样就得到4个边角坐标(xia,ymin）、 4 4 3 3 3 0 0 0 -1 1 0123456 10123456 0123456 (a)4个边角 (b)初始路径 (c)第1次收缩 4 3 3 2 0 0 0 123456 0123456 0123456 (d)第2次收猫 (e)第3次收缩 (f)第4次收缩 图3收缩方法的搜索次序 Fig.3 Searching order of shrink method 接下来的工作与扩展方法类似，搜索所有未访 100 问城市中距离离最近的城市，直至所有城市均被搜 形 索到。与扩张算法类似，其时间复杂度也低于 60 0(W3). 同样的例子，图3是扩张方法访问城市的搜索 顺序.搜索方法得到的路径为：1,2,3,4,8,5,7,6.路 径长度为12.602. 20 40 60 80100 2种方法的结果不一样，解的质量还可以接受， 由于收缩方法选择初始的4个城市不能保证把所有 图4 Oliver30的TSP最好的解 城市都包含四边形中，搜索过程中有时收缩，有时扩 Fig.4 The optimal tour of Oliver30 100 张，因此该方法的效果不如扩张方法好。 3实例分析 60 着重分析扩张方法，分别选用Oliver30(最好解 为420.15)和at48(TSPLIB提供的最好解为33522) 作为实验例子来研究.图4显示了目前Oliver30最 好解，图5显示了扩张方法解Oliver30的TSP解，路 20 40 ,60 80100 径长度为536.56.图6显示了att48最好解，图7显 图5扩张方法的Olivers30的TSP解 示了扩张方法求att48的解，路径长度为42439 Fig.5 The tour of Oliver30 by expansion method