第4期 高尚，等：求解旅行商问题的近似多项式算法 ·343· 带上节点的移动，第1种力是来自城市的吸引力，使 的次序为C:-2C:-1C:CC+1C+2 得节点朝城市位置靠近；第2种力是来自“弹性带” 上邻近节点的张力，使得节点朝相邻节点的位置运 动.第1种力的目的是使“弹性带”能覆盖所有城 C 市，而第2种力的作用是使“弹性带”的长度保持最 短.正是在这2种力的作用下，弹性带上的各点不断 地移动.当网络最终达到稳定时，弹性带上的M个 图1加入一个最近的城市节点 Fig.1 Add a nearest neighbor city 点中至少有N个点非常接近城市所在位置，并使所 表1是8个城市的坐标，图2是8个城市时，按扩 有城市形成一闭合回路，从而得到一有效路径，即得 张方法访问城市的搜索顺序.扩张方法得到的路径 到TSP问题的一个近似最优解. 为：1,6,7,5,4,8,3,2.路径长度为12.260 扩张方法继承了弹性网络的思想，首先从最短 表18个城市坐标 2个城市出发，将其与离2个城市最近的1个城市 Table 1 Coordinates of 8 cities 连成一个三角形，想象这个环是一个正在逐渐被吹 大气球，由于气球的弹力，则气球先遇到离这个气球 城市 坐标 1 上所有城市较近的城市，也就是所有未访问城市中 (2,0) 2 (3,0) 先访问距离最近的城市，直至所有城市均被搜索到 3 (3,1) 在实际操作时将遇到一个关键问题，当扩张到 4 (3,2) 距离最短的某个城市时，如何把该城市加入到路径 5 (3.3) 中.假设当前路径中的一段为C:-2C:-1C,C+1C+2,C 6 (1,1) 是所有未访问城市中离该路径最近的城市，并假设 > (1,2) 城市C:与C的距离d(C:,C)为最短，下一步，把C 8 (5,1.1) 加入到当前路径中，有2种加入次序（如图1）： 与弹性网络相同，由于扩张方法不会产生交叉 Ci-2C:-ICC:CiC2 C-2C-1CCCi C2. 的路径，所以产生的解都相当不错.而且扩张方法避 当d(C-C)+d(C-1,C)+d(C,C)≤ 免了弹性网络的训练过程，直接搜索使得访问路径 d(Ci-,C)+d(Ci,Ci) 最短的城市，加快了求解速度.因为N个城市之间 时，即 d(C-1,C)+d(C,C+i)≤ 共有)N(N-1)个距离，寻找距离最近的城市的复 d(Ci,C)+d(C:,Cim). 杂性不超过0(N2),每次扩张1次增加1个城市，因 加人的次序为C:-2C-1C,C,C+1C+2,反之加入 此扩张算法的时间复杂度低于O(N3). 4 3 3 2 2 2 0 0 0 -1 0123456 -101234 5 2 (a)第1次扩张 (b)第2次扩张 (c)第3次扩张 4 4 3 2 2 0 0 23456 0123456 0123456 (d)第4次扩张 (e)第5次扩张 (f)第6次扩张 图2扩张方法的搜索次序 Fig.2 Searching order of expansion method