第4期 高尚，等：求解旅行商问题的近似多项式算法 ·345· 610 城市选23，路径长度为3862.94（图9）.虽然完全 扩张方法不一定能找到最优解，但能在较短时间内 找到“次优解”也能满足实际需要. ×103 ×10 图6at48的最好的解 Fig.6 The optimal tour of att48 610 810 图9完全扩张方法的a48的解 Fig.9 The tour of att48 by complete expansion method 4结束语 在弹性网络算法基础上，提出了扩张方法和收 缩方法，它们时间复杂性低于O(N),经过比较扩 ×10 张方法的效果比较好.在扩张方法的基础上，提出随 图7扩张方法的a48的解 机扩张方法和完全扩张方法，完全扩张方法的时间 Fig.7 The tour of att48 by expansion method 复杂性低于O(N),仍然是一个多项式算法，运行 扩张方法首先从最短2个城市出发，将其与离 速度极快.由于TSP问题代表着一类组合优化问 2个城市最近的1个城市连成一个三角形，然后扩 题，并且TSP问题在实际工程中有许多应用，如电 展.实际上可以先随机挑选一个城市，然后找离该城 子地图、交通诱导、VLSI布线等.在很难找到最优解 市最短的第2个城市，后面的步骤与扩展方法相同， 的情况下，由完全扩张方法找到的“次优解”可满足 此方法称为随机扩张方法，这样随机的选取会增大 实际工程需要. 更好解的几率 参考文献： 由于扩张方法的复杂性为O(W3),复杂性不 高，可采取完全枚举法，分别以各个城市为第1个城 [1]邢文循，谢金星.现代优化计算方法[M].北京：清华大 市，然后找离该城市最短的第2个城市，后面的步骤 学出版社，1999：90-129. [2]高国华，沈林成，常文森.求解TSP问题的空间锐化模拟 与扩展方法相同，最后从N个结果中挑选最好的结 退火算法[J].自动化学报，1999,25(3)：425428. 果，此方法称为完全扩张方法.很显然其时间性低于 GAO Guohua,SHEN Lincheng,CHANG Wensen.Using 0(W). simulated annealing algorithm with search space sharpening 100 to solve traveling salesman problem[J].Acta Automatica 0 Sinica,1999,25(3):425428. [3]KIRKPATRICK S,GELATT JR,VECCHI J R.Optimization by simulated annealing[J].Science,1983,220:671-680. [4]康立山，谢云，尤矢勇，等.模拟退火算法[M].北京：科 20 学出版社，1994：150-151 [5]谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传 20 40 6080100 算法[J].计算机工程与应用，2002,38(8)：5860. XIE Shengli,TANG Min,DONG Jinxiang.An improved 图8完全扩张方法的Oliver30的解 genetic algorithm for TSP problem[J].Computer Engineer Fig.8 The tour of Oliver30 by complete expansion method ing and Applications,2002,38(8):58-60. 对于Oliver30问题，完全扩张方法最好的结果 [6]喻镝，凌捷，谢晓峰.用遗传算法求解CTSP[J].广东工 是：第1个城市选29，路径长度为485.11（图8）.对 业大学学报，2000,17(5)：5255. 于a48问题，完全扩张方法最好的结果是：第1个 YU Di,LING Jie,XIE Xiaofeng.Solving CTSP with genet-